Performance

Here are some benchmarks comparing the Malachite to two other libraries:

• num, the de facto standard bignum library for Rust.
• rug, a library that calls GMP, a widely used, highly-optimized bignum library written in C.

The num version that is compared against is 0.4.3, and the rug version is 1.30.0. The Malachite version is 0.10.0.

The general trend is that Malachite is faster than num due to better algorithms, and slower than rug, though the gap is steadily decreasing. My guess is that the better performance of rug is due partly to GMP’s use of inline assembly (Malachite has none, being written entirely in safe Rust), and possibly due to operations on Rust’s slices being a little slower than C’s raw pointers.

The following is just a small sample of the benchmarks that are available in Malachite. For each benchmark, I’ve included the command that you can use to run it yourself. You can specify the output file using -o benchfile.gp, and then use gnuplot to convert the .gp to your format of choice. I like SVG:

gnuplot -e "set terminal svg; l \"benchfile.gp\"" > benchfile.svg

Rational addition

cargo run --features bin_build --release -- -l 100000 -m random -b benchmark_rational_add_library_comparison -c "mean_bits_n 256"

The most significant operations involved in adding two rational numbers (fractions) are GCD computation and division.

For GCD computation, num uses the binary GCD algorithm, a quadratic algorithm. Malachite follows GMP in using Lehmer’s GCD algorithm, which takes advantage of fast multiplication algorithms to achieve \(O(n (\log n)^2 \log \log n)\) time.

For division, num uses Knuth’s Algorithm D, which is quadratic, for small inputs. For large inputs it uses Burnikel-Ziegler division, which takes \(O(n \log n \log \log n)\) time. Malachite, again following GMP, uses several division algorithms depending on the input size. For the largest inputs, it uses a kind of Barrett reduction, which also takes \(O(n \log n \log \log n)\) time.

Converting a Natural to a string

cargo run --features bin_build --release -- -l 100000 -m random -b benchmark_natural_to_string_library_comparison -c "mean_bits_n 1024"

When converting a natural number to a string, num seems to use an \(O(n^{3/2})\) algorithm. Malachite uses a divide-and-conquer algorithm that takes \(O(n (\log n)^2 \log \log n)\) time.

Natural multiplication

cargo run --features bin_build --release -- -l 20000 -m random -b benchmark_natural_mul_library_comparison -c "mean_bits_n 16384"

For multiplying two natural numbers, num uses a basecase quadratic algorithm for small inputs, then Toom-22 (Karatsuba) multiplication for larger inputs, and finally Toom-33 for the largest ones. This means that multiplication takes \(O(n^{\log_3 5}) \approx O(n^{1.465})\) time.

Malachite also uses a basecase quadratic algorithm, then 13 variants of Toom-Cook multiplication, and finally Schönhage-Strassen (FFT) multiplication for the largest inputs, achieving \(O(n \log n \log \log n)\) time.

For numbers of up to 1000 bits, all three libraries are about equally fast:

cargo run --features bin_build --release -- -l 100000 -m random -b benchmark_natural_mul_library_comparison -c "mean_bits_n 64"

Natural addition

cargo run --features bin_build --release -- -l 100000 -m random -b benchmark_natural_add_library_comparison -c "mean_bits_n 1024"

Addition of natural numbers is fast for all three libraries, being a straightforward and linear-time affair. Here, rug is a bit slower than num or Malachite.

Copyright © 2026 Mikhail Hogrefe