mod: Fast type-safe modular arithmetic

[ library, math, mit, number-theory ] [ Propose Tags ] [ Report a vulnerability ]

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


[Skip to Readme]

Flags

Automatic Flags
NameDescriptionDefault
semirings

Derive semiring instances

Enabled
vector

Derive unboxed and primitive vector instances

Enabled

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

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.0.0.0, 0.1.0.0, 0.1.1.0, 0.1.2.0, 0.1.2.1, 0.1.2.2, 0.2.0.0, 0.2.0.1
Change log changelog.md
Dependencies base (>=4.15 && <5), deepseq, ghc-bignum, primitive, semirings (>=0.5), vector (>=0.12) [details]
Tested with ghc ==9.0.2, ghc ==9.2.5, ghc ==9.4.4, ghc ==9.6.1
License MIT
Copyright 2017-2022 Andrew Lelechenko
Author Andrew Lelechenko <andrew.lelechenko@gmail.com>
Maintainer Andrew Lelechenko <andrew.lelechenko@gmail.com>
Category Math, Number Theory
Home page https://github.com/Bodigrim/mod
Bug tracker https://github.com/Bodigrim/mod/issues
Source repo head: git clone https://github.com/Bodigrim/mod
Uploaded by Bodigrim at 2023-02-13T20:29:53Z
Distributions Arch:0.2.0.1, LTSHaskell:0.2.0.1, NixOS:0.2.0.1, Stackage:0.2.0.1
Reverse Dependencies 7 direct, 7905 indirect [details]
Downloads 8353 total (163 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for mod-0.2.0.1

[back to package description]

mod Hackage Stackage LTS Stackage Nightly

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 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 the 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, 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.