Project Euler #4: Finding the largest palindrome that is a product of two 3-digit numbers

Question

Amateur c++ programmer here, working my way through the Project Euler problems (problem 4). I would love for someone to take a look at my ~40 lines of code and give suggestions on improving the effectiveness of the code, and how/what to change to better follow the general guidelines for the flow of a c++ program.

The task states as such: "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."

// Largest palindrome product (4)
#include <iostream>
#include <time.h>
bool is_palindrome(int &num) { // Determine if a given number is a palindrome or not
    int reverse=0, copy=num, digit;
    do {
        digit = copy % 10;
        reverse = reverse*10 + digit;
        copy /= 10;
    } while (copy != 0);
    return (reverse == num);
}
int main(void) {
    double time_spent = 0.0;
    clock_t begin = clock();

    int largest_palindrome = 0;
    for (int i=999; i>99; i--) {
        for (int j=999; j>99; j--) {
            if (i < largest_palindrome/1000) { // Optimalization
                // std::cout << "Any value lower than " << i << " will, when multiplied by 999, never exceed the largest palindrome (" << largest_palindrome << ")."<< '\n';
                std::cout << "No larger palindromes possible." << '\n';
                i = 0;
                j = 0;
            } else {
                int product = i*j;
                if (is_palindrome(product) && product>largest_palindrome) {
                    std::cout << "Found palindrome! " << i << " * " << j << " == " << product << '\n';
                    largest_palindrome = product;

                    // More optimalization (no product of the current iteration of i can be larger than the current palindrome, so skip to next iteration)
                    j = 0;
                }
            }
        }
    }

    // Program execution time
    clock_t end = clock();
    time_spent += (double)(end - begin) / CLOCKS_PER_SEC;
    std::cout << "Elapsed time is " << time_spent << " seconds." << std::endl;
    return 0;
}

Answer 1

Here are some suggestions in addition to the existing answers.

<chrono>

In general, the C++ std::chrono API is more flexible and type-safe than the C functions in <ctime>, so consider using std::chrono to time the function.

is_palindrome

In C++, it is usually not advised to declare multiple variables on one line. Taking small types like int by value is more efficient than by reference and gives you a free copy to use. To prevent errors, I would also add an assertion to ensure that the input is a nonnegative integer:

bool is_palindrome(int number) {
    assert(number >= 0);

    int original = number;
    int reversed = 0;

    while (number > 0) {
        reversed *= 10;
        reversed += number % 10;
        number /= 10;
    }

    return reversed == original;
}

Note that your version suffers from overflow problems for certain large values of number, which this version does not fix.

Mathematical optimizations

By analyzing the problem mathematically, some optimizations can be achieved. The largest product of two 3-digit numbers is \$ 999 \times 999 = 998001 \$, so the answer will be at most a six-digit number. For now, let's just assume that the answer is \$ \ge 900000 \$. Thus, the palindromes are restricted to the form \$ 9abba9 \$, where \$a\$ and \$b\$ are single-digit numbers.

By applying the divisibility rule for \$11\$, we see that \$ 9abba9 \$ is a multiple of \$11\$. Therefore, at least one of the 3-digit factors is a multiple of \$11\$ — we'll call this factor the primary factor. Since the product is an odd number, the primary factor is odd as well, so we can start from \$979\$, the largest odd 3-digit multiple of \$11\$, and subtract \$22\$ at a time. Our search would stop if the primary factor becomes lower than \$900\$, since \$899 \times 999 = 898101 < 900000\$, meaning our assumption would be invalid.

Here's my result:

#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>

bool is_palindrome(int number) {
    assert(number >= 0);

    int original = number;
    int reversed = 0;

    while (number > 0) {
        reversed *= 10;
        reversed += number % 10;
        number /= 10;
    }

    return reversed == original;
}

int main() {
    int max_product = INT_MIN;

    for (int primary = 979; primary >= 900; primary -= 22) {
        for (int secondary = 999; secondary >= 900; secondary -= 2) {
            int product = primary * secondary;

            if (is_palindrome(product)) {
                max_product = std::max(product, max_product);
                break; // break out of the inner loop
            }
        }
    }

    if (max_product < 900000) {
        std::cout << "No result >= 900000\n";
    } else {
        std::cout << "Found: " << max_product << '\n';
    }
}

(wandbox)

The result is 906609, which is correct.

Answer 2

Why is the parameter to is_palindrome a reference? It should just be int n since it is a built in type (i.e., not large) and you don't want to change the value passed from the caller.

The declaration of time_spent can be at near the end of main since that's the only place you use it. Initializing it to 0 then adding a single value to it is just an assignment, and you should declare variables as close to the point of first use as possible.

auto time_spent = double(end - begin) / CLOCKS_PER_SEC;

Note that I've also changed the cast from a C-style cast to a constructor style.

In far as the big double loops, there is no point in testing values of i * j that have already been tested (if j > i you've already tried that case when the two values were swapped). So j should start at i and decrease. However, since the goal is the largest palindrome, you should start j at 999 and end that loop when it is less than i. This will quickly work thru multiples of the larger numbers.

The check for no larger palindromes possible should be lifted out of the inner loop, and performed before you run the j loop. Its value does not need to be checked on every iteration of the j loop because it won't change. When you do change largest_palindrome you break out of the inner loop and won't execute the check. The '\n' character used in this message can be included in the message string.

Instead of ending a loop by setting the index to 0 (j = 0;), use a break; statement. With the optimization check made in the outer loop, you don't need to break out of two loops.

In the "found palindrome" message, consider replacing the '\n' with std::endl(). This will flush the output and let you see the message immediately. It will increase the execution time, but depending on how long this runs and how frequent palindromes are found having the faster feedback displayed on a console may be useful. But when running on the challenge site using it could be detrimental.

Answer 3

Much of this comes from what 1201ProgramAlarm mentioned.

Notably, changing:

if (is_palindrome(product) && product > largest_palindrome)

Into:

if ((product > largest_palindrome) && is_palindrome(product))

produces an 8x speedup!

This is because, now, the "lightweight" test is performed first, and, due to "short circuit" evaluation of the if, the [heavyweight] is_palindrome call is suppressed.

---

To minimize the effects of outputing to std::cout, I've added a "solution" struct that remembers i, j, and product and prints all results at the end of a given test. (i.e.) We're timing just the algorithm and not the algorithm plus the I/O time.

I've also added a timeit function and moved the actual code into functions so multiple algorithms can be compared. timeit also runs the test algorithm multiple times and takes the shortest time to minimize the effects of timeslicing.

I've shown a progression of improvements.

Anyway, here's the refactored code:

// Largest palindrome product (4)
#include <iostream>
#include <time.h>

struct sol {
    int i;
    int j;
    int product;
};

int solcnt;
sol solvec[100];

#define SAVE \
    do { \
        sol *sp = &solvec[solcnt++]; \
        sp->i = i; \
        sp->j = j; \
        sp->product = product; \
    } while (0)

// Determine if a given number is a palindrome or not
bool
is_palindrome(int num)
{
    int reverse = 0,
        copy = num,
        digit;

    do {
        digit = copy % 10;
        reverse = reverse * 10 + digit;
        copy /= 10;
    } while (copy != 0);

    return (reverse == num);
}

void
timeit(void (*fnc)(void),const char *reason)
{
    clock_t best = 0;

    for (int iter = 0;  iter <= 100;  ++iter) {
        clock_t begin = clock();

        solcnt = 0;
        fnc();

        clock_t end = clock();
        clock_t dif = end - begin;

        if (iter == 0)
            best = dif;

        if (dif < best)
            best = dif;
    }

    std::cout << '\n';
    std::cout << reason << ':' << '\n';

    for (sol *sp = solvec;  sp < &solvec[solcnt];  ++sp) {
        std::cout << "Found palindrome! " << sp->i << " * " << sp->j << " == "
            << sp->product << '\n';
    }

    double time_spent = double(best) / CLOCKS_PER_SEC;
    std::cout << "Elapsed time is " << time_spent << " seconds." << std::endl;
}

void
fix1(void)
{
    int largest_palindrome = 0;

    for (int i = 999; i > 99; i--) {
        for (int j = 999; j > 99; j--) {
            // Optimalization
            if (i < largest_palindrome / 1000) {
                //std::cout << "No larger palindromes possible." << '\n';
                i = 0;
                j = 0;
            }
            else {
                int product = i * j;

                if (is_palindrome(product) && product > largest_palindrome) {
                    SAVE;

                    largest_palindrome = product;

                    // More optimalization (no product of the current iteration
                    // of i can be larger than the current palindrome,
                    // so skip to next iteration)
                    j = 0;
                }
            }
        }
    }
}

void
fix2(void)
{
    int largest_palindrome = 0;

    for (int i = 999; i > 99; i--) {
        // Optimalization
        if (i < largest_palindrome / 1000) {
            //std::cout << "No larger palindromes possible." << '\n';
            break;
        }

        for (int j = 999; j > 99; j--) {
            int product = i * j;

            if (is_palindrome(product) && product > largest_palindrome) {
                SAVE;

                largest_palindrome = product;

                // More optimalization (no product of the current iteration
                // of i can be larger than the current palindrome,
                // so skip to next iteration)
                j = 0;
            }
        }
    }
}

void
fix3(void)
{
    int largest_palindrome = 0;

    for (int i = 999; i > 99; i--) {
        // Optimalization
        if (i < largest_palindrome / 1000) {
            //std::cout << "No larger palindromes possible." << '\n';
            break;
        }

        for (int j = 999; j > 99; j--) {
            int product = i * j;

            if ((product > largest_palindrome) && is_palindrome(product)) {
                SAVE;

                largest_palindrome = product;

                // More optimalization (no product of the current iteration
                // of i can be larger than the current palindrome,
                // so skip to next iteration)
                j = 0;
            }
        }
    }
}

void
fix4(void)
{
    int largest_palindrome = 0;
    int largest_div1000 = 0;

    for (int i = 999; i > 99; i--) {
        // Optimalization
        if (i < largest_div1000) {
            //std::cout << "No larger palindromes possible." << '\n';
            break;
        }

        for (int j = 999; j > 99; j--) {
            int product = i * j;

            if ((product > largest_palindrome) && is_palindrome(product)) {
                SAVE;

                largest_palindrome = product;
                largest_div1000 = product / 1000;

                // More optimalization (no product of the current iteration
                // of i can be larger than the current palindrome,
                // so skip to next iteration)
                j = 0;
            }
        }
    }
}

int
main(void)
{

    timeit(fix1,"fix1 -- original");
    timeit(fix2,"fix2 -- moved i < largest_palidrome out of j loop");
    timeit(fix3,"fix3 -- reversed order of inner if");
    timeit(fix4,"fix4 -- removed divide by 1000 in loop");

    return 0;
}

Note that solvec is a simple array. It might be replaced with std::vector [or std::array], but since it's just test jig code, I didn't bother.

---

Here's the program output:

fix1 -- original:
Found palindrome! 995 * 583 == 580085
Found palindrome! 993 * 913 == 906609
Elapsed time is 0.001755 seconds.

fix2 -- moved i < largest_palidrome out of j loop:
Found palindrome! 995 * 583 == 580085
Found palindrome! 993 * 913 == 906609
Elapsed time is 0.001668 seconds.

fix3 -- reversed order of inner if:
Found palindrome! 995 * 583 == 580085
Found palindrome! 993 * 913 == 906609
Elapsed time is 0.000219 seconds.

fix4 -- removed divide by 1000 in loop:
Found palindrome! 995 * 583 == 580085
Found palindrome! 993 * 913 == 906609
Elapsed time is 0.000222 seconds.

Answer 4

The is_palindrome function is nice. The long main is not so nice. It's doing 3 things:

• computing the desired value
• printing out the result
• timing the algorithm.

I think it's best if you can keep your functions to do just one thing. Extracting a function that just returns the answer you want could be a good first step.

Answer 5

You have a brute force solution as 90% of 3 digit number are not palindromes.

More optimal is to first generate a list of 3 digit palindromic numbers and then check their products, starting with the high numbers.

Of note is that a 3 digit palindromic number has the form ABA which is much easier to generate than to check every number.