Crate bare_metal_modulo

source ·
Expand description

Overview

The bare_metal_modulo crate includes the following structs:

  • ModNum is a highly ergonomic modular arithmetic struct intended for no_std use.
  • ModNumC is similar to ModNum, but uses const generics to specify the modulo.
  • ModNumIterator is a double-ended iterator that starts with the ModNum or ModNumC upon which it is invoked, making a complete traversal of the elements in that object’s ring.
  • WrapCountNum is similar to ModNum, but additionally tracks the amount of “wraparound” that produced the modulo value. WrapCountNumC corresponds to ModNumC.
  • OffsetNum is similar to ModNum, but instead of a zero-based range, it can start at any integer value. OffsetNumC corresponds to ModNumC.

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), *, /, pow(), ==, <, >, <=, >=, and !=. Additional capabilities include computing multiplicative inverses and solving modular equations. Division, multiplicative inverse, and solving modular equations are only defined for signed types.

ModNumC objects likewise represent a value modulo M, where M is a generic constant of the usize type. ModNumC objects support the same arithmetic operators as ModNum objects.

Modular numbers represent the remainder of an integer when divided by the modulo. If we also store the quotient in addition to the remainder, we have a count of the number of times a value had to “wrap around” during the calculation.

For example, if we start with 8 (mod 17) and add 42, the result is 16 (mod 17) with a wraparound of 2.

WrapCountNum/WrapCountNumC objects store this wraparound value and make it available. They only support subtraction and iteration with Signed values such as isize and i64.

This library 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. The iterator supports ModNum, ModNumC, OffsetNum, and OffsetNumC. It also supports WrapCountNum and WrapCountNumC for signed values only.

Note that ModNum, ModNumC, WrapCountNum, WrapCountNumC, OffsetNum, and OffsetNumC are not designed to work with arbitrary-length integers, as they require their 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/ModNumC/WrapCountNum/WrapCountNumC 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.

Each WrapCountNum/WrapCountNumC tracks accumulated wraparounds. Use the .wraps() method to access this tracked count.

 use bare_metal_modulo::*;

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

 let f = format!("{}", p);
 assert_eq!(f, "2 (mod 3)");

 // ModNumC variables indicate the modulo using a type annotation.
 let q: ModNumC<i32, 17> = ModNumC::new(23);
 assert_eq!(q, 6);

 // Create a new ModNum with the same modulo as an existing one.
 let r = p.with(8);
 assert_eq!(r.a(), 2);
 assert_eq!(r.m(), 3);

 let s = q.with(35);
 assert_eq!(s.a(), 1);
 assert_eq!(s.m(), 17);

 // Replace the value of the ModNum with a new value while keeping the modulo.
 let mut t = ModNum::new(3, 5);
 t.replace(12);
 assert_eq!(t.a(), 2);

 let mut v: ModNumC<usize,5> = ModNumC::new(3);
 v.replace(12);
 assert_eq!(v.a(), 2);

Arithmetic

Addition, subtraction, and multiplication are all fully supported for both signed and unsigned integer types. The right-hand side may either be an integer of the corresponding type or another ModNum/ModNumC object.

Unary negation and subtraction are supported for both signed and unsigned integers.

use bare_metal_modulo::*;

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 + ModNum::new(4, 5), ModNum::new(1, 5));
m += ModNum::new(4, 5);
assert_eq!(m, ModNum::new(1, 5));

assert_eq!(m - ModNum::new(4, 5), ModNum::new(2, 5));
m -= ModNum::new(4, 5);
assert_eq!(m, ModNum::new(2, 5));

assert_eq!(m * ModNum::new(3, 5), ModNum::new(1, 5));
m *= ModNum::new(3, 5);
assert_eq!(m, ModNum::new(1, 5));

let mut m: ModNumC<isize,5> = ModNumC::new(2);
m *= 3;
assert_eq!(m, ModNumC::new(1));

m += 1;
assert_eq!(m, ModNumC::new(2));

m += 3;
assert_eq!(m, ModNumC::new(0));

let m: ModNumC<isize,5> = ModNumC::default();
assert_eq!(m, ModNumC::new(0));

Saturating addition and subtraction are often useful relative to the modulus, so the num::traits::SaturatingAdd and num::traits::SaturatingSub traits are implemented as well for ModNum and ModNumC.

use bare_metal_modulo::*;
use num::traits::SaturatingAdd;
use num::traits::SaturatingSub;

let m = ModNum::new(2, 5);
assert_eq!(m.saturating_add(&ModNum::new(1, 5)), ModNum::new(3, 5));
assert_eq!(m.saturating_add(&ModNum::new(2, 5)), ModNum::new(4, 5));
assert_eq!(m.saturating_add(&ModNum::new(3, 5)), ModNum::new(4, 5));
assert_eq!(m.saturating_sub(&ModNum::new(1, 5)), ModNum::new(1, 5));
assert_eq!(m.saturating_sub(&ModNum::new(2, 5)), ModNum::new(0, 5));
assert_eq!(m.saturating_sub(&ModNum::new(3, 5)), ModNum::new(0, 5));

let m: ModNumC<i32, 5> = ModNumC::new(2);
assert_eq!(m.saturating_add(&ModNumC::new(1)), ModNumC::new(3));
assert_eq!(m.saturating_add(&ModNumC::new(2)), ModNumC::new(4));
assert_eq!(m.saturating_add(&ModNumC::new(3)), ModNumC::new(4));
assert_eq!(m.saturating_sub(&ModNumC::new(1)), ModNumC::new(1));
assert_eq!(m.saturating_sub(&ModNumC::new(2)), ModNumC::new(0));
assert_eq!(m.saturating_sub(&ModNumC::new(3)), ModNumC::new(0));

Multiplicative inverse (using the .inverse() method) is supported for signed integers only. As inverses are only defined when a and m are relatively prime, .inverse() will return None when it is not possible to calculate.

Division is defined in terms of the multiplicative inverse, so it is likewise only supported for signed integers, and will return None when the quotient does not exist. Assigned division (/=) will panic if the quotient does not exist.

The .pow() method is fully supported for unsigned integer types. It also works for signed integer types, but it will panic if given a negative exponent. If negative exponents are possible, use .pow_signed(), which will return None if the result does not exist.

use bare_metal_modulo::*;
use num::traits::Pow;

let m = ModNum::new(2, 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));

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

// Note: Very different result from m.pow(6)!
assert_eq!(m.pow(ModNum::new(6, 5)), ModNum::new(2, 5));

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

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

let m = ModNum::new(6, 11);
assert_eq!((m / 2).unwrap().a(), 3);
assert_eq!((m / 4).unwrap().a(), 7);
assert_eq!((m / 5).unwrap().a(), 10);
assert_eq!((m / 6).unwrap().a(), 1);
assert_eq!((m / 8).unwrap().a(), 9);
assert_eq!(m / 0, None);

assert_eq!((m / ModNum::new(2, 11)).unwrap(), ModNum::new(3, 11));
assert_eq!((m / ModNum::new(4, 11)).unwrap(), ModNum::new(7, 11));

let m: ModNumC<i32,5> = ModNumC::new(2);

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

assert_eq!(m.pow(2), ModNumC::new(4));
assert_eq!(m.pow(3), ModNumC::new(3));
assert_eq!(m.pow_signed(-2).unwrap(), ModNumC::new(4));
assert_eq!(m.pow_signed(-3).unwrap(), ModNumC::new(2));

let m: ModNumC<i32, 11> = ModNumC::new(6);
assert_eq!((m / 2).unwrap().a(), 3);
assert_eq!((m / 4).unwrap().a(), 7);
assert_eq!(m / 0, None);

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

Inequalities are also defined over those same sets.

 use bare_metal_modulo::*;

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

 assert_eq!(m, ModNum::new(2, 5));
 assert_eq!(m, ModNum::new(7, 5));
 assert_eq!(m, ModNum::new(-3, 5));

 assert!(m < 4);
 assert!(m < 8);
 assert!(m > 1);

 let n = ModNum::new(6, 5);
 assert!(m > n);
 assert!(n < 2);
 assert!(n > 0);

 let m: ModNumC<i32,5> = ModNumC::new(2);
 assert!(m == 2);
 assert!(m == 7);
 assert!(m == -3);
 assert!(m != 3);

 assert!(m < 4);
 assert!(m < 8);
 assert!(m > 1);

 let n: ModNumC<i32,5> = ModNumC::new(6);
 assert!(m > n);
 assert!(n < 2);
 assert!(n > 0);

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::*;

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

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

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

Counting Wraps

Modular numbers represent the remainder of an integer when divided by the modulo. If we also store the quotient in addition to the remainder, we have a count of the number of times a value had to “wrap around” during the calculation.

For example, if we start with 8 (mod 17) and add 42, the result is 16 (mod 17) with a wraparound of 2.

WrapCountNum objects store this wraparound value and make it available. It is tracked through both += and *= for all supported numeric types.

use bare_metal_modulo::*;

let mut value = WrapCountNum::new(8, 17);
value += 42;
assert_eq!(value, 16);
assert_eq!(value.wraps(), 2);

value += 18;
assert_eq!(value, 0);
assert_eq!(value.wraps(), 4);

value += 11;
assert_eq!(value, 11);
assert_eq!(value.wraps(), 4);

value *= 5;
assert_eq!(value, 4);
assert_eq!(value.wraps(), 7);

Because regular operations produce a new WordCountNum value every time, value = value + x only tracks wraps for a single operation, unlike value += x.

use bare_metal_modulo::*;
use num::traits::Pow;

let mut value = WrapCountNum::new(8, 17);
value = value + 42;
assert_eq!(value, 16);
assert_eq!(value.wraps(), 2);

value = value + 18;
assert_eq!(value, 0);
assert_eq!(value.wraps(), 2);

value = value + 11;
assert_eq!(value, 11);
assert_eq!(value.wraps(), 0);

value = value * 5;
assert_eq!(value, 4);
assert_eq!(value.wraps(), 3);

value = value.pow(3);
assert_eq!(value, 13);
assert_eq!(value.wraps(), 3);

The .pow_assign() method enables wrap tracking when exponentiating.

use bare_metal_modulo::*;

let mut value = WrapCountNum::new(4, 17);
value.pow_assign(3);
assert_eq!(value, 13);
assert_eq!(value.wraps(), 3);

value += 6;
assert_eq!(value, 2);
assert_eq!(value.wraps(), 4);

value.pow_assign(5);
assert_eq!(value, 15);
assert_eq!(value.wraps(), 5);

Subtraction causes the wrap count to decrease. To simplify the implementation, WrapCountNum only defines subtraction on Signed numerical types.

use bare_metal_modulo::*;

let mut value = WrapCountNum::new(2, 5);
value -= 8;
assert_eq!(value, 4);
assert_eq!(value.wraps(), -2);

value -= 3;
assert_eq!(value, 1);
assert_eq!(value.wraps(), -2);

value -= 13;
assert_eq!(value, 3);
assert_eq!(value.wraps(), -5);

value += 8;
assert_eq!(value, 1);
assert_eq!(value.wraps(), -3);

There is a const generic version as well, WrapCountNumC:

use bare_metal_modulo::*;

let mut value = WrapCountNumC::<isize,17>::new(8);
value += 42;
assert_eq!(value, 16);
assert_eq!(value.wraps(), 2);

value += 18;
assert_eq!(value, 0);
assert_eq!(value.wraps(), 4);

value += 11;
assert_eq!(value, 11);
assert_eq!(value.wraps(), 4);

value *= 5;
assert_eq!(value, 4);
assert_eq!(value.wraps(), 7);

let mut value = WrapCountNumC::<isize, 8>::default();
value += 15;
assert_eq!(value, 7);
assert_eq!(value.wraps(), 1);

Hash/BTree keys

ModNum and ModNumC objects implement the Ord and Hash traits, and therefore can be included in HashSet and BTreeSet collections and serve as keys for HashMap and BTreeMap dictionaries.

use bare_metal_modulo::*;
use std::collections::HashSet;

let m1: ModNumC<usize, 3> = ModNumC::new(2);
let m2: ModNumC<usize, 3> = ModNumC::new(4);
let m3: ModNumC<usize, 3> = ModNumC::new(5);
assert_eq!(m1, m3);
assert_eq!(m1 + 2, m2);

let mut set = HashSet::new();
set.insert(m1);
set.insert(m2);
assert_eq!(set.len(), 2);
for m in [m1, m2, m3].iter() {
    assert!(set.contains(m));
}

Modular ranges rooted elsewhere than zero

Occasionally of use is the ability to represent a modular range of values starting elsewhere than zero. To address this situation, OffsetNum and OffsetNumC are provided. Both support addition, subtraction, and iteration in a manner similar to the other types.

OffsetNum objects can be created directly or from a RangeInclusive:

use bare_metal_modulo::*;

let mut off = OffsetNum::<usize>::from(1..=10);
assert_eq!(off.a(), 1);
assert_eq!(off, 1);
assert_eq!(off, 11); // Congruence equality with basic integer type
assert_eq!(off.min_max(), (1, 10));

for i in 1..=10 {
    assert_eq!(off.a(), i);    
    off += 1;
}
assert_eq!(off.a(), 1);

for (i, n) in off.iter().enumerate() {
    assert_eq!(n.a(), i + 1);
}

off -= 1;
for i in (1..=10).rev() {
    assert_eq!(off.a(), i);
    off -= 1;
}
assert_eq!(off.a(), 10);

Negative offsets are fine:

use bare_metal_modulo::*;

let mut off = OffsetNum::<isize>::new(-4, 3, -6);
assert_eq!(off.a(), -4);
off += 1;
assert_eq!(off.a(), -6);

Subtraction is subtle for OffsetNum. The subtrahend is normalized to the size of the OffsetNum’s range, but zero-based. It is then subtracted from the modulus and added to the minuend.

use bare_metal_modulo::*;

let mut off = OffsetNum::<usize>::from(3..=6);
assert_eq!((off - 1).a(), 6);
assert_eq!((off - 2).a(), 5);
assert_eq!((off - 3).a(), 4);
assert_eq!((off - 4).a(), 3);

off += 3;
assert_eq!((off - 1).a(), 5);
assert_eq!((off - 2).a(), 4);
assert_eq!((off - 3).a(), 3);
assert_eq!((off - 4).a(), 6);

OffsetNumC has three generic parameters:

  • Underlying integer type
  • Number of values in the range
  • Starting offset for the range
use bare_metal_modulo::*;

let mut off = OffsetNumC::<i16, 7, 5>::new(5);
assert_eq!(off.a(), 5);
assert_eq!(off.min_max(), (5, 11));

for i in 0..7 {
    assert_eq!(off.a(), 5 + i);
    off += 1;
}
assert_eq!(off.a(), 5);

let off_at_start = OffsetNumC::<i16, 7, 5>::default();
assert_eq!(off_at_start, off);

for (i, n) in off.iter().enumerate() {
    assert_eq!(i + 5, n.a() as usize);
}

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 crate’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::*;

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(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(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(values);
assert_eq!(solution.unwrap().a(), 762009420388013796);

Structs

ModNum
Represents an integer a (mod m)
ModNumC
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.
OffsetNum
OffsetNumC
WrapCountNum
Represents an integer a (mod M)
WrapCountNumC

Traits

MNum
NumType