128 or 96 bit integer types?

Paul Rubin http
Sat Jul 28 09:28:12 CEST 2007


"mensanator at aol.com" <mensanator at aol.com> writes:
> has 146 digits. And that's just the begining. The above
> actually represents a polynomial with 264 terms, the
> exponents of which range from 0 to 492. One of those
> polynomials can have over 50000 decimal digits when
> solved.

You should use gmpy rather than python longs if you're dealing with
numbers of that size.  Python multiplication uses a straightforward
O(n**2) algorithm where n is the number of digits.  This is the best
way for up to a few hundred or maybe a few thousand digits.  After
that, it's better to use more complicated FFT-based algorithms which
are O(n log n) despite their increased constant overhead.  Gmpy does this.



More information about the Python-list mailing list