Large number multiplication

[Ulrich Eckhardt]

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