Euclidean and related algorithms in Scala / Dotty

A sampler of Euclidean algorithms written in pure Scala / Dotty.

Algorithms

These purely-functional methods provide textbook implementations of number theory primitives, designed to be read by humans. The source appears in src/main/scala/Euclid.scala.

• gcd and lcm implement the Euclidean greatest common divisor and least common multiple algorithms.

• bezout generates Bézout numbers via the extended Euclidean algorithm.

• modDiv computes modular division: Given integers a, n, and d, the modDiv function returns a number m such that m * d == a (mod n), i.e., it divides a by d modulo n.

• continuedFraction streams a continued fraction expansion of two integers.

• convergents returns a stream of convergents for a ratio n / d.

• rationalApprox provides the best rational approximation to a fraction, given an upper-bound on the denominator.

Effort has been made to make these algorithms correct, concise, and idiomatic Scala. If you have ideas for improvements, we welcome pull requests that further these goals.

All algorithms operate on BigInts.

Building and testing

Tests for the functions can be run via sbt test. The code compiles using the Dotty compiler.

Dotty, you say?

Dotty represents the future of Scala. While the two languages are not fully compatible, if you've programmed in Scala but haven't heard of Dotty, you probably won't notice any differences than a significantly faster build.

You can learn more about Dotty from Dotty's documentation, or just get an overview of the changes by perusing Martin Odersky's slides.

License

Software released under the MIT license. See the LICENSE for details.