Malachite, a new arbitrary-precision arithmetic library

Hi everyone,

For the past 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.

17 Likes

Very cool! Defining rationals between two values could come in handy.

1 Like

Small update: After getting some feedback from Reddit, I've decided to prioritize arbitrary-precision floats over primality testing and factorization. I'm still planning to implement the latter, but floats will come first. I think Malachite's approach of closely following existing code, in this case MPFR, is going to work well, since the MPFR developers have already figured out what the function specifications should be and what all the edge cases are.

Before I start working on floats, there are a few more integer functions that I want to add. Last week I released Malachite 0.2.3, which added extended GCD implementations to primitive integers, Naturals, and Integers. I'm currently working on modular inversion, including a neat, fast algorithm for inversion modulo a power of 2 that I found here; I don't think it's implemented in GMP or FLINT. (Edit: it is.)

It's implemented as mpn_binvert and widely used in GMP.

1 Like

My mistake.