Large number multiplication
noway at nohow.com
Wed Jul 6 22:21:03 CEST 2011
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
Side note: Are Numpy/Scipy the libraries you are referring to?
More information about the Python-list