overflow in mpz type using gmp mpz_pow

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

CodePudding user response：

There are various points to be considered in your code;

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)

You have to free the memory with mpz_clear or mpz_clears.
You use C to code, however, you are using C API of GNU/GMP. You may consider using the C interface.
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.
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;
    }

CodePudding user response：

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).