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

[David Sparks]

Niels Möller <nisse at lysator.liu.se> wrote:
> * Do just one more bit, w = floor (2^33 / log_2 (b)), except for b = 3
>   where that doesn't fit in 32 bits. I would expect that should give
>   correct result up to k = 2^32 - 1.

To be specific, with a multiplier of 2^33, w=1849741733 and the
worst case is still base-5, but the theoretical limit increases
to 5809073916.488212, and the first actual failures are at

k=7319019764 n=1576065120 n'=1576065122
k=7319069235 n=1576075773 n'=1576075775
k=7319118706 n=1576086426 n'=1576086428
k=7319128003 n=1576088428 n'=1576088430
k=7319168177 n=1576097079 n'=1576097081
k=7319177474 n=1576099081 n'=1576099083
k=7319217648 n=1576107732 n'=1576107734
k=7319226945 n=1576109734 n'=1576109736
k=7319276416 n=1576120387 n'=1576120389
k=7319285713 n=1576122389 n'=1576122391

Since log 2/log 5 = 0.215338, w could use a multiplier
of 2^34, but then you'd have the problem that k*w overflows
64 bits for k > 4986302614 = 0x12934f096, so you've lost
range.