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

[Niels Möller]

Pádraig Brady <P at draigBrady.com> writes:

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

And the reported example was for k = 2655232169 \approx 2.5 2^30.

> I've attached a proposed implementation to do that.

It would be nice if we could have just one case. There are a few options:

* Stick to 32-bit approximation, and accept that for numbers larger than
  mini-gmp's intended range, mpz_sizeinbase may give a slightly wrong
  result. Could do the multiplication as uint64_t, to not depend on limb
  size.

* Use 64-bit approximation everywhere. (For mpz_sizeinbase in the full
  gmp library, that could be the most reasonable fix).

* 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.

It's unfortunately not well defined how mini-gmp behaves when numbers
grow beyond sizes it can handle. Ideally, it should fail/crash in a
reliable way on overflow, but that would be rather difficult, I'm
afraid. And it would also be fine, I think, to declare that mini-gmp
works correctly only for numbers up to 2^30 bits.

Currently, mp_size_t is defined as a long, and mp_bitcnt_t as an
unsigned long. Which is overkill; it would make some sense and maybe
make some things simpler to pin those as always int32_t, while leaving
the mp_limb_t type as architecture dependent.

Regards,
/Niels

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