# mod

Fast type-safe modular arithmetic

https://github.com/Bodigrim/mod

 Version on this page: 0.1.2.1 LTS Haskell 22.12: 0.2.0.1 Stackage Nightly 2024-02-27: 0.2.0.1 Latest on Hackage: 0.2.0.1

See all snapshots `mod` appears in

This version can be pinned in stack with:`mod-0.1.2.1@sha256:1d05bd12be7bb1d13fbf6a0d4b47c713b51af5fbf8a9a6f88dfeac6d822d9756,2220`

#### Module documentation for 0.1.2.1

Depends on 6 packages(full list with versions):
Used by 1 package in lts-17.2(full list with versions):

# mod

Modular arithmetic, promoting moduli to the type level, with an emphasis on performance. Originally a part of arithmoi package.

``````> :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)
``````

## 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. 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.

• Small `(*)`. When a modulo fits 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 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 `modular-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 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 expected `0`. Even less expected is that `50 :: Mod Word8 300` appears to be `6` (remember that type-level numbers are always `Natural`).

### 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`, but offers almost twice faster addition and multiplication, 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.4x 1x 4.5x 6.1x 3.3x 5.0x
Product 0.6x 1x 3.6x 5.4x 3.1x 4.5x
Inversion 0.8x 1x N/A 6.1x N/A 4.1x
Power 0.9x 1x 6.0x 1.8x 1.9x 2.1x

## Whatâ€™s next?

This package was cut out of `arithmoi` 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.

# 0.1.2.1

• Support `integer-gmp-1.1`.

# 0.1.2.0

• Add `Storable`, `Prim` and `Unbox` instances.

# 0.1.1.0

• Add `Data.Mod.Word`.

# 0.1.0.0

• Initial release