Return to Revisions

In case Martin R's excellent solution should not be fast enough: there is a trick for raising a number to the nth power without performing (n - 1) multiplications on it.

The basic idea is easily demonstrated:

$$x^4 = x * x * x * x = (x^2)^2$$

Or, as a more drastic example:

$$x^{16} = x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x = (((x^2)^2)^2)^2$$

Exponents that are not a power of two can also be handled efficiently:

$$x^5 = (x^2)^2 * x$$

How to decide which squaring of x to multiply into the result and which not? Easy: if the binary representation of the exponent has bit i set, then the ith squaring of x needs to be multiplied into the result. Although this is not a very mathematical way of putting things, it happens to be very practical.

The principles can be explored by using a builtin type as a stand-in for a big integer:

typedef uint64_t bigint_t;

bigint_t nth_power (bigint_t x, unsigned exponent)
{
   bigint_t result = 1;
   
   for ( ; exponent; exponent >>= 1)
   {
      if (exponent & 1)
      {
         result *= x;
      }
      
      x *= x;
   }
   
   return result;
}