Fast exp() for Monoids


Today I learned that the fast-exponentiation in SICP 1.2.4 can be applied to all monoids as well.

Monoid

Definition: set S and operation ⊕ : S -> S -> S forms a Monoid if they satisfy:

  • Associativity: (x ⊕ y) ⊕ z === x ⊕ (y ⊕ z) for x, y, z in S .
  • Identity element, or Unit: I such that x ⊕ I === x === I ⊕ x exists.

Example of Monoid: Plus

We can see that the set of all real numbers, R, and a ⊕ b := a + b forms a Monoid, where I = 0.

More examples of Monoid

  • R, and a ⊕ b := a * b forms a Monoid, where I = 1.
  • When N is an integer, Set of all integers Z, and a ⊕ b := (a + b) mod N forms a Monoid, where I = 0.

“Multiplication” of Monoid

If we consider to be a general form of plus, we can define a general form of multiply, denoted by operator :

  • Let k be k a non-negative integer
  • a ⊗ 0 := I when k == 0
  • a ⊗ k := a ⊕ (a ⊗ (k-1)) when k > 0

This makes a ⊗ k := a ⊕ a ⊕ a ⊕ a ⊕ a ⊕ a ⊕ a ⊕ a ⊕ a ... where the right hand side is k as concatencated by .

  • When a ⊕ b is a + b, becomes *.
  • When a ⊕ b is a * b, becomes **.
  • When a ⊕ b is (a + b) % N, a ⊗ b becomes (a * b) % N.

a ⊗ k can be computed in O(ln2 k)

Let binary representation of k be B(m) B(m-1) ... B(0) where B0 is the LSB. We can rewrite a ⊗ k to be:

a ⊗ k := (a ⊗ (2**B(m))) ⊕ (a ⊗ (2**B(m-1))) ⊕ ... ⊕ (a ⊗ (2**B(0)))

If has O(1), a ⊗ k can be computing in O(ln2 k). The key idea is to reuse a ⊗ (2**B(m-1)) when computing a ⊗ (2**B(m)), with dynamic-programming.

Computing * in this way is not quite fruitful: we know that processor can compute a * b in O(1).

However things are different in the case of a * b and (a + b) % N. Applying our fast- method to them can save both time and space.

Code

function fastMul<T>(id: T, mplus: (op1: T, op2: T) => T, a: T, k: number): T {
    if (~~k !== k || k < 0)
        throw new Error('exp must be positive integer');

    let ans = id;

    while (k > 0) {
        if (k % 2 == 1) {
            ans = mplus(ans, a);
            k--;
        } else {
            a = mplus(a, a);
            k /= 2;
        }
    }

    return ans;
}

// 2**5
console.log(fastMul(1, (a, b) => a * b, 2, 5));

// (887 * 885) % 12
console.log(fastMul(0, (a, b) => (a % 12 + b % 12) % 12, 887, 885));