Large number multiplication

Thu Jul 7 13:46:35 EDT 2011

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