mod alternatives and similar packages
Based on the "Math" category
* Code Quality Rankings and insights are calculated and provided by Lumnify.
They vary from L1 to L5 with "L5" being the highest. Visit our partner's website for more details.
Do you think we are missing an alternative of mod or a related project?
> :set -XDataKinds > 4 + 5 :: Mod 7 (2 `modulo` 7) > 4 - 5 :: Mod 7 (6 `modulo` 7) > 4 * 5 :: Mod 7 (6 `modulo` 7) > 4 / 5 :: Mod 7 (5 `modulo` 7) > 4 ^ 5 :: Mod 7 (2 `modulo` 7)
There are other Haskell packages, employing the very same idea of moduli on the type level,
modular-arithmetic. One can also use
which covers some elementary modular arithmetic as well.
Unfortunately, all of them fall behind
in terms of performance. Here is a brief comparison:
Addition. All competing implementations of the modular addition involve divisions, while
modcompletely avoids this costly operation. It makes 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.
(*). When a modulo fits a machine word (which is quite a common case on 64-bit architectures),
modimplements the modular multiplication as a couple of CPU instructions and neither allocates intermediate arbitrary-precision values, nor calls
libgmpat 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
libgmpfor modular inversions. Even for small arguments it is about 5x faster than the native implementation of modular inversion in
Power. This package relies on
libgmpfor modular exponentiation. Even for small arguments it is about 2x faster than competitors.
Overflows. At first glance
modular-arithmeticis 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 100returns
44instead of expected
0. Even less expected is that
50 :: Mod Word8 300appears to be
6(remember that type-level numbers are always
Citius, altius, fortius!
If you are looking for an ultimate performance
and your moduli fit into
which is a drop-in replacement of
but offers almost 3x faster addition,
2x faster multiplication and much less allocations.
Here are some relative benchmarks,
which can be reproduced by running
This package was cut out of
to provide a modular arithmetic
with a light dependency footprint. This goal certainly limits the scope of API
to the bare minimum. If you need more advanced tools
(the Chinese remainder theorem, cyclic groups, modular equations, etc.)
please refer to Math.NumberTheory.Moduli.