gmp_printf bug?

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> I hit a slight snag when attempting to put this into a GMP bootstrap; It
> would take 8 hours to compute the 254 values using dumbmp.c, on the fast
> GMP main development machine.

You appear to do about 64^2 calls to mpz_root, per base. 64 ought to be
enough. Algorithm sketch (variables assumed to be fixpoint, with all
related bit fiddling omitted, totally untested):

  b = base;
  e = 0;
  x = 1;

  for (i=1; i <= bits_of_accuracy; i++)
    {
      /* Loop invariant: x = base ^ e */
      b = sqrt(b);
      eold = e;
      xold = x;

      e += 2^{-i};
      x *= b;
      if (x > 2)
        { e = eold; x = xold; }
    }

  return e;

The idea is to not restart mp_exp in each iteration, but go on from the
result for the previous bit.

Regards,
/nisse

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.