Project Euler

The best way I've found to learn new programming concepts is to build a small project. Sometimes I'll make a puzzle solver or a command line tool, but by far my favorite project to work on is Project Euler. It's a collection of math problems designed to be solved with the aid of a computer. The problems are usually simple, but because they can be solved in many ways, they're useful for learning how to use new libraries.

This page serves to document my progress in solving Project Euler problems. My initial goals in taking on this project were testing, benchmarking, iterators, paralellism, and optimization. My language of choice is Rust, which I believe to be one of the best programming languages for small projects. With one "cargo new" I can start coding with no further setup. Rust also has many mature libraries which can be incorporated into any project with ease. Additionally, Rust has a reputation for being fast and safe, which I will put to the test as I solve each problem.

Problem 1: Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

The first problem is simple, and most likely meant as an introduction to the style of future Project Euler problems. Because the limit of 1000 is so low, there are few concerns related to performance, but I explored a few different solutions to get used to benchmarking and testing in Rust. The first solution is a simple for loop, testing each number for the conditions.

pub fn euler_1(limit: u32) -> u32 {
        let mut sum = 0;
        for i in 1..limit {
            if i % 5 == 0 || i % 3 == 0 {
                sum += i;
            }
        }
        sum
    }

Using cargo bench and Criterion, the benchmark output:

Euler 1/For Loop time: [2.0562 us 2.1070 us 2.1765 us]

To give a point of comparison, I wrote the next solution using a simple iterator. Rust contains many "zero-cost abstractions," so I predict that the iterator approach should provide the same performance.

pub fn euler_1_iter(limit: u32) -> u32 {
        (1..limit).filter(|i| i % 5 == 0 || i % 3 == 0).sum()
    }

As expected, the benchmark output agrees, showing virtually no change in performance:

Euler 1/Iterator time: [2.0246 us 2.1309 us 2.2494 us]

Not bad for a one-liner, but can it be improved? Sticking to the iterator approach, I next reached for another popular Rust library, Rayon. Rayon provides easy to use methods for parallel computation. With one insertion of the into_par_iter method, this function is now parallel.

pub fn euler_1_par_iter(limit: u32) -> u32 {
        (1..limit).into_par_iter().filter(|i| i % 5 == 0 || i % 3 == 0).sum()
    }

Euler 1/Parallel Iterator time: [39.087 us 44.793 us 52.946 us]

What happened? Well, given the limit of only 1000, the jump to parallel processing is not only not needed, it's detrimental to performance. I'll keep this type of solution in mind for future problems, however.

pub fn euler_1_loop(limit: u32) -> u32 {
        let mut sum = 0;
        let mut threes = 3;
        let mut fives = 5;

        while threes < limit {
            sum += threes;
            threes += 3;
        }

        while fives < limit {
            sum += fives;
            fives += 5;
            if fives >= limit { break }
            sum += fives;
            fives += 10;
        }

        sum
    }