Paul Rubin wrote: > "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> 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.
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 -- http://mail.python.org/mailman/listinfo/python-list
