Repeated squaring is a technique used to evaluate the $N^{\text{th}}$ term of a sequence in O(log N) time. It relies on an efficient method to compute $a_{n+m}$ from $a_n$ and $a_m$, for example, multiplying $x^n$ and $x^m$.

### The Algorithm

Suppose we have a fast way to compute $a_{n+m}$ from $a_n$ and $a_m$. Then, we can start by computing $a_1$, and computing $a_{2^k}$ for each $k$ by combining $a_k$ and $a_k$. Then, keeping track of a global $a_g$ starting at $a_0$, we add $2^k$ to $g$ if and only if the $2^k$ bit of $N$ is set. So, for example, if $N=6$, we add $2$ and $4$, but not $1$.

## Example: Raising a number to a power

Suppose we want to find $3^{104}$ efficiently. Multiplying 3 by itself 104 times is very inefficient. So instead we start the squaring. $104 = 1101000_2$.

$k$ | $2^k$ | kth bit in N | $a_{2^k}$ | $a_g$ |

0 | 1 | 0 | 3 | 1 |

1 | 2 | 0 | 9 | 1 |

2 | 4 | 0 | 81 | 1 |

3 | 8 | 1 | 6561 | 6561 |

4 | 16 | 0 | 43046721 | 6561 |

5 | 32 | 1 | 1853020188851841 | 12157665459056928801 |

6 | 64 | 1 | 3433683820292512484657849089281 | 41745579179292917813953351511015323088870709282081 |

So our answer is $41745579179292917813953351511015323088870709282081$. As a side note, to actually compute numbers this big, one would either have to lose precision or use bignums.