Large powers

[tim1234]

How would you write an algorithm in C to calculate large numbers raised to large numbers modulo n. (numbers in the 10,000s) so obviously can't just do it straight off.

I tried working out x, x^2, x^4 and somehow using the binary representation of the power to work it out but I have no idea how to program this.

[WingedPanther]

int power(int base, int exponent, int modulo)
{
  if exponent=1 return base % modulo;
  if not (exponent % 2)
     return power(base*base%modulo,exponent/2,modulo)
  else
     return power(base*base%modulo,exponent/2,modulo)*base%modulo;
}

[DevilsCharm]

A power to the 10,000? That's really large, although I've always thought if supercomputers can process really, really, really big numbers.

[xXHalfSliceXx]

Sounds like we are doing your HW for you? 0_o

Good Luck

[TcM]

Originally Posted by WingedPanther

int power(int base, int exponent, int modulo)
{
  if exponent=1 return base % modulo;
  if not (exponent % 2)
     return power(base*base%modulo,exponent/2,modulo)
  else
     return power(base*base%modulo,exponent/2,modulo)*base%modulo;
}

When theres Math.. WingedPanther is the one
Good Job

[WingedPanther]

Maybe I should write some tutorials about math in programming.