GMP- Power without modulo

Question

I am trying to raise and arbitrarily larger number to an arbitrarily large power. As far as I can see, GMP has a function that does this, but applies modulo to the result, and a function that lets me raise an arbitrary number to an unsigned int exponent. Is there a way around this?

Answer 1

and a function that lets me raise an arbitrary number to an unsigned int exponent

It's an unsigned long int exponent, so if you are on a system where unsigned long is 64 bits (or more), that will take you beyond the available memory for the next few years (2^(2^64-1) needs a couple of Exabytes storage).

If you're on a system with 32-bit unsigned long, you can split the exponent in two parts,

if (exponent >= (1u << 31)) {
    mpz_pow_ui(base, base, exponent >> 31);
    mpz_pow_ui(base, base, 1u << 31);
}
mpz_pow_ui(base, base, exponent & ((1u << 31) - 1));

and that has very good chances of needing more memory than you have.

A further problem is that GMP uses ints to count the limbs, so typically you can't have numbers using more than (2^31 - 1)*BITS_PER_LIMB bits anyway (BITS_PER_LIMB is 32 or 64 depending on the platform, usually).

If you think you need a^b where a > 1 and b doesn't fit in an unsigned long (long), you will have problems with GMP and your memory anyway.