Repeated Squaring
Repeated squaring is a technique used to evaluate the 
term of a sequence in O(log N) time. It relies on an efficient method to compute 
from 
and 
, for example, multiplying 
and 
.
The Algorithm
Suppose we have a fast way to compute from and . Then, we can start by computing 
, and computing 
for each 
by combining 
and . Then, keeping track of a global 
starting at 
, we add 
to 
if and only if the bit of 
is set. So, for example, if 
, we add 
and 
, but not 
.
Example: Raising a number to a power
Suppose we want to find 
efficiently. Multiplying 3 by itself 104 times is very inefficient. So instead we start the squaring. 
.
|
|
kth bit in N | |
|
| 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 
. 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: 1206931739|%e %b %Y, %H:%M %Z (%O ago)
