mod
Fast type-safe modular arithmetic
https://github.com/Bodigrim/mod
LTS Haskell 22.40: | 0.2.0.1 |
Stackage Nightly 2024-11-03: | 0.2.0.1 |
Latest on Hackage: | 0.2.0.1 |
mod-0.2.0.1@sha256:eeb316fef3a8c12f4e83bbeeea748e74d75fca54d4498d574ace92e464adb05a,2409
Module documentation for 0.2.0.1
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
, modular-arithmetic
and finite-field
. One can also use finite-typelits
,
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 |
modular-arithmetic |
finite-typelits |
finite-field |
---|---|---|---|---|---|
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 64-bit architectures),mod
implements the modular multiplication as a couple of CPU instructions and neither allocates intermediate arbitrary-precision values, nor callslibgmp
at all. For computations likeproduct [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 inmodular-arithmetic
. -
Power. This package relies on
libgmp
for modular exponentiation. Even for small arguments it is about 2x faster than competitors. -
Overflows. At first glance
modular-arithmetic
is more flexible thanmod
, 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
returns44
instead of the expected0
. Even less expected is that50 :: Mod Word8 300
appears to be6
(remember that type-level numbers are alwaysNatural
).
What is the difference between mod
and finite-typelits
?
mod
is specifically designed to represent modular residues
for mathematical applications (wrapping-around finite numbers) and
provides modular inversion and exponentiation.
The main focus of finite-typelits
is on non-wrapping-around finite numbers,
like indices of arrays in vector-sized
.
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 finite-typelits
’ viewpoint this is a by-product.
Citius, altius, fortius!
If you are looking for an ultimate performance
and your moduli fit into Word
,
try Data.Mod.Word
,
which is a drop-in 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 |
modular-arithmetic |
finite-typelits |
finite-field |
---|---|---|---|---|---|---|
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.
Changes
0.2.0.1
- Fix build on
aarch64
.
0.2.0.0
- Breaking change: redesign
GcdDomain
andEuclidean
instances. - Add
instance Read
andinstance Real
. - Migrate from
integer-gmp
toghc-bignum
. - Remove
(^) -> (^%)
rewrite rule, it does not fire. - Plug loopholes to inhabit
Mod 0
. - Work around performance degradation on ARM.
0.1.2.2
- Work around an issue with
fromIntegral
in GHC 9.0.1.
0.1.2.1
- Support
integer-gmp-1.1
.
0.1.2.0
- Add
Storable
,Prim
andUnbox
instances.
0.1.1.0
- Add
Data.Mod.Word
.
0.1.0.0
- Initial release