gmp_printf bug?
Torbjorn Granlund
tg at gmplib.org
Wed Aug 3 21:34:17 CEST 2011
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
More information about the gmp-devel
mailing list