gmp_printf bug?

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  You appear to do about 64^2 calls to mpz_root, per base. 64 ought to be
  enough.

Yep, if nothing else, one could table b^(1/2), b^(1/4), ...

  Algorithm sketch (variables assumed to be fixpoint, with all
  related bit fiddling omitted, totally untested):
  
I hacked my code to avoid the exp calls.  I suppose this is what you
suggested:

#define PREC 64
#define SCALE (PREC + 32)

/* Compute log(2)/log(b) as a fixnum. */
void
mp_2logb (mpz_t r, int bi)
{
  mpz_t t, t2, two, b;
  int i;

  mpz_init_set_ui (t, 1);
  mpz_mul_2exp (t, t, SCALE);

  mpz_init (t2);

  mpz_init_set_ui (two, 2);
  mpz_mul_2exp (two, two, SCALE);

  mpz_set_ui (r, 0);

  mpz_init_set_ui (b, bi);
  mpz_mul_2exp (b, b, SCALE);

  for (i = PREC-1; i >= 0; i--)
    {
      mpz_mul_2exp (b, b, SCALE);
      mpz_root (b, b, 2);

      mpz_mul (t2, t, b);
      mpz_tdiv_q_2exp (t2, t2, SCALE);

      if (mpz_cmp (t2, two) < 0)	/* not too large? */
	{
	  mpz_setbit (r, i);		/* set next less significant bit */
	  mpz_set (t, t2);		/* new value acceptable */
	}
    }

  mpz_clear (t);
  mpz_clear (t2);
  mpz_clear (two);
  mpz_clear (b);
}


Unfortunately, it stillruns stupidly slow at about 40 seconds on the
main GMP machine, using dumbmp.  Some improvements to dumbmp are needed.
With a less silly dumbmp mpz_root starting approximaton, time is down to
2.3s, which is OK.  (This is not super critical, but we don't want to a
GMP bootstrap to become 2 times slower just because of a table
computation.)

-- 
Torbjörn