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.

page revision: 5, last edited: 31 Mar 2008 02:48