mpz_sizeinbase

[Torbjorn Granlund]

  > Now, suppose the return value of mpz_sizeinbase(op, base) is
  > numdigs and I want to know the *exact* number of digits. The most
  > straightforward way is to compare op with base^(numdigs-1) and
  > then reduce numdigs by 1 if op is less than base^(numdigs-1). Is
  > there a better way?

  Not that I know of.

One could compute t=approx(base^n/2^m), where n is initially
chosen to a suitable value less than returned mpz_sizeinbase(op,
base).  During the computation of base^n, low limbs should be
truncated gradually,

Then, we compute op/t and op/(t+1) and convert these small number
to to base.  If they are the same number of digits, we're done.
Else, decrease m and try again...

On average, this should be very fast.

  > By the way, is it too expensive to *always* return the exact
  > number of digits when base is not 2 ?

  It already does so. :-) (And it always did I think, but it's
  has only recently been documented.)

No, the results are exact just for powers of 2.

--
Torbjörn