Crate bare_metal_modulo

Overview

The bare_metal_modulo crate includes two structs:

• ModNum is a highly ergonomic modular arithmetic struct intended for no_std use.
• ModNumIterator is a double-ended iterator that starts with the ModNum upon which it is invoked, making a complete traversal of the elements in that ModNum's ring.

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.

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);

Arithmetic

Addition, subtraction, multiplication, and exponentiation 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 for three reasons:

1. As the second operand is not a ModNum, there is no need to check to ensure that their modulo components match. The user ensures that the operand value makes sense in context.
2. In code I have written, I find that the operand value emerges from a context in which ModNum structs are irrelevant.
3. If the desired operand is another ModNum, it is ergonomic to call .a() to obtain the operand.

Unary negation is supported for both signed and unsigned integers. Multiplicative inverse (using the inverse() method) is supported for signed integers only.

use bare_metal_modulo::ModNum;
use num::traits::Pow;

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);

assert_eq!(m.pow(2), ModNum::new(4, 5));
assert_eq!(m.pow(3), ModNum::new(3, 5));
assert_eq!(m.pow(4), ModNum::new(1, 5));
assert_eq!(m.pow(5), ModNum::new(2, 5));
assert_eq!(m.pow(6), ModNum::new(4, 5));

let i = m.inverse().unwrap();
assert_eq!(m * i.a(), 1);

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);
assert!(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]);

Solving Modular Equations with the Chinese Remainder Theorem

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.

Note that the solution value can rapidly become large, as shown in the third example. I recommend using i128, so as to maximize the set of solvable equations given this library's constraint of using Copy integers only. While the solution to the third example is representable as an i64, some of the intermediate multiplications will overflow unless i128 is used.

use bare_metal_modulo::ModNum;

let mut values = (2..).zip((5..).step_by(2)).map(|(a, m)| ModNum::new(a, m)).take(3);
let solution = ModNum::<i128>::chinese_remainder_system(&mut values);
assert_eq!(solution.unwrap().a(), 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());
assert_eq!(solution.unwrap().a(), 157);

let mut values = [(0, 23), (28, 41), (20, 37), (398, 421), (11, 17), (15, 19), (6, 29),
   (433, 487), (11, 13), (5, 137), (19, 49)]
   .iter().copied().map(|(a, m)| ModNum::new(a, m));
let solution = ModNum::<i128>::chinese_remainder_system(&mut values);
assert_eq!(solution.unwrap().a(), 762009420388013796);

Structs

ModNum	Represents an integer a (mod m)
ModNumIterator	A double-ended iterator that starts with the ModNum upon which it is invoked, making a complete traversal of the elements in that ModNum's ring.