gmp_printf bug?
Torbjorn Granlund
tg at gmplib.org
Thu Jul 21 12:57:51 CEST 2011
[This thread comes from gmp-bugs. For some background, please see
http://gmplib.org/list-archives/gmp-bugs/2011-July/002300.html, and
http://gmplib.org/list-archives/gmp-bugs/2011-July/002303.html.]
Torbjorn Granlund <tg at gmplib.org> writes:
A possible aproach would be to store the chars_per_bit_exactly field as
an mp_limb_t (which always >= size_t) and use umul_ppmm and keep the
high word. There are a couple of problems with that approach, though.
I see two approaches for the problem.
(1) Implement the solution above, with a single-word fixed-point
approximation of the logarithms. Using mp_limb_t for these words seems
attractive, but will not work in GMP 5.1 where mp_limb_t will be
slightly more abstract internally (to improve testing, by allowing tiny
limbs sizes). We will need mp_size_t size arithmetic, conditionally
abusing longlong.h to give us that.
(2) Stay with the 'double' approximation but cope with its poor accuracy
for large mpf exponents. This would require a rewrite of (at least)
mpf/get_str.c, making it iterate in the code that generates a suitable
integer for passing to mpn_get_str. (In practice, we would only make
one iteration for normal exponents, and two iterations for tiny/huge
exponents.)
I analysed the current problem in some more depth, and as I suspected,
some bases will cause too few digits to be produced (including no digits
at all) for these huge exponents (greater than 2^53).
There is an anti-symmetric problem for tiny exponents (less than -2^53);
here bases with a logarithm rounded upward in GMP's table will cause too
many digits to be generated (and as a result potential memory
corruption), while other bases will give too few digits. No surprises
there.
I know how to implements solution 2. It will be some hours of work, and
some hours of validating results.
I am not sure how to compute the more-than 53 bits accurate logarithm
tables needed for solution 1, in the very constrained environment of a
GMP compile. I see two solutions: (a) put 64-bit logarithms for all
bases in a master table, and truncate these as needed during compilation
and (b) teach the dumbmp.c bootstrap library to compute base-2
logarithms. Such computations need not be efficient at all, but it
still seems tricky.
--
Torbjörn
More information about the gmp-devel
mailing list