mod
Modular arithmetic,
promoting moduli to the type level, with an emphasis on performance.
Originally a part of the arithmoi package.
> :set XDataKinds
> 4 + 5 :: Mod 7
2
> 4  5 :: Mod 7
6
> 4 * 5 :: Mod 7
6
> 4 / 5 :: Mod 7
5
> 4 ^ 5 :: Mod 7
2
Competitors
There are other Haskell packages, employing the very same idea of moduli on the type level,
namely modular
, modulararithmetic
and finitefield
. One can also use finitetypelits
,
which covers some elementary modular arithmetic as well.
Unfortunately, all of them fall behind
in terms of performance. Here is a brief comparison:
Discipline 
mod 
modular 
modulararithmetic 
finitetypelits 
finitefield 
Addition 
Fast 
Slow 
Slow 
Slow 
Slow 
Small (*) 
Fast 
Slow 
Slow 
Slow 
Slow 
Inversion 
Fast 
N/A 
Slow 
N/A 
Slow 
Power 
Fast 
Slow 
Slow 
Slow 
Slow 
Overflows 
Safe 
Safe 
Unsafe 
Safe 
Safe 

Addition.
All competing implementations of
the modular addition involve divisions, while mod
completely avoids
this costly operation. This makes a difference even for small numbers;
e. g., sum [1..10^7]
becomes 5x faster. For larger integers the speed up
is even more significant, because the computational complexity of division is not linear.

Small (*)
.
When a modulus fits in a machine word (which is quite a common case on 64bit architectures),
mod
implements the modular multiplication as a couple of CPU instructions
and neither allocates intermediate arbitraryprecision values,
nor calls libgmp
at all. For computations like product [1..10^7]
this gives a 3x boost to performance
in comparison to other libraries.

Inversion.
This package relies on libgmp
for modular inversions.
Even for small arguments it is about 5x faster than
the native implementation of modular inversion
in modulararithmetic
.

Power.
This package relies on libgmp
for modular exponentiation.
Even for small arguments it is about 2x faster than competitors.

Overflows.
At first glance modulararithmetic
is more flexible than mod
,
because it allows to specify the underlying representation of a modular residue,
e. g., Mod Integer 100
, Mod Int 100
, Mod Word8 100
. We argue that this is
a dangerous freedom, vulnerable to overflows.
For instance, 20 ^ 2 :: Mod Word8 100
returns 44
instead of the expected 0
.
Even less expected is that 50 :: Mod Word8 300
appears to be 6
(remember that typelevel numbers are always Natural
).
What is the difference between mod
and finitetypelits
?
mod
is specifically designed to represent modular residues
for mathematical applications (wrappingaround finite numbers) and
provides modular inversion and exponentiation.
The main focus of finitetypelits
is on nonwrappingaround finite numbers,
like indices of arrays in vectorsized
.
It features a Num
instance only for the sake of overloading numeric literals.
There is no lawful way to define Num
except modular arithmetic,
but from finitetypelits
' viewpoint this is a byproduct.
Citius, altius, fortius!
If you are looking for an ultimate performance
and your moduli fit into Word
,
try Data.Mod.Word
,
which is a dropin replacement of Data.Mod
,
offering better performance and much less allocations.
Benchmarks
Here are some relative benchmarks (less is better),
which can be reproduced by running cabal bench
.
Discipline 
Data.Mod.Word 
Data.Mod 
modular 
modulararithmetic 
finitetypelits 
finitefield 
Sum 
0.44x 
1x 
16.6x 
8.9x 
14.7x 
14.2x 
Product 
0.95x 
1x 
7.8x 
4.5x 
7.0x 
7.0x 
Inversion 
0.54x 
1x 
N/A 
3.2x 
N/A 
1.8x 
Power 
0.29x 
1x 
2.0x 
1.2x 
1.4x 
1.5x 
What's next?
This package was cut out of arithmoi
to provide modular arithmetic
with a light dependency footprint. This goal certainly limits the scope of the API
to the bare minimum. If you need more advanced tools
(the Chinese remainder theorem, cyclic groups, modular equations, etc.)
please refer to the Math.NumberTheory.Moduli module.