alga2 0.1.0

A modern abstract-algebra hierarchy for Rust — the successor to alga, powered by batch-impl
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

//! Integer powers in a monoid.
//!
//! Any monoid supports `aⁿ` by square-and-multiply — the default
//! implementation here runs in `O(log n)` combines and needs only the
//! monoid structure.

use crate::op::Operator;

use super::{Magma, Monoid};

/// Integer powers in a [`Monoid`] via square-and-multiply.
pub trait Power<Op: Operator>: Monoid<Op> + Clone {
    /// `selfⁿ` (`n == 0` yields the identity).
    fn pow(&self, n: u32) -> Self {
        let mut acc = Self::identity();
        let mut base = self.clone();
        let mut e = n;
        while e > 0 {
            if e & 1 == 1 {
                acc = <Self as Magma<Op>>::combine(&acc, &base);
            }
            base = <Self as Magma<Op>>::combine(&base, &base);
            e >>= 1;
        }
        acc
    }
}