CODEWITHSUNDEEP
c++overflowgmpexponentiation
Yoni Zohar
Yoni Zohar

Reputation: 311

overflow in mpz type using gmp mpz_pow_ui

I am getting an overflow error when calling mpz_pow_ui from gmp, with the maximum unsigned long int value. According to the signature here, this is supposed to work, shouldn’t it? What am I missing?

Example:

example.cpp:

#include <gmp.h>
#include <limits>

int main(){
  unsigned long int exp = std::numeric_limits<unsigned long int>::max();
  mpz_t result;
  mpz_t three;
  mpz_init(three);
  mpz_set_ui(three, 3);
  mpz_pow_ui(result, three, exp);
}

$ gcc -oexample example.cpp -lgmp
$ ./example 
gmp: overflow in mpz type
Aborted

Upvotes: 2

Views: 699

Answers (2)

Arc
Arc

Reputation: 462

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 type\n");
  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).

EDIT: INT_MAX is a definition from the standard (Appendix E - Implementation limits) defintion of numeric limits, limits.h, which was included in GMP in gmp-impl.h in 2014:

#  define INT_MAX        2147483647

EDIT 2: The OP asks in a comment why is the parameter to mpz_pow_ui an unsigned long int and not an unsigned int, since it cannot compute with all of the values of an unsigned long int exponent. This is because GMP is, according to 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. GMP has a rich set of functions, and the functions have a regular interface.

Well, all GMP functions named with an ui work with an unsigned long int, see mpz_get_ui, mpz_add_ui, mpq_set_ui, mpz_fac_ui, mpf_add_ui, and many others.

Its just not worth to mix arbitrary precision mpn_, mpz_, and mpq_ functions with simple ints or unsigned ints, since these are trivially converted to longs. That's one of the reasons they say the interface is regular, all functions named ui work with unsigned long ints and all functions named si work with long ints, no function that mixes native integer types with "arbitrary precision" integers work with simple non-long ints.

The pow functions are among the few of GMP's ui functions that cannot produce a result for a long argument, so it makes no sense to make only those functions to work with simple non-long ints, since this would confuse the interface.

But I agree that GMP maintainers should be more clear about the limitations of the library.

Upvotes: 2

kelalaka
kelalaka

Reputation: 5636

There are various points to be considered in your code;

  1. You have to init every variable. You can also use Combined Initialization and Assignment Functions
 void mpz_init_set (mpz_t rop, const mpz_t op)
 void mpz_init_set_ui (mpz_t rop, unsigned long int op)
 void mpz_init_set_si (mpz_t rop, signed long int op)
 void mpz_init_set_d (mpz_t rop, double op)

  1. You have to free the memory with mpz_clear or mpz_clears.

  2. You use C++ to code, however, you are using C API of GNU/GMP. You may consider using the C++ interface.

  3. The main function should return. If there is no return value, 0 is returned by default. Even in the void case, some programmers always prefer a return statement.

  4. The exponent is too big; 3^18446744073709551615. That is ~10^18 digits

    #include <gmp.h>
    #include <limits>
    
    int main(){
    
     unsigned long int exp = std::numeric_limits<unsigned long int>::max();
    
      mpz_t result;
      mpz_t three;
      
      //init the memory
      mpz_init(three);
      mpz_init(result);
     
      mpz_set_ui(three, 3);
      mpz_pow_ui(result, three, exp);
    
      //free the memory
      mpz_clear(three);
      mpz_clear(result);

      return 0;
    }

Upvotes: 1

Related Questions