Large number multiplication

Mark Dickinson mdickinson at enthought.com
Fri Jul 8 09:31:10 CEST 2011


On Jul 7, 9:30 am, Ulrich Eckhardt <ulrich.eckha... at 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



More information about the Python-list mailing list