power of element

Semigroup

Let be a semigroup which has no identity element and .

For , the n-th power of (under ) is defined as:

That is

¹

Monoid

Let be a monoid whose identity element is . Let and .

The definition of of a semigroup can be extended to allow an exponent of 0:

¹

Implementation

By implementing the idea behind Egyptian multiplication and exponentiating by squaring, we can implement a generic power function for any semigroups.

This implementation uses two loops for efficiency reason. Check Egyptian multiplication for more information

fn power_accumulate_semigroup<A>(mut r: A, mut a: A, mut n: impl Integer, op: (A, A) -> A) -> A {
    // precondition(n >= 0);
    if (n == 0) return r;
    while (true) {
        if (is_odd(n)) {
            r = op(r, a);
            if (n == 1) return r;
        }
        n = n / 2;
        a = op(a, a);
    }
}
 
fn power_semigroup<A>(mut a: A, mut n: impl Integer, op: (A, A) -> A) -> A
where is_semigroup(A, op)
{
    assert(n > 0);
    while (!is_odd(n)) {
        a = op(a, a);
        n = n / 2;
    }
    if (n == 1) { 
        return a 
    } else {
        return power_accumulate_semigroup(a, op(a, a), half(n - 1), op)
    }
}

²

We can also extend the above code to monoid by check for zero:

fn power_monoid<A>(a: A, n: impl Integer, op: impl MonoidOperation<A>) -> A
where is_monoid(A, op)
{
    assert(n >= 0);
    if (n == 0) { op.identity() } else { power_semigroup(a, n, op) }
}

²

One implementation of power of monoid is to compute any linear recurrence functions. For example, Fibonacci numbers ²

fn fib(u32: n) -> isize
{
    let mat = Mat2::new(1, 1, 1, 0);
    let result = power_monoid(mat, n, Mat2::mult)
    result[1][0]
}

Footnotes

1. Definition:Power of Element - ProofWiki ↩ ↩²

2. From Mathematics to Generic Programming chapter 7 ↩ ↩² ↩³