Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #9037

Re: Large number multiplication

Show all headers | View raw

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@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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Large number multiplication Billy Mays <noway@nohow.com> - 2011-07-06 15:30 -0400
  Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-06 14:02 -0600
    Re: Large number multiplication Billy Mays <noway@nohow.com> - 2011-07-06 16:21 -0400
      Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-06 14:37 -0600
      Re: Large number multiplication Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2011-07-07 10:30 +0200
        Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-07 09:49 -0600
        Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-07 09:50 -0600
        Re: Large number multiplication casevh <casevh@gmail.com> - 2011-07-07 10:46 -0700
        Re: Large number multiplication Mark Dickinson <mdickinson@enthought.com> - 2011-07-08 00:31 -0700
      Re: Large number multiplication Parerga <nabble.com@bodrato.it> - 2011-07-07 09:00 -0700
  Re: Large number multiplication Christian Heimes <lists@cheimes.de> - 2011-07-06 22:05 +0200
    Re: Large number multiplication Billy Mays <noway@nohow.com> - 2011-07-06 16:15 -0400
      Re: Large number multiplication Christian Heimes <lists@cheimes.de> - 2011-07-06 22:43 +0200
    Re: Large number multiplication Nobody <nobody@nowhere.com> - 2011-07-07 01:33 +0100

csiph-web