chalk 0.1.1

A computational algebra library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

use crate as chalk;
use crate::chalk;
use crate::AddIdentity;
use crate::Binary;
use crate::MulIdentity;

#[derive(Copy, Clone, Default, Eq, PartialEq)]
#[chalk(
  |> Ring
)]
pub struct ZMod<const N: usize>(usize);

impl<const N: usize> Binary for ZMod<N> {
  type Rhs = Self;
  fn into_rhs(&self) -> &Self {
    self
  }
}

impl<const N: usize> From<usize> for ZMod<N> {
  fn from(n: usize) -> ZMod<N> {
    ZMod(n)
  }
}

impl<const N: usize> ZMod<N> {
  fn reduce(&mut self) {
    match const { Algorithm::choose(N, 0) } {
      Algorithm::Add(exponent, power) => {
        if self.0 >= power {
          self.0 = (self.0 >> exponent) + (self.0 & (power - 1))
        }
      }
      Algorithm::Mod => {
        self.0 %= N;
      }
    }
  }
}

enum Algorithm {
  Add(usize, usize),
  Mod,
}

impl Algorithm {
  const fn choose(n: usize, i: usize) -> Algorithm {
    if i == 32 {
      Algorithm::Mod
    } else if (1 << i) % n == 1 {
      Algorithm::Add(i, 1 << i)
    } else {
      Algorithm::choose(n, i + 1)
    }
  }
}

impl<'a, const N: usize> std::ops::AddAssign<&'a ZMod<N>> for ZMod<N> {
  fn add_assign(&mut self, ZMod(rhs): &'a ZMod<N>) {
    self.0 += rhs;
    self.reduce()
  }
}

impl<'a, const N: usize> std::ops::SubAssign<&'a ZMod<N>> for ZMod<N> {
  fn sub_assign(&mut self, ZMod(rhs): &'a ZMod<N>) {
    self.0 += N - rhs;
    self.reduce()
  }
}

impl<'a, const N: usize> std::ops::MulAssign<&'a ZMod<N>> for ZMod<N> {
  fn mul_assign(&mut self, ZMod(rhs): &'a ZMod<N>) {
    self.0 *= rhs;
    self.reduce()
  }
}

impl<const N: usize> AddIdentity for ZMod<N> {
  fn add_id() -> ZMod<N> {
    Default::default()
  }
}

impl<const N: usize> MulIdentity for ZMod<N> {
  fn mul_id() -> ZMod<N> {
    ZMod(1)
  }
}