logo

Announcing Malachite, a new arbitrary-precision arithmetic library

110 points mikhail_hogrefe
View on Reddit ↗

(I've made this same post on users.rust-lang.org.)

Hi everyone,

For the best 5 years I've been writing Malachite, a library that provides bignum Naturals, Integers, and Rationals. Now that it has approximate feature parity with other bignum Rust libraries, I'm ready to release it. You can find links to crates.io and docs.rs at www.malachite.rs.

The obvious question is, why use Malachite when num exists? In two words, performance and features.

Malachite's secret sauce is that a good portion of its code (40 to 50%, if I had to guess) is translated from GMP's and FLINT's C code into safe Rust. The resulting code is complex, but thoroughly tested; Malachite has 4,297 unit tests and 1,652 doctests. I've shown the results of some benchmarks here, but I highly encourage you to make your own benchmarks too! The general trend is that Malachite is (often significantly) faster than num, and slower than GMP (which has been around for decades and is very highly optimized).

The downside of using translated code is that Malachite has to be released under LGPL, a more restrictive license than num's MIT or Apache.

As for unique features, there are too many to describe here; I've tried to make the docs.rs comprehensive, so they're a good place to get an overview. For each of Malachite's crates I'll give an example of something that I don't think you can do with any other Rust library (or in GMP, for that matter).

malachite-base has many utilities used by the other two crates. Among other things, it provides iterators that exhaustively generate all values of a type. Apart from being interesting in themselves, I've used these to great effect when testing the rest of Malachite. For example, this code generates the first 20 Vec<u8>s, ordered more-or-less by simplicity:

for xs in exhaustive_vecs(exhaustive_unsigneds::<u8>()).take(20) {
    println!("{:?}", xs);
} 

[]
[0]
[1]
[0, 0, 0]
[2]
[0, 0]
[3]
[0, 0, 0, 0]
[4]
[0, 1]
[5]
[0, 0, 1]
[6]
[1, 0]
[7]
[0, 0, 0, 0, 0]
[8]
[1, 1]
[9]
[0, 1, 0]

malachite-nz defines Naturals and Integers. Apart from all the usual operations, you can also do lots of modular arithmetic, or divide-and-round using a specified rounding mode. Another thing you can do is format them in scientific notation:

println!("{}", Natural::power_of_2(1_000_000).to_sci()); 

9.900656229295898e301029

By using to_sci_with_options, you can specify many options including the precision and the base.

malachite-q defines Rationals. You can do the usual things with them, and also convert them to and from primitive floats, which I believe num doesn't let you do. And here's an example of finding the simplest (lowest-denominator) fraction between 3.14 and 3.15:

let a = Rational::from_sci_string("3.14").unwrap();
let b = Rational::from_sci_string("3.15").unwrap();
println!("{}", Rational::simplest_rational_in_open_interval(&a, &b));

22/7

I have a lot planned for Malachite's future. I intend to implement the following, roughly in chronological order:

  • Some of the remaining integer functions in GMP, like extended GCD, the Jacobi symbol, factorials, and binomial coefficients
  • Univariate polynomials
  • Primality testing and factorization (using code translated from FLINT)
  • Arbitrary-precision floats (using code translated from MPFR) and more.

I'm eager to respond to all of your questions and comments.