[PATCH] mini-gmp: avoid a mpz_sizeinbase call in mpz_get_str

[Niels Möller]

Pádraig Brady <P at draigBrady.com> writes:

> This two line patch avoids obviously redundant work,
> which results in 10x faster basenc --base58 at least.

Thanks, applied.

It's really curious that you got 10x speedup. One could reasonably
expect that mpz_sizeinbase should be faster than actually producing the
digits, or at the very least not slower. But after looking at the code,
I think understand why mpz_sizeinbase *is* significantly slower in
mini-gmp.

mpz_sizeinbase (when the base isn't a power of 2) is implemented as a
plain loop around mpn_div_qr_1_preinv dividing by the base. The function
is allowed to return a digit count that is one to large, to enable the
implementation to compute an approximative digit count by multiplying
the bit count by some constant related to the logarithm of the base. The
reason it wasn't implemented that way in mini-gmp was that I haven't
worked out the required error analysis.

On the other hand, producing the digits for a base that isn't a power of
two (the internal mpn_get_str_other function) uses the "big base" bb,
the largest power of the base that fits in a limb, and then loops around
mpn_div_qr_1_preinv dividing by bb. And then the individual digits are
produced using single-limb arithmetic.

So there's plenty of room for optimization of mini-gmp's mpz_sizeinbase,
contributions welcome.

Regards,
/Niels

PS. Torbjörn, when pushing the changes, I got a warning message

remote: added 1 changesets with 2 changes to 2 files
remote: notify: sending 1 subscribers 1 changes
remote: warning: changegroup.makesnap hook exited with status 12

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.