gmp_printf bug?

Niels Möller nisse at lysator.liu.se
Wed Aug 3 22:54:24 CEST 2011


Torbjorn Granlund <tg at gmplib.org> writes:

> I hacked my code to avoid the exp calls.  I suppose this is what you
> suggested:

Something like that. Looks nice and simple when you implement it.

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

So it is mpz_root which is the bottleneck (in the case of linking with
dumpmp)? What is the less-silly approximation? nthroot(x, n) \appr
2^{bitsize(x) / n} or so?

After a quick look at dumpmp.c, I guess there are also significant
savings by having special cade to handle the case of *square* roots
(call to mpz_pow_ui unnecessary, and call to mpz_tdiv_q_ui can be
replaced by a shift).

BTW, do you have any error analysis? To me, it seems that if you want to
guarantee that the returned value can never be larger than the true
value of log_b(2) = log(2) / log(b), the square roots used, as well as
the multiplications, should be rounded *upwards* to the given precision.
Naturally, this doesn't matter much when the function is used only for a
small number of inputs, and you have some independent check that the
results are correct for all these inputs.

/nisse

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


More information about the gmp-devel mailing list