# Fast exp() operator 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` `a`s 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));``````