Pow() calculates wrong?

Question

I need to use pow in my c++ program and if i call the pow() function this way:

long long test = pow(7, e);

Where

e is an integer value with the value of 23.

I always get 821077879 as a result. If i calculate it with the windows calculator i get 27368747340080916343.. Whats wrong here? ):

I tried to cast to different types but nothing helped here... What could be the reason for this? How i can use pow() correctly?

Thanks!

Answer 1

The result is doesn't fit in long long.

If you want to deal with very big numbers then use a library like GMP

Or store it as a floating point (which won't be as precise).

Applying modulo:

const unsigned int b = 5; // base
const unsigned int e = 27; // exponent
const unsigned int m = 7; // modulo

unsigned int r = 1; // remainder

for (int i = 0; i < e; ++i)
  r = (r * b) % m;

// r is now (pow(5,27) % 7)

Answer 2

7²³ is too big to fit into a long long (assuming it's 64 bits). The value is getting truncated.

Edit: Oh, why didn't you say that you wanted pow(b, e) % m instead of just pow(b, e)? That makes things a whole lot simpler, because you don't need bigints after all. Just do all your arithmetic mod m. Pubby's solution works, but here's a faster one (O(log e) instead of O(e)).

unsigned int powmod(unsigned int b, unsigned int e, unsigned int m)
{
   assert(m != 0);

   if (e == 0)
   {
      return 1;
   }
   else if (e % 2 == 0)
   {
      unsigned int squareRoot = powmod(b, e / 2, m);
      return (squareRoot * squareRoot) % m;
   }
   else
   {
      return (powmod(b, e - 1, m) * b) % m;
   }
}