ANN: BigDecimal - decimal arithmetic on very large intergers

[casevh at comcast.net]

M.-A. Lemburg wrote:
> casevh at comcast.net wrote:
> > BigDecimal is a Python class that supports decimal arithmetic on
very large integers. BigDecimal was inspired by the posting of BigDec
to c.l.py by Tim Peters. BigDecimal implements all the commonly used
integer methods. (It doesn't implement any of the binary/shifting
operations.)
> >
> > It has been optimized for performance. It uses a 4x4 Toom-Cook
algorithm for multiplication and a new, very fast, division algorithm.
If GMPY is available, it will be automatically used.
> >
> > Performance examples, computing the decimal represendation of the
42nd Mersenne prime:
> >     2**25964951 - 1
> >
> > Tim Peter's posting to c.l.py: 13 minutes 41 seconds
> > BigDecimal: 59 seconds
> > BigDecimal w/gmpy: 10 seconds
>
> You might want to look into mxNumber (part of the
egenix-mx-experimental
> package):
>
> 	http://www.egenix.com/files/python/mxNumber.html
>
> There's a C type called Integer in that package that basically
> wraps the GMP integer type.
>
> --
> Marc-Andre Lemburg
> eGenix.com
>
> Professional Python Services directly from the Source  (#1, Apr 01
2005)
> >>> Python/Zope Consulting and Support ...
http://www.egenix.com/
> >>> mxODBC.Zope.Database.Adapter ...
http://zope.egenix.com/
> >>> mxODBC, mxDateTime, mxTextTools ...
http://python.egenix.com/
>
________________________________________________________________________
>
> ::: Try mxODBC.Zope.DA for Windows,Linux,Solaris,FreeBSD for free !
::::

I have used mxNumber in the past. This library uses "super" digits with
hundreds / thousands of decimal digits and then builds builds
multiplication and division on those. The original motivation was that
the conversion time to / from decimal string format is O(n) instead of
O(n^2).

Using just native Python long support, the 4-way Toom-Cook
multiplication algorithm is faster than the built-in multiplication
when the numbers are several hundred thousand digits long. On my
machine, it is roughly twice as fast when multiplying one million digit
numbers. (The 4-way Toom-Cook is O(n^~1.4) versus O(n^~1.585) for the
Karatsuba multiplication in Python.)

The division algortihm in BigDecimal is effectively O(n^~1.4) also.
Using just native Python long support, the division algorithm is faster
than the built-in division algorithm when the numbers are several tens
of thousands digits long.

Interestingly, BigDecimal can do division faster than GMP 3.1.x with
numbers approximately 10 million digits in length. BigDecimal is faster
than GMP 4.1.4 with numbers of approximately 1 million digits in
length. (GMP 4 is faster for small, ~10,000 digits, than GMP 3, but
grows more quickly.)

casevh