Paul Rubin wrote:

"me********@aol.com" <me********@aol.comwrites:
>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.

That's untrue since quite a while. CPython now uses

Karatsuba-multiplication if the number of digits is larger than a

certain threshold. Karatsuba is O(n**(log(3) / log(2)).

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.

Karatsuba is still slower than these algorithms, but only if you have

quite a big number of digits. Of course the core of your argument

remains valid: CPython is not up to providing extremely good big integer

arithmetic, so if you have extreme needs, you shouldn't use the builtin

longs.

Cheers,

Carl Friedrich Bolz