mod: Fast type-safe modular arithmetic

[ library, math, mit, number-theory ] [ Propose Tags ]

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

[Skip to Readme]
Versions [faq]
Change log
Dependencies base (>=4.9 && <5), deepseq, integer-gmp (<1.1), semirings (>=0.5) [details]
License MIT
Copyright 2019 Andrew Lelechenko
Author Andrew Lelechenko <>
Maintainer Andrew Lelechenko <>
Category Math, Number Theory
Home page
Bug tracker
Source repo head: git clone
Uploaded by Bodigrim at Sun Nov 3 20:19:56 UTC 2019
Distributions NixOS:
Downloads 96 total (45 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2019-11-03 [all 1 reports]


[Index] [Quick Jump]



Derive semiring instances


Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info


Maintainer's Corner

For package maintainers and hackage trustees

Readme for mod-

[back to package description]

mod Build Status Hackage Hackage CI Stackage LTS Stackage Nightly

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)


There are other Haskell packages, employing the very same idea of moduli on the type level, namely modular and modular-arithmetic. Unfortunately, both of them fall behind in terms of performance. Here is a brief comparison:

| Discipline | mod | modular | modular-arithmetic | :---------- | :----: | :-------: | :------------------: | Addition | Fast | Slow | Slow | Small (*) | Fast | Slow | Slow | Inversion | Fast | N/A | Slow | Power | Fast | Slow | Slow | Overflows | Safe | Safe | Unsafe

  • Addition. It appears that modular and modular-arithmetic 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'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.