An Unreasonably Deep Dive Into Project Euler Problem 4

Or: How to make your solution 8000x faster with math and short-circuit evaluation.

Introduction

It has been a couple of years since my last Project Eueler effort, An Unreasonably Deep Dive into Project Euler Problem 3, and since I’ve also been wanting to do more work with Rust recently, I thought it would be a good opportunity to do both things at once by doing Project Euler problem 4 in Rust instead of my default of Go as before.

Problem Statement

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

The general approach to the solution will be to find a working version first (as always), then focus on making it faster by reducing the search space. Along the way, there are a couple of programming techniques we can employ for great speedups as well.

All of this results in the final version being about 8000x faster than the naive version.

For the full code, see the github repository.

Helper function(s)

To start with, we will need a function that tells us if a number is palindromic. This is not the most efficient way to write this helper function, but it works.

// We will need a helper function to determine if a number is palindromic
//
// is_palindromic_v1() will convert the number to a string, reverse the string, and compare that with the
// string representation of the number.
fn is_palindromic_v1(i: i32) -> bool {
    return i.to_string().chars().rev().collect::<String>() == i.to_string();
}

v0() - time required: ~102,000,000ns

As a naive/brute-force first version, let’s just multiply all three-digit numbers, check each time if the product is palindromic, keep it if it is, and continue that process until we have checked all products of three-digit numbers.

This is slow but it works.

// v0() is the naive attempt: multiply three-digit numbers.  When a palindromic number is found,
// if it's larger than the most recent palindromic number found then keep it.  Iterate until the end 999.
fn v0() -> i32 {
    let mut res = 0;
    for i in 100..=999 {
        for j in 100..=999 {
            let prod = i * j;
            if is_palindromic_v1(prod) && prod > res {
                res = prod;
            }
        }
    }
    return res;
}

v1() - time required: 7,300,000ns (~14x speedup from v0())

This isn’t really an algorithm change, but it is a slight change in the code that makes a massive performance difference. We are taking advantage of the Short-circuit evaluation present in Rust. This means that for a given sequence of arguments chained together with certain operators, like &&, the evaluation will take place from left to right and will terminate as soon as possible. This prevents the remaining elements in the sequence from being evaluated unnecessarily. In our case, that makes a big difference since we are iterating through many numbers and therefore would be executing is_palindromic_v1() many times. Since prod > res has a much lower computational cost than is_palindromic_v1(prod) and since prod > res happens sufficiently frequently, this cuts down runtime by a factor of 14.

// v1(): FUN FACT - Rust has short-circuit evaluation.
fn v1() -> i32 {
    let mut res = 0;
    for i in 100..=999 {
        for j in 100..=999 {
            let prod = i * j;
            // Note that this order changed.
            // Consequently, the right-hand side of the && is only evaluated if needed.
            // This is important since string casting and reversing is so slow and the search
            // space is so large.  Many languages have short-circuit/lazy evaluation.
            // This matters less as we start restricting the search space.
            if prod > res && is_palindromic_v1(prod) {
                res = prod;
            }
        }
    }
    return res;
}

v2() - time required: ~1,800,000ns (~57x speedup from v0())

If you think about it, starting at the lower end of the range and iterating all the way to the higher end does not make very much sense when looking for the largest product. The chances that the largest product will come from the lower end of the range are very small, so we should start the iteration from the large numbers and work our way down instead. This results in a much smaller search space since we break out as soon as we find the large palindromic number.

// v2(): Start from the biggest numbers, which makes a lot more sense.
fn v2() -> i32 {
    let mut res = 0;
    for i in (100..=999).rev() {
        for j in (100..=999).rev() {
            let prod = i * j;

            if prod > res && is_palindromic_v1(prod) {
                res = prod;
                break;
            }
        }
    }
    return res;
}

v3() - time required: ~1,050,000ns (~97x speedup from v0())

Now we start to take advantage of some convenient math. Since we are multiplying two numbers, and multiplication is a commutative binary operation, we know that we do not need to check p * q and q * p since they are the same. So if we get to a point in the evaluation where our product is less than the result we would currently return then we can also skip checking any smaller numbers that would come after that on the inner loop. This additional restriction of the search space gives us even more speedup.

// v3(): Now stop if result is greater than current product.  If you
// are multiplying and the product is smaller than the current number, you won't be
// able to get around the fact that p * q = q * p, so you can stop.
fn v3() -> i32 {
    let mut res = 0;
    for i in (100..=999).rev() {
        for j in (100..=999).rev() {
            let prod = i * j;

            if prod > res && is_palindromic_v1(prod) {
                res = prod;
                break;
            } else if res > prod {
                break;
            }
        }
    }
    return res;
}

v4() - time required: ~195,000ns (~517x speedup from v0())

Now we can reduce search space a little more by examining the general shape of our palindromic number in question, and doing some factoring. This leads us to the conclusion that we don’t need to check every factor, but only cases where one of the factors is divisible by 11. For details, see the code comment below.

// v4(): Note that the number is probably 6 digits, i.e. abccba = p * q where each letter is some number between 1 and 9
// then we can rewrite as a * 100000 + b * 10000 + c * 1000 + c * 100 + b * 10 + a * 1 = p * q
// which we can rewrite as a * 100001 + b * 10010 + c * 1100 = p * q
// which can be factored to 11 * (a * 9091 + b * 910 + c * 100) = p * q
// therefore p * q must be divisible by 11
// therefore either p or q must be divisible by 11.
//
// Since p or q must be divisible by 11, just start the iteration at 990 because it is
// the largest possible number in the given range that is also divisible by 11 and
// work our way down in steps of 11.
fn v4() -> i32 {
    let mut res = 0;
    for i in (100..=990).rev().step_by(11) {
        for j in (100..=999).rev() {
            let prod = i * j;
            if prod > res && is_palindromic_v1(prod) {
                res = prod;
                break;
            } else if res > prod {
                break;
            }
        }
    }
    return res;
}

Aside: finding palindromic integers

Our naive helper function for checking palindromic integers is convenient but inefficient.

It has to cast our integer to a string, reverse that string to make a new string, and then compare that to another string-casted version of our original integer.

Fortunately, there is a much faster way to determine if an integer is palindromic. We can just continually divide the original number by 10 and append the remainder on the right side of a new number each time to construct the reverse of the original number. If the new number and the original number match, then the number is palindromic.

This version is a ~16x speedup over the version that uses string reversal and comparison.

// is_palindromic_v2() will build up a new number `reverse` by shifting `reverse` one decimal place
// and adding the 10s place of the candidate number until no places are left in the candidate
// number.  In this way, `reverse` is constructed as the sequence of successive tens place numbers
// from the original candidate number.  This version is ~16x faster than is_palindromic_v1().
fn is_palindromic_v2(i: i32) -> bool {
    let mut reversed = 0;
    let mut number = i;

    while number > 0 {
        reversed = reversed * 10 + number % 10;
        number = number / 10;
    }
    return reversed == i || i == number / 10;
}

v5() - time required: ~13,000ns (~8000x speedup from v0())

This version loops 1627 times, a ~500x reduction from v0() and v1(). The ~500x overall reduction in search space, the short-circuit evaluation change, plus the ~16x reduction due to the improved method of palindromic number checking is what gets us to the ~8000x reduction relative to the initial version.

// v5(): Get rid of the slow string reversing and use the numerical palindrome helper function.
fn v5() -> i32 {
    let mut res = 0;
    for i in (100..=990).rev().step_by(11) {
        for j in (100..=999).rev() {
            let prod = i * j;

            if prod > res && is_palindromic_v2(prod) {
                res = prod;
                break;
            } else if res > prod {
                break;
            }
        }
    }
    return res;
}

Summary

While there are still some performance gains likely to be had, they would probably be nominal and require extensive effort. By simply pursuing our general problem solving strategy of reducing the search space, combined with a couple of domain knowledge improvements in the form of taking advantage of short-circuit evaluation and a different helper function to check if a number is palindromic, we were able to get an approximately 8000x speedup over the original naive version.