Large number multiplication
Parerga
nabble.com at bodrato.it
Thu Jul 7 12:00:08 EDT 2011
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<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?
>
>> 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.
More information about the Python-list
mailing list