Hacker's Delight

11-3. Integer Exponentiation

Computing xⁿ by Binary Decomposition of n

A well-known technique for computing xⁿ, when n is a nonnegative integer, involves the binary representation of n. The technique applies to the evaluation of an expression of the form x • x • x • x • … • x where • is any associative operation, such as addition, multiplication including matrix multiplication, and string concatenation (as suggested by the notation (‘ab’)³ = ‘ababab’). As an example, suppose we wish to compute y = x¹³. Because 13 expressed in binary is 1101 (that is, 13 = 8 + 4 + 1),

Thus, x¹³ may be computed as follows:

This requires five multiplications, ...