Exponentiation by squaring

From TCS Wiki
Revision as of 22:13, 8 March 2013 by imported>Addbot (Bot: 10 interwiki links moved, now provided by Wikidata on d:q864127)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Exponentiating by squaring is an algorithm. It is used for quickly working out large integer powers of a number. It is also known as the square-and-multiply algorithm or binary exponentiation. It implicitly uses the binary expansion of the exponent. It is of quite general use, for example in modular arithmetic. The algorithm has been known for a long time. It is already written down in a book called Chandah-sûtra. That book was published in India, around 200 BC.

Squaring algorithm

The following recursive algorithm computes xn for a positive integer n where n > 0:

[math]\displaystyle{ \mbox{Power}(x,\,n)= \begin{cases} x, & \mbox{if }n\mbox{ = 1} \\ \mbox{Power}(x^2,\,n/2), & \mbox{if }n\mbox{ is even} \\ x\times\mbox{Power}(x^2,\,(n-1)/2), & \mbox{if }n \gt \mbox{2 is odd} \end{cases} }[/math]

This algorithm is much faster than the ordinary method to compute such a value. Multipliying x by itself, n operations are needed to calculate x n. With the method shown above, only log2(n) operations are needed.

Template:Math-stub