LARGE numbers

[casevh at comcast.net]

Paul Rubin wrote:
> aleax at mail.comcast.net (Alex Martelli) writes:
> > As the author of gmpy, I'd like to point out that the speed difference
> > isn't all that large, if all you're doing is ordinary arithmetic -- a
> > few times at most (it can be better if you need some of GMP's
> > functionality which gmpy exposes, such as primality testing).
>
> For numbers of this size, won't gmpy use FFT-based multiplication?
> That's potentially orders of magnitude faster than ordinary n**2
> multiplication.

Python's native longs use Karatsuba multiplication with is O(n^1.585).

My early version of DecInt (BigDecimal) uses 4-way Toom-Cook
multiplication which is O(n^1.4). My development version uses
Nussbaumer convolution with is O(n ln(n)).

For multiplicaiton of two 1,000,000 digits numbers and conversion to a
decimal string, here are some times:

GMPY
multiplication: 0.96 seconds
conversion to string: 712.7 seconds

DecInt with GMPY
multiplication: 1.33 seconds
conversion to string: 0.83 seconds

DecInt without GMPY
multiplication: 2.84 seconds
conversion to string: 0.45 seconds

Python (using native long)
multiplication: 8.47 seconds
conversion to string: a really long time

Case