package euler
Install
Authors
Maintainers
Sources
sha256=46786c629673fc8f36c6ee57764778188983f6de8e24d3003a8de21e4752919c
sha512=5273d89967cba8397139a179c243ecb7a80c008961a06bc5396316cc32651fc902a9eb0152b98f5075db4331349d6c8dc23f249ca3fc67be5b984daac9debd6c
Description
euler is a library for doing integer arithmetic with OCaml’s standard integers (31 or 63 bits). It provides:

Dropin, overflowdetecting base arithmetic: if you are paranoid about vicious bugs sneaking in silently, this library detects overflows and signal them by throwing an exception; the module can be used as a dropin replacement for the standard library (beware that Euler.Arith.min_int differs from Stdlib.min_int, the latter being a forbidden value). There are also a few additional functions such as integer logarithms and square roots.

More advanced arithmetic: for the weird folks (like myself) who are interested in advanced arithmetic but do not care about integers larger than 262, and thus do not want the burden of using an arbitraryprecision library (zarith of GMP), there you are. The library provides some classic functions such as the GCD, the Jacobi symbol, primality testing (fast and deterministic for all 63bit integers!), integer factorization (implementing Lenstra’s elliptic curve factorization, which was apparently one of the best known algorithms back when I wrote that code, but obviously it is still very slow! — and I must say I understand very little about it…), a prime sieve (heavily optimized) and a factorization sieve, Euler’s totient function (slow too, of course), and so on.

Solvers for some forms of integer equations (socalled “Diophantine equations”): linear congruence systems (the Chinese remainder theorem), PellFermat’s equations (the Chakravala method) — preliminary code that just needs some packaging effort).

Modular arithmetic: including finding modular inverses (and pseudoinverses). A nice functorial interface provides convenient notations and uses a private type to enforce that values are always normalized in the range 0…m−1 where m is the modulus. Example use:
module M = Euler.Modular.Make (struct let modulo = 42 end) let () = assert (M.( !:1 /: (!:33 +: !:4) = !:5 *:(4) )) ( said otherwise, modulo 42, the inverse of (33 + 4) is equal to 5^(−4) *)
Published: 29 Jun 2023
Dependencies (4)
 seq
 containers

ocaml
>= "4.14"

dune
>= "2.0"