Repeated squaring, or repeated doubling is an algorithm that computes integer powers of a number quickly. The general problem is to compute xy for an arbitrary integer y. The naive method, doing y multiplications of x, is very slow. It can be sped up by repeatedly squaring x until the current power of x exceeds y, and then collecting the "useful" powers.
[edit] Example
So, which powers of x are useful? Consider the concrete example of computing 313. The binary representation of 13 is (1101)2, so 8 + 4 + 1 = 13.
| 31 | 3 |
| 32 |  |
| 34 |  |
| 38 |  |
Notice that each result is the square of the previous result, and hence can be computed in one multiplication.
Read full article from Repeated Squaring - Algorithmist
No comments:
Post a Comment