[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
mpz_sizeinbase
From: |
Winfried Dreckmann |
Subject: |
mpz_sizeinbase |
Date: |
Tue, 27 Mar 2001 08:25:23 +0200 |
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
- mpz_sizeinbase,
Winfried Dreckmann <=