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<(E-Mail Removed)> 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-m...p32014454.html
Sent from the Python - python-list mailing list archive at Nabble.com.