Crate bare_metal_modulo[−][src]
Expand description
Overview
The bare_metal_modulo crate includes two structs:
ModNumis a highly ergonomic modular arithmetic struct intended for no_std use.ModNumCis similar to ModNum, but uses const generics to specify the modulo.ModNumIteratoris a double-ended iterator that starts with theModNumupon which it is invoked, making a complete traversal of the elements in thatModNum’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),
*, /, pow(), and ==. Additional capabilities include computing multiplicative inverses
and solving modular equations.
ModNumC objects likewise represent a value modulo M, where M is a generic constant of the
usize type. Arithmetic operators include +, - (both unary and binary), *, and ==.
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 both ModNum and ModNumC.
Note that ModNum and ModNumC 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 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::*;
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. In the latter case, if the modulo values differ it will panic. For a ModNumC, there is no risk of a panic, as any disparity will be flagged at compile time.
Unary negation is 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));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.
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));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.
use bare_metal_modulo::*;
let m = ModNum::new(2, 5);
assert!(m == 2);
assert!(m == 7);
assert!(m == -3);
assert!(m != 3);
let m: ModNumC<i32,5> = ModNumC::new(2);
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::*;
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]);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::*;
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
Represents an integer a (mod m)
Represents an integer a (mod M)
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.