Large number multiplication

[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?

 

[Ian Kelly]

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.

 

[Billy Mays]

Am 06.07.2011 21:30, schrieb Billy Mays:

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.

 

[Billy Mays]

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?

 

[Ian Kelly]

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.

 

[Nobody]

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.

 

[Ulrich Eckhardt]

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

 

[Ian Kelly]

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.

 

[Ian Kelly]

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.

 

[Parerga]

Hi,



Better complexity, yes. This means "smaller execution time for LARGE ENOUGH
operands"



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

 

[casevh]

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 "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 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

 

[Mark Dickinson]

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