Large number multiplication

[casevh]

On Jul 7, 1:30 am, Ulrich Eckhardt <ulrich.eckha... at dominolaser.com>
wrote:
> Billy Mays wrote:
> > On 07/06/2011 04:02 PM, Ian Kelly wrote:
> >> According to Wikipedia:
>
> >> """
> >> In practice the Schönhage–Strassen algorithm starts to outperform
> >> older methods such as Karatsuba and Toom–Cook multiplication for
> >> numbers beyond 2**2**15 to 2**2**17 (10,000 to 40,000 decimal digits).
> >> """
>
> >> I think most Python users are probably not working with numbers that
> >> large, and if they are, they are probably using specialized numerical
> >> libraries anyway, so there would be little benefit in implementing it
> >> in core.
>
> > You are right that not many people would gain significant use of it.
>
> Even worse, most people would actually pay for its use, because they don't
> use numbers large enough to merit the Schönhage–Strassen algorithm.
>
> > The reason I ask is because convolution has a better (best ?) complexity
> > class than the current multiplication algorithm.
>
> The "asymptotic complexity" of algorithms (I guess that's what you mean) is
> concerned with large up to infinite n elements in operations. The claim
> there always excludes any number of elements below n_0, where the complexity
> might be different, even though that is usually not repeatedly mentioned. In
> other words, lower complexity does not mean that something runs faster, only
> that for large enough n it runs faster. If you never realistically reach
> that limit, you can't reap those benefits.
>
> That said, I'm sure that the developers would accept a patch that switches
> to a different algorithm if the numbers get large enough. I believe it
> already doesn't use Karatsuba for small numbers that fit into registers,
> too.
>
> > I was more interested in finding previous discussion (if any) on why
> > Karatsuba was chosen, not so much as trying to alter the current
> > multiplication implementation.
>
> I would hope that such design decisions are documented in code or at least
> referenced from there. Otherwise the code is impossible to understand and
> argue about.
>
> Cheers!
>
> Uli
>
> --
> Domino Laser GmbH
> Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932- Hide quoted text -
>
> - Show quoted text -

A quick search on the Python issue tracker (bugs.python.org) yields
the following issues:

http://bugs.python.org/issue560379

http://bugs.python.org/issue4258

The issues also refer to discussion threads on the python-dev mailing
list.

casevh