128 or 96 bit integer types?

[Carl Friedrich Bolz]

Paul Rubin wrote:
> "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. 

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