# Announcing Primal: Putting Raw Power Into Prime Numbers

By Huon Wilson08 Jun 2015

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.

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:

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:

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

1. I realised the original implementation was inefficient, and using far more memory than necessary: fixing that made a huge difference.

I'm Huon Wilson @huon_w, a mathematically and statistically inclined software engineer. I have been a long-term volunteer on Rust's core team, a compiler engineer on the Swift team at Apple, and a senior software engineer at CSIRO's Data61, working on the StellarGraph graph machine learning library.