• Welcome to Valhalla Legends Archive.
 

Huge Powers

Started by R.a.B.B.i.T, May 13, 2005, 11:02 AM

Previous topic - Next topic

Adron

Quote from: rabbit on May 14, 2005, 07:35 PM
That is faring a little better, but even still, the returns top out at x ** 31 (2 ** 31 ==-2147483648, 31 ** 31 == -2010103841, and the such), they simply start rolling over to negatives then to 0.  Using unsigned __int64 does not resolve this issue, and I am still at a loss.

You need to have big numbers. If you take a ready-made library, it will most likely come with a powers algorithm that works for huge powers. Otherwise you need to implement the operations used by the algorithm Yoni described. I think of the algorithm like this:

integer Power(integer a, integer b)
{
   integer result, factor;
   for(result = 1, factor = a; b > 0; factor = factor * factor, b >>= 1) {
      if(b & 1) result = result * factor;
   }
   return result;
}

R.a.B.B.i.T

I'll have a look at the libraries, and see what I can understand of them.  As for Adron's implementation: it's 1/3 the length of mine...guess that shows how well I know what I'm doing...