# Crate bare_metal_modulo[−][src]

Expand description

## Overview

The bare_metal_modulo crate includes two 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 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), *, /, 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::SaturatingSub;

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