128 or 96 bit integer types?

[mensanator at aol.com]

On Jul 28, 2:28?am, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> "mensana... at aol.com" <mensana... 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.

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