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

[Pádraig Brady]

On 14/10/2026 14:59, Niels Möller wrote:
> Niels Möller <nisse at lysator.liu.se> writes:
> 
>> The reason it wasn't implemented that way in mini-gmp was that I
>> haven't worked out the required error analysis.
> 
> Looking briefly at this again. Assume that x > 0 is an integer of k bits
> and n digits in base b. Then
> 
>    2^{k-1} <= x < 2^k
> 
> meaning that k = 1 + floor(log_2 x). Similarly
> 
>    b^{n-1} <= x < b^n
> 
> so that n = 1 + floor(log_b x). And the problem of mpn_sizeinbase is
> that given only k, we want to compute an n' such that n <= n' <= n+1.
> 
> Since log_b x = log_2 x / log_2 b, we can bound n like
> 
>    n = 1 + floor (log_b x) = 1 + floor (log_2 x / log_2 b)
>      <= 1 + floor (k / log_2 b)
> 
> And for the other direction, we can start from
> 
>    n > log_b x = log_2 x / log_2 b >= (k-1) / log_2 b
>      >= floor ((k-1) / log_2 b)
> 
> Since n is an integer, the strict inequality implies
>     
>    n >= 1 + floor ((k-1) / log_2 b)
> 
> So we have a rather narrow range
> 
>    1 + floor ((k-1) / log_2 b) <= n <= 1 + floor (k / log_2 b)
> 
> So it seems natural to use an approximation of 1 / log_2 b. E.g., say we
> put w = ceil (2^{32} / log_2 b), and
> 
>    n' = 1 + floor (k w / 2^{32})
> 
> Then n' >= n, but can n' be too large? The accuracy of w is limited, so
> for large enough k we'll surely get n' > n+1, but how large must k be
> for that to become a problem?

Your analysis looks correct to me.
You could use that to shortcut a huge range,
falling back to the existing implementation outside of that.

So how to bound the combined error from using the bit count
and rounding the reciprocal logarithm upwards?

Using k instead of log_2(x) overestimates by at most one bit.
In base b, that contributes at most 1/log_2(b) digits.
Since non-power-of-two bases are at least 3, this contribution is less than 3/4 of a digit.

Rounding 1/log_2(b) upward to a multiple of 2^-32 adds less than 2^-32 to the coefficient.
Multiplying by k therefore adds less than k/2^32 digits. For k <= 2^30, that is less than 1/4 of a digit.

The combined overestimate is thus less than one digit.

So the proposed approximation is safe through at least
2^30 bits, which is a handy cutoff point.

I've attached a proposed implementation to do that.

cheers,
Padraig
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mini-mpz_sizeinbase-fast.diff
Type: text/x-patch
Size: 1888 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20261014/57e02f93/attachment.bin>