On Jul 28, 2:28?am, Paul Rubin <http://[EMAIL PROTECTED]> 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. 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.
I actually do use gmpy. Great stuff. But one thing I
learned about gmpy is to never use literals inside
a loop. Otherwise the mpz coercion has to be done
every time and that kills performance.
So you would do something like
import gmpy
ONE = gmpy.mpz(1)
TWO = gmpy.mpz(2)
TWE = gmpy.mpz(3)
n = gmpy.mpz(2**177149-1)
while n > ONE:
if n % TWO == 1
n = TWE*n + ONE
else:
n = n/TWO
--
http://mail.python.org/mailman/listinfo/python-list
