Repeated Squaring

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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License