One Algorithm, Infinite Powers

How the Russian peasant algorithm reveals the universal structure of exponentiation

The Algorithm

Russian peasants had a clever method for multiplication that doesn’t require memorizing times tables. To compute 23 x 17:

23    17
11    34     (halve, double)
 5    68
 2   136
 1   272
Copy

Add the right column wherever the left is odd: 17 + 34 + 68 + 272 = 391. That’s 23 x 17.

Why does this work? Because we’re really computing:

23 x 17 = (16 + 4 + 2 + 1) x 17 = 16x17 + 4x17 + 2x17 + 17
Copy

The algorithm only needs three operations on the multiplier:

• half(n) — integer division by 2
• even(n) — test if divisible by 2
• Addition on the result

From Multiplication to Exponentiation

Here’s the insight that makes this interesting: the same algorithm computes powers.

Replace “add to accumulator” with “multiply into accumulator” and “double the multiplicand” with “square the base”:

T power(T base, int exp) {
    T result = 1;
    while (exp > 0) {
        if (!even(exp)) result = result * base;
        base = base * base;
        exp = half(exp);
    }
    return result;
}
Copy

This is O(log n) multiplications instead of O(n). Computing 2^1000 takes about 10 multiplications, not 1000.

The Monoid Connection

The peasant algorithm works whenever you have:

1. An associative binary operation *
2. An identity element 1 where 1 * x = x * 1 = x

This structure is called a monoid. The algorithm computes x * x * ... * x (n times) using O(log n) operations.

What makes this powerful is that many things form monoids:

Examples in Code

Fibonacci via Matrix Exponentiation

The Fibonacci recurrence F(n) = F(n-1) + F(n-2) can be encoded as matrix multiplication:

[F(n+1)]   [1 1]^n   [1]
[F(n)  ] = [1 0]   x [0]
Copy

Computing F(1,000,000) takes about 20 matrix multiplications:

mat2 fib_matrix{1, 1, 1, 0};
mat2 result = power(fib_matrix, 1000000);
// result.b is F(1,000,000)
Copy

Quaternion Rotations

A rotation by angle theta around axis (x,y,z) is a unit quaternion. Composing rotations is quaternion multiplication. To rotate by theta x n:

auto rot = rotation_z(theta);
auto rot_n = power(rot, n);  // O(log n) multiplications
Copy

Shortest Paths via Tropical Semiring

In the tropical semiring, “addition” is min and “multiplication” is +. Matrix “multiplication” computes path lengths. Powers find multi-hop paths:

trop_matrix adj = /* adjacency matrix with edge weights */;
auto paths_k = power(adj, k);  // paths_k[i][j] = shortest k-hop path i->j
Copy

Compound Interest

An affine transformation f(x) = ax + b under composition:

(a1*x + b1) compose (a2*x + b2) = a1(a2*x + b2) + b1 = (a1*a2)x + (a1*b2 + b1)
Copy

Compound interest with rate r and deposit d is f(x) = (1+r)x + d. After n years:

affine yearly = {1.05, 100};  // 5% interest, $100 deposit
affine after_30_years = power(yearly, 30);
double final_balance = after_30_years(1000);  // Starting with $1000
Copy

The Minimal Interface

The implementation uses C++20 concepts to express exactly what’s needed:

template<typename T>
concept algebraic = requires(T a) {
    { zero(a) } -> convertible_to<T>;
    { one(a) } -> convertible_to<T>;
    { twice(a) } -> convertible_to<T>;
    { half(a) } -> convertible_to<T>;
    { even(a) } -> convertible_to<bool>;
    { a + a } -> convertible_to<T>;
};
Copy

Any type satisfying this concept works with power(). The examples demonstrate 15 different monoids, each with about 50 lines of code.

Why This Matters

Alex Stepanov’s key insight: algorithms arise from algebraic structure. The peasant algorithm isn’t really “about” integers or matrices—it’s about monoids. Once you see this, you find the same pattern everywhere.

This is generic programming: write the algorithm once, state its requirements precisely, and let it work on anything that satisfies those requirements.

Further Reading

• Stepanov & Rose, From Mathematics to Generic Programming
• Stepanov, Elements of Programming