c++ – overflow in mpz type using gmp mpz_pow_ui

Common beleif is that GMP is truly an arbitrary precision software, from the front page:

What is GMP?
GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on.

But that is (unfortunately) not true. A grep on the GMP code for the error overflow in mpz type shows it appears in mpz/init2.c, mpz/realloc.c, and mpz/realloc2.c. Basically (if you are not running on a CRAY machine), the abort you got happens here:

if (UNLIKELY (new_alloc > INT_MAX))
  fprintf (stderr, "gmp: overflow in mpz typen");
  abort ();

Thus whenever you try to create or calculate a number with more than 2^31 - 1 limbs (or machine words), GMP will abort. This is because the limbs of a number are accessed by an int index:

typedef struct
  int _mp_alloc;        /* Number of *limbs* allocated and pointed to by the _mp_d field.  */
  int _mp_size;         /* abs(_mp_size) is the number of limbs the last field points to.  If _mp_size is negative this is a negative number.  */
  mp_limb_t *_mp_d;     /* Pointer to the limbs.  */
} __mpz_struct;
typedef __mpz_struct mpz_t[1];

So, there is a practical limit for what GMP can calculate (note that on most machines you will won’t have that much RAM anyway, but there are special computers with very large RAM, and those require long indexing).

Read more here: Source link