aoc/util/
math.rs

1//! Extended mathematical operations.
2//!
3//! * [Greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of 2 numbers using
4//!   the [Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm).
5//!
6//! * [Least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple)
7//!
8//! * [Modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation). Calculates bᵉ mod
9//!   m efficiently using [exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring).
10use crate::util::integer::*;
11
12pub trait MathOps<T: Integer> {
13    #[must_use]
14    fn gcd(self, b: T) -> T;
15    #[must_use]
16    fn lcm(self, b: T) -> T;
17    #[must_use]
18    fn mod_pow(self, e: T, m: T) -> T;
19}
20
21impl<T: Integer> MathOps<T> for T {
22    /// Greatest common divisor.
23    #[inline]
24    fn gcd(self, mut b: T) -> T {
25        let mut a = self;
26
27        while b != T::ZERO {
28            (a, b) = (b, a % b);
29        }
30
31        a
32    }
33
34    /// Least common multiple.
35    #[inline]
36    fn lcm(self, b: T) -> T {
37        self * (b / self.gcd(b))
38    }
39
40    /// Modular exponentiation.
41    #[inline]
42    fn mod_pow(self, mut e: T, m: T) -> T {
43        let mut base = self;
44        let mut result = T::ONE;
45
46        while e > T::ZERO {
47            if e & T::ONE == T::ONE {
48                result = (result * base) % m;
49            }
50            base = (base * base) % m;
51            e = e >> 1;
52        }
53
54        result
55    }
56}
aoc/util/math.rs

aoc/util/
math.rs
