On 07/06/2011 04:02 PM, Ian Kelly wrote:
On Wed, Jul 6, 2011 at 1:30 PM, Billy Mays<no...@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
--
http://mail.python.org/mailman/listinfo/python-list
