Optimal base for mpz_set_str()

Marc Glisse marc.glisse at inria.fr
Tue Sep 21 22:36:20 CEST 2010

On Tue, 21 Sep 2010, Paul Zimmermann wrote:

>> Any tips or suggestions?
> I would use the largest allowed power of two, i.e., 32. Conversion is O(n)
> for a power-of-two base, against O(M(n) log n) for other bases.

16 has the advantage that it is 2^4 and 4 is a divisor of 32 (or 64), 
whereas 32=2^5 doesn't have this nice property, so it must occasionally 
take bits from 2 limbs and the loop has too long a period to be unrolled 
(and possibly vectorized?).

Don't know if that's really important, it just looks like a reason why 32 
might not be as much faster compared to 16 as one might hope.

(now it sounds strange that the conversion has to go through a string)

Marc Glisse

More information about the gmp-discuss mailing list