mpz_sizeinbase

[Winfried Dreckmann]

Hi,

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
following expression:

 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
program:

#include <gmp.h>
#include <stdio.h>

int main()
{
    mpz_t monster;
    mpz_init(monster);
    mpz_ui_pow_ui(monster, 10, 59632978);
    printf("size = %d\n", mpz_sizeinbase(monster, 10));
    return 0;
}

This produces the output: size = 59632978.
However, 10^59632978 has 59632979 digits in base 10.

Explanation:
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