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. -- http://mail.python.org/mailman/listinfo/python-list
