Extension of the Mods package for very small moduli.
The MiniMods module defines the MiniMod type that behaves
exactly the same as Mod (from the Mods module) except that
moduli are restricted to lie between 2 and 255. In this way, a
MiniMod only takes up one byte of memory, whereas a Mod uses
eight.
julia> using MiniMods
julia> a = MiniMod{17}(-2)
MiniMod{17}(15)
julia> inv(a)
MiniMod{17}(8)
julia> 2a-5
MiniMod{17}(8)
julia> b = MiniMod{1000}(-1)
ERROR: AssertionError: modulus is too large
While it is not clear why one would like to mix expressions with both Mod and
MiniMod types, this is permitted so long as the moduli of the numbers are the same. The result of such a mixed expression is MiniMod because this is the more
space efficient type.
julia> using Mods
julia> a = MiniMod{10}(6);
julia> b = Mod{10}(5);
julia> a+b
MiniMod{10}(1)
julia> sizeof(a)
1
julia> sizeof(b)
8
We have tested using MiniMods with LinearAlgebra, LinearAlgebraX, and SimplePolynomials. It appears to work well in those settings.
julia> using LinearAlgebra, LinearAlgebraX
julia> A = rand(MiniMod{11},5,5)
5×5 Matrix{MiniMod{11}}:
MiniMod{11}(4) MiniMod{11}(2) MiniMod{11}(0) MiniMod{11}(6) MiniMod{11}(1)
MiniMod{11}(4) MiniMod{11}(5) MiniMod{11}(1) MiniMod{11}(3) MiniMod{11}(6)
MiniMod{11}(9) MiniMod{11}(7) MiniMod{11}(2) MiniMod{11}(9) MiniMod{11}(9)
MiniMod{11}(1) MiniMod{11}(9) MiniMod{11}(7) MiniMod{11}(0) MiniMod{11}(5)
MiniMod{11}(5) MiniMod{11}(7) MiniMod{11}(5) MiniMod{11}(2) MiniMod{11}(8)
julia> det(A)
MiniMod{11}(7)
julia> detx(A)
MiniMod{11}(7)
julia> rankx(A)
5
julia> sizeof(A) # 5x5 matrix of MiniMods using 25 bytes
25
julia> sizeof(Mod.(A)) # but same matrix of Mods using 8 times as much
200
julia> using SimplePolynomials
julia> x = getx()
x
julia> p = one(MiniMod{2}) + x
MiniMod{2}(1) + MiniMod{2}(1)*x
julia> p^8
MiniMod{2}(1) + MiniMod{2}(1)*x^8
julia> using MiniMods, Mods, LinearAlgebra, BenchmarkTools
julia> m = 251; d = 500;
julia> A = rand(Mod{m}, d, d);
julia> B = MiniMod.(A);
julia> @btime A*A;
601.262 ms (6 allocations: 1.94 MiB)
julia> @btime B*B;
682.364 ms (6 allocations: 275.75 KiB)
julia> @btime det(A)
150.941 ms (4 allocations: 1.91 MiB)
Mod{251}(217)
julia> @btime det(B)
176.047 ms (4 allocations: 248.31 KiB)
MiniMod{251}(217)
We envision that users of this module will be primarily using very small
moduli, so the upper bound of 255 won't (we hope) be a problem. However,
users may elect to modify the code to work with larger integers (but smaller
than Int).
In the source file MiniMods.jl find the line
const SmallInt = UInt8and change UInt8 to another integer type. For example, use UInt16 to expand
the range of moduli to 65535.