Halving an exponent is useful only if the meaning is preserved
To compute , multiplying thirteen copies is wasteful: the same squares can be reused. Yet an implementation with an accumulator and a changing base can be difficult to read. Why can one multiply into the answer when a bit is 1, square the base, and discard that bit? A loop invariant makes the relationship precise.
The argument works for more than ordinary numbers. It applies to matrices and other associative operations, including operations whose inputs cannot generally be exchanged. That gives one small algorithm several useful roles in competitive programming.
Specify the operation before specifying the loop
Definition 11.1.1
(A monoid and its nonnegative powers)
Let be a set with a closed associative operation and a two-sided identity . Thus , , and . Such a structure is called a monoid.
For , define and for integers . Associativity implies
These identities follow by grouping repeated copies of the same element; they do not require arbitrary elements of S to commute.
Examples include integers with multiplication and identity 1, residues modulo a positive integer with modular multiplication, and square matrices of a fixed dimension with matrix multiplication and identity matrix. The operation used below is exact. Floating-point multiplication is only approximately associative, so its evaluations inherit rounding issues that the exact algebraic proof does not remove.
The exponent contract is a nonnegative integer. Negative powers require an inverse of a, which need not exist in a monoid, and are outside this algorithm's input domain. An implementation must not attempt to process a negative exponent with the halving loop.
Read the binary digits from right to left
The least significant binary digit of a nonnegative integer e is
e % 2, and e // 2 removes it. The successive powers needed are
, obtained by squaring. A 1 digit says to
include the current power in the accumulator.
BINARY_POWER(a, n, combine, I):
require n is a nonnegative integer
result = I
power = a
e = n
while e > 0:
if e % 2 == 1:
result = combine(result, power)
e = e // 2
if e > 0:
power = combine(power, power)
return result
The final square is skipped because there is no remaining bit to process.
combine implements , and its inputs and result are values in
the specified monoid. For matrices, it performs matrix multiplication;
it does not multiply corresponding entries independently.
Theorem 11.1.2
(The algorithm returns the specified monoid power)
For every allowed , BINARY_POWER terminates and returns .
At each loop entry its central invariant is
Proof
(One binary digit changes the representation, not the target)
Initially the invariant is . Suppose first that the current exponent is . The accumulator is unchanged; after halving and squaring, the represented value is .
If , first replace the accumulator by . Halving and squaring then represent . Only associativity and the identities for powers of one element were used.
The positive exponent strictly decreases under integer halving. On the
last iteration it is 1, so the accumulator absorbs the final power and
the exponent becomes 0. Skipping that last square is harmless because
every possible next power raised to 0 is I. The invariant therefore
gives result equal to at termination. For , the loop is
never entered and returns I directly.
Proof X-ray
Where associativity enters, and why order is safe
The key move is the choice of invariant: rather than tracking the accumulator alone, it tracks the pair of the accumulator and the remaining power, so that moving one factor from the pair into result leaves the product unchanged. Associativity is used twice: to regroup into , and to justify . Commutativity is never used, because every multiplication puts result on the left and a power of one element on the right, and powers of one element commute with each other. The argument closes because is a nonnegative integer that strictly decreases, and at the remaining factor is .
The hypothesis that cannot be dropped is associativity.
Counterexample mode
Without associativity the invariant fails
Let with an identity and the remaining products , , , . This operation is not associative: , but . Define , which is . The algorithm on , sets result , squares to power , and then sets result . It returns , not . The repair is the hypothesis of the definition: the operation must be associative, which is why the algorithm applies to matrices and residues but not to arbitrary operations.
Count the operations that the code actually performs
For , let be its bit length,
and let be its number of 1 bits.
There are exactly L loop iterations, one accumulator multiplication
per 1 bit, and one square after every iteration except the last. Thus
the number of calls to combine is exactly
For , there are zero calls. A version that squares unconditionally at the end of each iteration performs one extra unnecessary operation; its exact count is different even though its answer is the same.
This is an arithmetic-operation count, not a universal bit-time bound.
The cost of combine depends on its operands. For fixed-size d-by-d
matrices, the ordinary multiplication method costs scalar
operations, giving scalar operations for positive n.
Exact integer entries may grow, so those scalar operations need not
have constant bit cost.
Modular powers: reduce the operation and the identity
For a positive modulus m, use residues in ,
combine(x,y) = (x*y) mod m, base a mod m, and identity 1 mod m.
Reducing after each multiplication is valid because congruence is
preserved by multiplication.
When , the sole residue is 0. In particular, even exponent zero
must return 1 mod 1 = 0, not the unnormalized integer 1. Modulus
zero is outside the operation's definition. For integer multiplication,
the algorithm treats as the empty product 1; this explicit
discrete convention is not a statement about indeterminate limits.
Residue reduction bounds stored values, but the intermediate product can still approach . Exact big integers or a correctly sized/safe modular multiplication routine are needed to preserve the mathematical operation. An overflowing fixed-width product is not repaired by reducing its already corrupted value afterward.
Worked example 11.1.3
(Compute 3 to the power 13 modulo 17)
The binary expansion is . Read the bits 1,0,1,1 from right to left. The table records the current loop-entry values and the accumulator after that iteration's bit is processed:
| e at entry | Bit | Current power | Result at entry | Result after bit |
|---|---|---|---|---|
| 13 | 1 | 3 | 1 | 3 |
| 6 | 0 | 9 | 3 | 3 |
| 3 | 1 | 13 | 3 | 5 |
| 1 | 1 | 16 | 5 | 12 |
The squares are , and . The accumulator products are , and . Hence . There are three squares and three accumulator products, agreeing with .
Worked example 11.1.4
(The smallest exponents and modulus one)
For the loop is not entered, so result is returned with zero calls; for the loop runs once, result , and no square is taken, so there is one call, in agreement with . Modulo every residue is , so : the call returns , and every product is as well. A routine that returns the literal integer for exponent zero is wrong here.
Encode a recurrence as a fixed linear transition
Define Fibonacci numbers by , and . Put
One matrix application advances the column state by one step. Induction therefore gives
The starting vector matters: pairing a different state convention with the same output index can introduce a one-step error. Exponent zero uses the identity matrix and recovers .
For example , whose first column is . Binary exponentiation computes this matrix using a logarithmic number of matrix multiplications. Computing exact Fibonacci numbers still has growing integer costs: has bits. The output itself prevents interpreting the matrix-operation bound as an bit-time algorithm. If only a residue is requested, perform the matrix arithmetic modulo m.
Worked example 11.1.5
(Fibonacci matrix power by binary steps)
To compute with : at the bit is 1, so result ; the exponent becomes and power . At the bit is 0, so result is unchanged; the exponent becomes and power . At the bit is 1, so result , and the exponent becomes without a final square. The two accumulator products and two squares total matrix multiplications. The first column gives .
Common mistake
(Starting the matrix accumulator at zero)
For matrix powers result must start at the identity matrix, not the zero matrix. With the zero matrix, combine(result, power) stays zero for every exponent, so even would be reported as the zero matrix. For exponent zero the answer must be the identity matrix, matching .
Common mistake
(Returning the wrong coordinate of the state vector)
The state is , whose first entry is . For the first coordinate of is , not .
Adjacency powers count walks of exactly the chosen length
Let A be the adjacency matrix of a finite directed graph, with equal to the number of edges from u to v. Rows denote start vertices and columns denote end vertices. Loops and parallel edges are allowed; distinct choices of edges count as distinct walks.
Theorem 11.1.6
(The walk-count interpretation)
For every integer , is the number of walks from u to v using exactly k edges. Walks may repeat vertices and edges.
Proof
(Split a walk at its final edge)
For , the identity matrix records one empty walk from a vertex to itself and none between different vertices. Assume the claim for k. Every length- walk from u to v has one unique penultimate vertex w. Choose a length-k walk from u to w, then an edge from w to v. There are choices. Summing over w counts every walk exactly once, which is the matrix product .
Worked example 11.1.7
(A loop and a directed three-cycle)
On vertices 0,1,2, take edges , , , . Then
The entry counts the walks and . It is not a shortest-path distance. The matrix keeps the length fixed and counts all choices, including repetitions.
Counterexample mode
A zero modular count does not prove absence
Suppose a directed diamond has edges , , , . There are two length-two walks from s to t. Modulo 2, their count is 0, but the walks still exist. Reducing walk counts modulo a number preserves residues, not the truth of a zero-versus-nonzero reachability test.
Nor does an exact count at length k describe all shorter walks. With only one edge and no other edges, the length-two count from u to v is 0 although a length-one walk exists. State whether a problem asks for exactly k edges, at most k edges, or a shortest path before choosing a matrix formulation.
Solved exercises
Exercise 11.1.8
(Compute using binary powers and count the calls to combine in the given algorithm. State what the algorithm returns for exponent zero modulo 13 and modulo 1, and whether a negative exponent is an allowed input.)
Core
Solution(4)
- 1
List the repeated squares
Since , the needed powers are . Modulo 13 they are , , and .
- 2
Multiply the powers for the 1 bits
Because: The bits of 11 that equal 1 correspond to the exponents 1, 2 and 8.
- 3
Count the calls to combine
Key step
There are three 1 bits and four bits in total, so the count is : three accumulator products and three squares.
- 4
State the boundary cases
. Exponent zero returns the monoid identity, which is modulo 13 and modulo 1. Negative exponents are outside the stated contract; they would need an invertible base and a separate treatment.
Exercise 11.1.9
(For the matrices and below, compute and , find , and explain why does not invalidate binary exponentiation.)
Core
Solution(3)
- 1
Compute both products
- 2
Find the pattern of powers of P
Hence for , and .
Because: adds the upper-left entry to the upper-right entry, and starts the induction.
- 3
Explain why noncommutativity is harmless
The powering proof groups copies of the same using associativity; it never exchanges two arbitrary input matrices. Noncommutativity therefore does not contradict its invariant.
Exercise 11.1.10
(For the stated Fibonacci transition, use the matrix power below to find . Which column-state vector does this power produce from ? Count the algorithm's matrix multiplications for exponent 10.)
Core
Solution(3)
- 1
Apply the power to the starting column
- 2
Read the correct coordinate
Key step
The second coordinate is ; returning the first coordinate would give the next Fibonacci number.
- 3
Count the multiplications
Since has two 1 bits and four bits in total, the algorithm uses matrix multiplications.
Exercise 11.1.11
(For the three-vertex worked graph, explain and . List the length-three walks counted by . If this entry is computed modulo 2 and becomes zero, may we conclude that no such walk exists?)
Core
Solution(3)
- 1
Interpret the identity entries
is the identity matrix, so and : one empty walk from 0 to itself, none from 0 to 1.
- 2
List the walks of length three from 0 to 0
The walks are and , so .
- 3
Interpret the zero modulo 2
The count becomes modulo 2. That zero is a residue of a positive count and supplies no absence certificate. The algorithm has answered the modular counting question correctly; the proposed reachability conclusion asks it for information that was discarded by reduction.