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

[Niels Möller]

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?

Regards,
/Niels

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