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