Large number multiplication

Parerga at
Thu Jul 7 12:00:08 EDT 2011


Billy Mays wrote:
>> On 07/06/2011 04:02 PM, Ian Kelly wrote:
>> > On Wed, Jul 6, 2011 at 1:30 PM, Billy Mays<noway at>  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?
>> The reason I ask is because convolution has a better (best ?) complexity 

Better complexity, yes. This means "smaller execution time for LARGE ENOUGH

Billy Mays wrote:
>> 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'm not a python developer, but I worked on multiplication algorithms for
GMP  [ ], and I can guess the answer:
 - Karatsuba is (by far) simpler to implement,
 - FFT-based multiplication is (by far) slower than Karatsuba for numbers
that are not huge.
I try to attach a small graph karaVSfft.pdf , with
timings for multiplications of n-bits operands (with GMP, on my very old
laptop) with Toom(2,2) (it's Karatsuba!) and the FFT-based computation. The
first is faster than the latter up to 10000 bits (GMP uses some Toom for
that size, to get the result even faster).


View this message in context:
Sent from the Python - python-list mailing list archive at

More information about the Python-list mailing list