Crate bare_metal_modulo

ModNum is a highly ergonomic modular arithmetic struct intended for no_std use.

ModNum objects represent a value modulo m. The value and modulo can be of any primitive integer type. Arithmetic operators include +, - (both unary and binary), *, and ==.

ModNum was originally developed to facilitate bidirectional navigation through fixed-size arrays at arbitrary starting points. This is facilitated by a double-ended iterator that traverses the entire ring starting at any desired value.

Note that ModNum is not designed to work with arbitrary-length integers, as it requires its integer type to implement the Copy trait.

For the 2020 Advent of Code (Day 13 part 2), I extended ModNum to solve systems of modular equations, provided that each modular equation is represented using signed integers. My implementation is based on this lucid explanation by Brent Yorgey.

Arithmetic Examples

Addition, subtraction, multiplication, and unary negation are all fully supported for both signed and unsigned integer types. Note that the right-hand side will be an integer of the corresponding type, rather than another ModNum. I have personally found this to be most convenient in practice.

use bare_metal_modulo::ModNum;
let mut m = ModNum::new(2, 5);
m += 2;
assert_eq!(m, ModNum::new(4, 5));
m += 2;
assert_eq!(m, ModNum::new(1, 5));
m -= 3;
assert_eq!(m, ModNum::new(3, 5));
m *= 2;
assert_eq!(m, ModNum::new(1, 5));
m *= 2;
assert_eq!(m, ModNum::new(2, 5));
m *= 2;
assert_eq!(m, ModNum::new(4, 5));
m *= 2;
assert_eq!(m, ModNum::new(3, 5));
m = -m;
assert_eq!(m, ModNum::new(2, 5));
assert_eq!(m.a(), 2);
assert_eq!(m.m(), 5);

The == operator can be used to compare two ModNums or a ModNum and an integer of the corresponding type. In both cases, it represents congruence rather than strict equality.

use bare_metal_modulo::ModNum;
let m = ModNum::new(2, 5);
assert!(m == 2);
assert!(m == 7);
assert!(m == -3);

Accessing Values

Each ModNum represents an integer a (mod m). To access these values, use the corresponding a() and m() methods. Note that a() will always return a fully reduced value, regardless of how it was initialized.

use bare_metal_modulo::ModNum;
let m = ModNum::new(7, 10);
assert_eq!(m.a(), 7);
assert_eq!(m.m(), 10);

let n = ModNum::new(23, 17);
assert_eq!(n.a(), 6);
assert_eq!(n.m(), 17);

let p = ModNum::new(-4, 3);
assert_eq!(p.a(), 2);
assert_eq!(p.m(), 3);

Iteration

I originally created ModNum to facilitate cyclic iteration through a fixed-size array from an arbitrary starting point in a no_std environment. Its double-ended iterator facilitates both forward and backward iteration.

use bare_metal_modulo::ModNum;

let forward: Vec<usize> = ModNum::new(2, 5).iter().map(|mn| mn.a()).collect();
assert_eq!(forward, vec![2, 3, 4, 0, 1]);

let reverse: Vec<usize> = ModNum::new(2, 5).iter().rev().map(|mn| mn.a()).collect();
assert_eq!(reverse, vec![1, 0, 4, 3, 2]);

For the 2020 Advent of Code (Day 13 part 2), I extended ModNum to solve systems of modular equations, provided that each modular equation is represented using signed integers. My implementation is based on this lucid explanation by Brent Yorgey.

The solver works directly with an iterator containing the ModNum objects corresponding to the modular equations to be solved, facilitating space-efficient solutions of a sequence coming from a stream. The examples below show two variants of the same system. The first example uses an iterator, and the second example retrieves the system from a Vec.

use bare_metal_modulo::ModNum;
let a_values = (2..=4);
let m_values = (5..).step_by(2);
let mut values = a_values.zip(m_values).map(|(a, m)| ModNum::new(a, m));
let solution = ModNum::<i128>::chinese_remainder_system(&mut values).unwrap();
assert_eq!(solution, 157);

let values = vec![ModNum::new(2, 5), ModNum::new(3, 7), ModNum::new(4, 9)];
let solution = ModNum::<i128>::chinese_remainder_system(&mut values.iter().copied()).unwrap();
assert_eq!(solution, 157);

Structs

ModNum	Represents an integer a (mod m)
ModNumIterator