Announcing Primal: Putting Raw Power Into Prime Numbers

Over the past few weeks I’ve been working on improving my slow_primes library, culminating in needing rename and the 0.2 release of primal, a Rust crate for computing properties of prime numbers with state-of-the-art algorithms, while still maintaining an idiomatic and easy-to-use interface.

primal

My computer takes a quarter of a second and less than 3MB of RAM to tell me that there 50,847,534 primes below 1 billion:

1
2
3
4
5
6
extern crate primal;

fn main() {
    println!("there are {} primes below 1 billion",
             primal::StreamingSieve::prime_pi(1_000_000_000));
}

Some of the first programming I did was Project Euler: a site that has little mathematical problems designed to be solved with the assistance of a computer. Beyond just the challenge of solving the problem, there’s the challenge of writing code to go as fast as possible: Project Euler will always hold a little place in my heart for making me learn a lot about writing fast code. That’s where I first tried to write fast prime sieves: I recall being pretty happy when I could sieve up to a “big” number like 1 million quickly; now I’m pretty happy that I can sieve up to 1 billion in (probably) less time, and certainly less memory.

Migrating from slow_primes/primal 0.1

• rename slow_primes to primal or bump the version in your Cargo.toml,
• replace Primes with Sieve: Primes::sieve(100) → Sieve::new(100),
• call primes_from instead of primes(): sieve.primes() → sieve.primes_from(0),
• revel in the improved sieving performance.

Highlights

primal is pretty great, if I do say so myself:

• the documentation is complete: every function has some text describing it, all have explicit examples (except Sieve::new), and there’s a nice introductory walk-through tackling three classes of problems.
• it includes a highly optimised segmented, wheel sieve: Sieve. It is essentially a Rust port of Kim Walisch’s awesome primesieve, which is apparently the fastest sieve in the world. The version in primal is really fast, certainly the fastest sieve I can find in Rust, but there’s still room to improve: the Rust version is currently around 5-20% slower than primesieve (single-threaded), and lacks some of the fancier features that it adds on top.

• there’s some reasonably deep mathematics: estimate_nth_prime(n) and estimate_prime_pi(k) provide fast (O(1)) but precise bounds for the nth prime, and the number of primes below k:

  • estimate_prime_pi(1_000_000_000) returns a lower-bound of 50,785,736 (0.12% below the true value) and an upper-bound of 50,865,514 (0.04% above),
  • estimate_nth_prime(50_847_535) returns 999,873,297 and 1,000,273,162, which are 0.01% below and 0.03% above (respectively) the true value of 1,000,000,007.

However, my favourite feature is Primes: which is an fast lazy iterator over all primes, with no upper-bound (other than integer size). In a flash of inspiration, I realised it would be possible to do this reasonably efficiently with a simple wrapper around the core sieve. It can be used a bit like:

1
2
3
4
5
6
extern crate primal;

fn main() {
    println!("the 50,847,535th prime is {}",
             primal::Primes::all().nth(50_847_535 - 1).unwrap());
}

It’s not the most efficient way to get the nth prime, but it still only takes 0.9 0.52 seconds⁰ to print 1,000,000,007. (A better way is StreamingSieve::nth_prime, which takes ~0.22s for the same task.)