M.-A. Lemburg wrote:

> (E-Mail Removed) 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