DecInt: decimal arithmetic on very large integers

DecInt is a Python class that provides support for operations on very large decimal integers. Conversion to and from the decimal string representation is very fast. The multiplication and division algorithms are asymptotically faster than the algorithms native to Python. For numbers with 200,000 digits or more, multiplication is faster than the native Python long multiplication. Division is faster than native Python long division when numbers are 20,000 digits long. For additional performance, GMPY and/or psyco are used if available.

DecInt started as BigDec from a posting by Tim Peters to comp.lang.python. BigDec used decimal arithmetic to calculate the decimal representation of a large Mersenne prime. I tried to make it faster and I got a little carried away. ;-)

Performance

Multiplication: DecInt uses a 4-way Toom-Cook algorithm for multiplication of small numbers and Nussbaumer convolution for larger numbers. Multiplication is O(n ln(n)).

Division: DecInt uses a division algorithm by David M. Smith for small numbers. For large numbers, DecInt uses a modified version of Smith's algorithm with a running time of O(n ln(n)^2).

Example

# Compute the decimal form of the 43rd Mersenne prime.
import DecInt
bignum = DecInt.DecInt(2) ** 30402457 - 1
print len(bignum)

Optimized Program

DecInt supports an optional argument that controls how many decimal digits are stored in each term internally. The default value for DecInt w/GMPY is 1000 digits per term. 1000 works well for numbers with millions of digits.

When computing 2^power, the best performance is achieved when the total number of terms in the final result is a power of two. For M42, the optimal value for the number of digits per term is 955. This is close to, and less than, the default value of 1000 so the default value works well. Below is a short program that calculates the optimal number of digits per term. It is significantly faster for M43.

mersenne.py

Changes

Version 0.4.1
Support user-specified digits-per-term in __pow__.
Include mersenne.py example program.

Version 0.4
Version 0.4 fixes a serious bug in version 0.3.
DecInt is merged into a single file.
Some examples are added: gcd(), square_root(), pell()

Requirements

Python 2.4 or later
psyco (optional)
gmpy (optional, version 1.01 or later is required)

Download:

decint_041.zip
decint_041.tar.gz

GMPY binaries for Windows

GMPY binaries for Windows are available at http://code.google.com/p/gmpy.