Figuring out $x^n$

Question

Exponents are used to represent multiplying by a number over and over. but big numbers, like $6^8$ are hard to calculate. is there any simple way to calculate big numbers of the form $x^y$? ($y>0$ and is whole)

Answer 1

One classic way is iterated squaring. Start with 1.

1. Write the exponent in binary form
2. Loop over digits starting with most significant-1:
   • if 1: multiply with x
   • if 0: don't multiply with x
3. Square the number, go to next digit and iterate 2 until we run out of digits.

Let's take example $9 = (1001)_2$

We start with most significant 1 bit:

1. it is 1, so we multiply with x, we now have $x$

2. new iteration, so we square, and we have $x^2$

3. digit nr 2 is 0, so we just square $(x^2)^2=x^4$
4. digit nr 3 is 0, so we just square $(x^4)^2 = x^8$
5. last digit is 1 so we multiply with x: $x(x^8) = x^9$

Answer 2

One short cut is to notice that $x^4 = (x^2)^2$ so it can be done with two multiplications rather than the obvious 3. The savings get bigger for higher powers $x^{16} = (((x^2)^2)^2)^2$ - four multiplications instead of 15. In those simple examples, the power is itself a power of 2 but you can do things such as $x^{17} = x(((x^2)^2)^2)^2$. Expressing $y$ in binary can help you plot an efficient combination of squaring and multiplying by $x$.