[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Tue, 27 Mar 2001 08:25:23 +0200
I have a problem with the source code for "mpz_sizeinbase" in gmp 3.1.1.
If the base is not a power of 2 it calculates its result by the
return (size_t) (totbits * __mp_bases[base].chars_per_bit_exactly) + 1;
Here "totbits" is the number of significant bits and
"__mp_bases[base].chars_per_bit_exactly" an approximation of the
logarithm of 2 in the given base. Due to limited precision there is no
garantuee that this result is actually greater than the true
mathematical logarithm. As a consequence is may happen for very, very
large numbers that the result is 1 too small. (The manual states that
the result is exact or 1 too big.)
Numbers must be truely gigantic for this to happen. Clearly nobody will
want to print them. Just, how gigantic is not clear to me. I was able
to produce the following example:
gmp version: 3.3.1
machine: PowerPC 604e running Linux 2.2.14
compiler: gcc 2.95.2
mpz_ui_pow_ui(monster, 10, 59632978);
printf("size = %d\n", mpz_sizeinbase(monster, 10));
This produces the output: size = 59632978.
However, 10^59632978 has 59632979 digits in base 10.
The total number of bits is 198096465. With much higher precision:
198096465 * log_10(2) = 59632978.00000000259831659447
Using the gmp approximation:
198096465 * 0.3010299956639811 = 59632977.99999998373681149999
Here, (size_t) (totbits * __mp_bases[base].chars_per_bit_exactly)
gives 59632977 which is 1 too small.
Winfried Dreckmann <=