This comment was just posted to the gmp-devel mail list.  It seems
relevant to the discussion on how to compute exact-integer-log.
Unfortunately I don't have time now to compare it with the existing
sample implementation.

Brad

-------- Forwarded Message --------
Subject: Re: [PATCH] mini-gmp: avoid a mpz_sizeinbase call in mpz_get_str
Date: Wed, 14 Oct 2026 15:59:35 +0200
From: Niels Möller <xxxxxx@lysator.liu.se>
To: Pádraig Brady <xxxxxx@draigBrady.com>
CC: xxxxxx@gmplib.org

---- External Email: Use caution with attachments, links, or sharing
data ----

Niels Möller <xxxxxx@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?

Regards,
/Niels

--
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
_______________________________________________
gmp-devel mailing list
xxxxxx@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel