# \[ANN\] euler, an arithmetic library for native integers **URL:** \ **Category:** Community\ **Created:** [June 26, 2023, 4:06pm UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482 "2023-06-26T16:06:39Z")\ **Posts on this page:** 11\ **Page:** 1
**Author:** ![glen](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/glen/32/4656_2.png) [@glen](https://discuss.ocaml.org/u/glen)\ **Post date:** [June 26, 2023, 4:06pm UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/1 "2023-06-26T16:06:39Z")
In case anyone is interested, I let you know of `euler`, a small arithmetic library of mine. Unfortunately it is not published on opam (but there is an opam file), and I won’t be working on it anymore, so anyone is welcome to take over the project or just steal code from it. If you see fun in it, I left plenty of TODOs! 🙂 The library is documented, with a focus on algorithmic complexities, and implementation code has a lot of comments too. **[repo](https://gitlab.crans.org/mevel/euler-lib), [doc preview](https://perso.crans.org/mevel/odoc/euler/Euler/).** # What’s in it? `euler` is a library for doing integer arithmetic with OCaml’s standard integers (31 or 63 bits). It provides: - Drop-in, **overflow-detecting** 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 drop-in 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 arbitrary-precision 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 63-bit 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** (so-called “Diophantine equations”): - linear congruence systems (the Chinese remainder theorem), - Pell-Fermat’s equations (the Chakravala method) — preliminary code that just needs some packaging effort). - **Modular arithmetic** : including finding modular inverses (and pseudo-inverses). 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: ```ocaml 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) *) ``` # But why? Writing this library was fun and educative for me, and allowed me to solidify my math training in code. In fact, as the name suggests, the initial incentive was playing with Project Euler (hence the focus on integers that fit in a machine word) while sparing me the boredom of implementing a prime sieve for the hundredth time. Nevertheless, I believe `euler` might prove actually useful outside of the playground. Overflow detection is an actual need in some software, and implementing it is not trivial, even less so after some amount of micro-optimization (see code). Modular arithmetic is not trivial either (e.g. multiplication is not as simple as `(a * b) mod m` because this computation might overflow). And well, even integer logarithms and square roots are handy at times, and again they not trivial to implement (as using their floating-point counterpart gives incorrect results for large integers). ---
**Author:** ![sim642](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/sim642/32/3597_2.png) [@sim642](https://discuss.ocaml.org/u/sim642)\ **Post date:** [June 26, 2023, 5:19pm UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/2 "2023-06-26T17:19:14Z")
> [@glen](#): > > Unfortunately it is not published on opam (but there is an opam file), and I won’t be working on it anymore, so anyone is welcome to take over the project or just steal code from it. It might still be worth making one release on opam-repository such that it could be easily used, even if you won’t be updating it and making more releases. ---
**Author:** ![UnixJunkie](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/unixjunkie/32/638_2.png) [@UnixJunkie](https://discuss.ocaml.org/u/UnixJunkie)\ **Post date:** [June 28, 2023, 1:36am UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/3 "2023-06-28T01:36:54Z")
Can you upload the code on github? I cannot access your repo. I want to look at some code in there. ---
**Author:** ![mseri](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/mseri/32/91_2.png) [@mseri](https://discuss.ocaml.org/u/mseri)\ **Post date:** [June 28, 2023, 6:54am UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/4 "2023-06-28T06:54:18Z")
I have a copy forked here if you want: [GitHub - mseri/euler-lib: Fork of https://gitlab.crans.org/mevel/euler-lib](https://github.com/mseri/euler-lib) ---
**Author:** ![glen](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/glen/32/4656_2.png) [@glen](https://discuss.ocaml.org/u/glen)\ **Post date:** [June 28, 2023, 10:34am UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/5 "2023-06-28T10:34:04Z")
Great! You might want to pull again, as I just pushed two small commits (more TODOs!). And since the number of commits is now a satisfying 100, I think that’s all for me. 🙂 > [@UnixJunkie](#): > > Can you upload the code on github? That I can do! So now [the repo is there](https://github.com/gmevel/euler-lib) (argh, 101). (It seems I am unable to edit my first post so as to put the new link, well.) ---
**Author:** ![mseri](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/mseri/32/91_2.png) [@mseri](https://discuss.ocaml.org/u/mseri)\ **Post date:** [June 28, 2023, 11:15am UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/6 "2023-06-28T11:15:38Z")
Ah fantastic, thanks! I have synced them again. M ---
**Author:** ![mseri](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/mseri/32/91_2.png) [@mseri](https://discuss.ocaml.org/u/mseri)\ **Post date:** [June 28, 2023, 11:18am UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/7 "2023-06-28T11:18:12Z")
I would be happy to make a release on the opam-repository if you are fine with it. If you are comfortable with it, you could also give me access to your repo on GitHub and I can do it from there directly. ---
**Author:** ![glen](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/glen/32/4656_2.png) [@glen](https://discuss.ocaml.org/u/glen)\ **Post date:** [June 28, 2023, 11:46am UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/8 "2023-06-28T11:46:26Z")
Please do. 🙂 Access granted. ---
**Author:** ![struktured](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/struktured/32/385_2.png) [@struktured](https://discuss.ocaml.org/u/struktured)\ **Post date:** [June 28, 2023, 1:53pm UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/9 "2023-06-28T13:53:56Z")
This is very cool- thanks for sharing. I wonder if this is a useful addition to [Owl](https://github.com/owlbarn/owl), the ocaml “fat” math library. ---
**Author:** ![glen](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/glen/32/4656_2.png) [@glen](https://discuss.ocaml.org/u/glen)\ **Post date:** [July 21, 2023, 5:07pm UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/10 "2023-07-21T17:07:12Z")
Thanks to @mseri, `euler` is now on opam! And in the meantime it has gained more functions, the most striking of which being [`Primes.prime_seq : int -> int Seq.t`](https://gmevel.github.io/euler-lib/index.html/euler/Euler/Primes/index.html#val-prime_seq) (thank @cuihtlauac for pointing me to the algorithm!) and [`Arith.smallest_root : int -> int * int`](https://github.com/gmevel/euler-lib/blob/39648c6/src/Euler.mli#L429-L433) (the latter in the next release, 3.0, not on opam yet). Also, since I still cannot edit the first post, this is a reminder that the project has moved to GitHub: **[repo](https://github.com/gmevel/euler-lib)**, **[doc](https://gmevel.github.io/euler-lib/index.html/euler/Euler/)**. The links in my first message won’t be updated. > [@struktured](#): > > I wonder if this is a useful addition to [Owl](https://github.com/owlbarn/owl), the ocaml “fat” math library. Perhaps? I am not very familiar with Owl (ask Owl’s Benevolent Dictators For Life? 😉 ). Euler is an integer arithmetic library whereas, as I understand it, Owl is mainly a floating-point math library for scientific computing (linear algebra, differentiation, statistics and and such). I would guess that prime numbers and friends are rather remote concerns for Owl users, but perhaps Owl is interested in expanding its domains? I did spot [a small number of integer arithmetic functions in Owl](https://github.com/owlbarn/owl/blob/48434ea/src/owl/maths/owl_maths.mli#L587-L607), most of which are also found in Euler. ---
**Author:** ![glen](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/glen/32/4656_2.png) [@glen](https://discuss.ocaml.org/u/glen)\ **Post date:** [June 28, 2024, 11:25pm UTC](https://discuss.ocaml.org/t/ann-euler-an-arithmetic-library-for-native-integers/12482/11 "2024-06-28T23:25:05Z")
cross-posting: [new topic](https://discuss.ocaml.org/t/ann-euler-0-3/14877)