Large number multiplication

[Billy Mays]

On 07/06/2011 04:02 PM, Ian Kelly wrote:
> On Wed, Jul 6, 2011 at 1:30 PM, Billy Mays<noway at nohow.com>  wrote:
>> I was looking through the python source and noticed that long multiplication
>> is done using the Karatsuba method (O(~n^1.5)) rather than using FFTs O(~n
>> log n).  I was wondering if there was a reason the Karatsuba method was
>> chosen over the FFT convolution method?
>
> 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. 
The reason I ask is because convolution has a better (best ?) complexity 
class than the current multiplication algorithm.  I do like the idea of 
minimizing reliance on external libraries, but only if the changes would 
be useful to all the regular users of python.

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.

Side note: Are Numpy/Scipy the libraries you are referring to?

--
Bill