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

Groups > comp.lang.python > #8975 > unrolled thread

Large number multiplication

Back to article view | Back to comp.lang.python

Contents

  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

#8975 — Large number multiplication

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?

--
Bill

[toc] | [next] | [standalone]

#8981

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?

According to Wikipedia:

"""
In practice the Schönhage–Strassen algorithm starts to outperform
older methods such as Karatsuba and Toom–Cook multiplication for
numbers beyond 2**2**15 to 2**2**17 (10,000 to 40,000 decimal digits).
"""

I think most Python users are probably not working with numbers that
large, and if they are, they are probably using specialized numerical
libraries anyway, so there would be little benefit in implementing it
in core.

[toc] | [prev] | [next] | [standalone]

#8985

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?
>
> According to Wikipedia:
>
> """
> In practice the Schönhage–Strassen algorithm starts to outperform
> older methods such as Karatsuba and Toom–Cook multiplication for
> numbers beyond 2**2**15 to 2**2**17 (10,000 to 40,000 decimal digits).
> """
>
> I think most Python users are probably not working with numbers that
> large, and if they are, they are probably using specialized numerical
> libraries anyway, so there would be little benefit in implementing it
> in core.

You are right that not many people would gain significant use of it. 
The reason I ask is because convolution has a better (best ?) complexity 
class than the current multiplication algorithm.  I do like the idea of 
minimizing reliance on external libraries, but only if the changes would 
be useful to all the regular users of python.

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.

Side note: Are Numpy/Scipy the libraries you are referring to?

--
Bill

[toc] | [prev] | [next] | [standalone]

#8986

On Wed, Jul 6, 2011 at 2:21 PM, Billy Mays <noway@nohow.com> wrote:
> Side note: Are Numpy/Scipy the libraries you are referring to?

I was thinking more of gmpy or mpmath, but I'm not personally well
acquainted with any of them.

[toc] | [prev] | [next] | [standalone]

#9016

Billy Mays wrote:
> On 07/06/2011 04:02 PM, Ian Kelly wrote:
>> According to Wikipedia:
>>
>> """
>> In practice the Schönhage–Strassen algorithm starts to outperform
>> older methods such as Karatsuba and Toom–Cook multiplication for
>> numbers beyond 2**2**15 to 2**2**17 (10,000 to 40,000 decimal digits).
>> """
>>
>> I think most Python users are probably not working with numbers that
>> large, and if they are, they are probably using specialized numerical
>> libraries anyway, so there would be little benefit in implementing it
>> in core.
> 
> You are right that not many people would gain significant use of it.

Even worse, most people would actually pay for its use, because they don't 
use numbers large enough to merit the Schönhage–Strassen algorithm.


> The reason I ask is because convolution has a better (best ?) complexity
> class than the current multiplication algorithm.

The "asymptotic complexity" of algorithms (I guess that's what you mean) is 
concerned with large up to infinite n elements in operations. The claim 
there always excludes any number of elements below n_0, where the complexity 
might be different, even though that is usually not repeatedly mentioned. In 
other words, lower complexity does not mean that something runs faster, only 
that for large enough n it runs faster. If you never realistically reach 
that limit, you can't reap those benefits.

That said, I'm sure that the developers would accept a patch that switches 
to a different algorithm if the numbers get large enough. I believe it 
already doesn't use Karatsuba for small numbers that fit into registers, 
too.


> 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 would hope that such design decisions are documented in code or at least 
referenced from there. Otherwise the code is impossible to understand and 
argue about.


Cheers!

Uli

-- 
Domino Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932

[toc] | [prev] | [next] | [standalone]

#9034

On Thu, Jul 7, 2011 at 2:30 AM, Ulrich Eckhardt
<ulrich.eckhardt@dominolaser.com> wrote:
> Even worse, most people would actually pay for its use, because they don't
> use numbers large enough to merit the Schönhage–Strassen algorithm.

As it stands, Karatsuba is only used for numbers greater than a
specific threshold.  Adding Schönhage–Strassen would just mean adding
another threshold, below which Karatsuba would still be used.  So at
worst it would just add another comparison or two for numbers within
the Karatsuba range.

[toc] | [prev] | [next] | [standalone]

#9035

On Thu, Jul 7, 2011 at 9:49 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Thu, Jul 7, 2011 at 2:30 AM, Ulrich Eckhardt
> <ulrich.eckhardt@dominolaser.com> wrote:
>> Even worse, most people would actually pay for its use, because they don't
>> use numbers large enough to merit the Schönhage–Strassen algorithm.
>
> As it stands, Karatsuba is only used for numbers greater than a
> specific threshold.  Adding Schönhage–Strassen would just mean adding
> another threshold, below which Karatsuba would still be used.  So at
> worst it would just add another comparison or two for numbers within
> the Karatsuba range.

And I just realized that you said as much yourself further down in
your message.  My apologies for the needless lecturing.

[toc] | [prev] | [next] | [standalone]

#9045

On Jul 7, 1:30 am, Ulrich Eckhardt <ulrich.eckha...@dominolaser.com>
wrote:
> Billy Mays wrote:
> > On 07/06/2011 04:02 PM, Ian Kelly wrote:
> >> According to Wikipedia:
>
> >> """
> >> In practice the Schönhage–Strassen algorithm starts to outperform
> >> older methods such as Karatsuba and Toom–Cook multiplication for
> >> numbers beyond 2**2**15 to 2**2**17 (10,000 to 40,000 decimal digits).
> >> """
>
> >> I think most Python users are probably not working with numbers that
> >> large, and if they are, they are probably using specialized numerical
> >> libraries anyway, so there would be little benefit in implementing it
> >> in core.
>
> > You are right that not many people would gain significant use of it.
>
> Even worse, most people would actually pay for its use, because they don't
> use numbers large enough to merit the Schönhage–Strassen algorithm.
>
> > The reason I ask is because convolution has a better (best ?) complexity
> > class than the current multiplication algorithm.
>
> The "asymptotic complexity" of algorithms (I guess that's what you mean) is
> concerned with large up to infinite n elements in operations. The claim
> there always excludes any number of elements below n_0, where the complexity
> might be different, even though that is usually not repeatedly mentioned. In
> other words, lower complexity does not mean that something runs faster, only
> that for large enough n it runs faster. If you never realistically reach
> that limit, you can't reap those benefits.
>
> That said, I'm sure that the developers would accept a patch that switches
> to a different algorithm if the numbers get large enough. I believe it
> already doesn't use Karatsuba for small numbers that fit into registers,
> too.
>
> > 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 would hope that such design decisions are documented in code or at least
> referenced from there. Otherwise the code is impossible to understand and
> argue about.
>
> Cheers!
>
> Uli
>
> --
> Domino Laser GmbH
> Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932- Hide quoted text -
>
> - Show quoted text -

A quick search on the Python issue tracker (bugs.python.org) yields
the following issues:

http://bugs.python.org/issue560379

http://bugs.python.org/issue4258

The issues also refer to discussion threads on the python-dev mailing
list.

casevh

[toc] | [prev] | [next] | [standalone]

#9070

On Jul 7, 9:30 am, Ulrich Eckhardt <ulrich.eckha...@dominolaser.com>
wrote:
> That said, I'm sure that the developers would accept a patch that switches
> to a different algorithm if the numbers get large enough. I believe it
> already doesn't use Karatsuba for small numbers that fit into registers,
> too.

I'm far from sure that such a patch would be accepted. :-)  Indeed,
Tim Peters has been heard to mention that if he were to do it all
again, he probably wouldn't even have implemented Karatsuba [1].
Asymptotically fast integer multiplication is a specialist need that's
already available in 3rd-party Python libraries (gmpy).  IMO, it's not
appropriate to include it in a general-purpose programming language,
and the burden of maintaining such code would outweigh the benefits.

One thing that has been considered in the past is making it possible
to use GMP directly for Python's implementation of long integers;  see
Victor Stinner's efforts in this direction [2].  Licensing concerns,
and the fact that Python's implementation is faster for small
integers, ended up killing this issue.

[1] http://mail.python.org/pipermail/python-dev/2008-November/083355.html
[2] http://bugs.python.org/issue1814

--
Mark

[toc] | [prev] | [next] | [standalone]

#9037

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.

[toc] | [prev] | [next] | [standalone]

#8982

Am 06.07.2011 21:30, schrieb Billy Mays:
> 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 Karatsuba algorithm uses just addition, subtraction and
multiplication, so you don't need to resort to floats and have no
rounding errors. On the other hand FFT are based on e, complex numbers
or trigonometric functions (=floats), which mean you'll get rounding errors.

We don't want rounding errors for large long multiplication.

Christian

[toc] | [prev] | [next] | [standalone]

#8984

On 07/06/2011 04:05 PM, Christian Heimes wrote:
> Am 06.07.2011 21:30, schrieb Billy Mays:
>> 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 Karatsuba algorithm uses just addition, subtraction and
> multiplication, so you don't need to resort to floats and have no
> rounding errors. On the other hand FFT are based on e, complex numbers
> or trigonometric functions (=floats), which mean you'll get rounding errors.
>
> We don't want rounding errors for large long multiplication.
>
> Christian
>

I believe it is possible to do FFTs without significant rounding error. 
  I know that the GIMPS's Prime95 does very large multiplications using 
FFTs (I don't know if they use the integer based or double based 
version).  I also know they have guards to prevent rounding errors so I 
don't think it would be impossible to implement.

--
Bill

[toc] | [prev] | [next] | [standalone]

#8987

Am 06.07.2011 22:15, schrieb Billy Mays:
> I believe it is possible to do FFTs without significant rounding error. 
>   I know that the GIMPS's Prime95 does very large multiplications using 
> FFTs (I don't know if they use the integer based or double based 
> version).  I also know they have guards to prevent rounding errors so I 
> don't think it would be impossible to implement.

It might work for medium large longs but how about really large longs
like 5 * 1,000**10,000? I'm not familiar with FFT based multiplication
but I guess that very large numbers are going to introduce rounding
errors if floating points are involved.

Python used to run on platforms without an FPU and floats. These days
Python might still run on platforms with just an emulated FPU. Unless
there is a way to implement FFT without floating point ops, an emulated
or missing FPU makes FFT slower than Karatsuba. There might be one but I
haven't learned a way in my numerics classes.

Christian

[toc] | [prev] | [next] | [standalone]

#9004

On Wed, 06 Jul 2011 22:05:52 +0200, Christian Heimes wrote:

> On the other hand FFT are based on e, complex numbers or
> trigonometric functions (=floats), which mean you'll get rounding errors.

It's possible to perform a DFT over any field. Schoenhage-Strassen uses
a DFT over a finite field (integers modulo N); it doesn't use floats.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web