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

[Marco Bodrato]

Ciao David,

Il giorno Mercoledi, Ottobre 14, 2026 21:31 CEST, David Sparks <sparks05 at proton.me> ha scritto:

> >   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?

The formula proposed by Niels is exactly the one used by the main GMP library.

So...

> (TL;DR: The first failure occurs when b=5 and k=2655232169.)

> Making the search easy, the worst case happens very early, in base 5.
> 2^32 * log_5 2 = 1849741732.079068, rounding up by \eps = 0.920932
> to w = 1849741733.  From there, it's easy to see that we don't need
> to consider bases greater than 6.144 (although I checked up to 1000
> in my first draft code).

...as we can check that value 1849741732 + 1 is exactly the one generated 

$ tcc -run gen-bases.c table 32 0 | grep \ 5\ 
  /*   5 */ { 13, CNST_LIMB(0x6e40d1a4), CNST_LIMB(0x4a4d3c25), CNST_LIMB(0x48c27395), CNST_LIMB(0xc25c2684) },

0x6e40d1a4 is 1849741732

> FWIW, here are the first 10 failures in base-5:
> Gotcha!  k=2655232169 n=1143546251 n'=1143546253

...should we take this as a bug report against the 32-bits version of the main library?

gmp-impl.h reads

#define DIGITS_IN_BASEGT2_FROM_BITS(res, nbits, b)                      \
  do {                                                                  \
    mp_limb_t _ph, _dummy;                                              \
    size_t _nbits = (nbits);                                            \
    umul_ppmm (_ph, _dummy, mp_bases[b].logb2 + 1, _nbits);             \
    res = _ph + 1;                                                      \
  } while (0)

I tried this with the main library:
void check_5 (void)
{
  mpz_t n;
  unsigned long base = 5;
  unsigned long exponent = 1143546251UL;

  mpz_init (n);
  mpz_ui_pow_ui (n, base, exponent);
  mpz_sub_ui (n, n, 1);

  printf("Should have %lu <= %zu <= %lu\n", exponent, mpz_sizeinbase (n, base), exponent + 1);
}

With the 32-bits version of the library, it prints
Should have 1143546251 <= 1143546253 <= 1143546252

We should reconsider the implementation of sizeinbase for the main library too.

Ĝis,
mb