Hi,
Billy Mays wrote: > >> 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? > >> The reason I ask is because convolution has a better (best ?) complexity > Better complexity, yes. This means "smaller execution time for LARGE ENOUGH operands" 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 [ http://gmplib.org/ ], 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 http://old.nabble.com/file/p32014454/karaVSfft.pdf 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). Regards, Marco -- http://bodrato.it/software/toom.html -- View this message in context: http://old.nabble.com/Large-number-multiplication-tp32007815p32014454.html Sent from the Python - python-list mailing list archive at Nabble.com. -- http://mail.python.org/mailman/listinfo/python-list
