3
\$\begingroup\$

Update! I got a lot of pointers, suggestions and tips on improving the readability, structure and efficiency of my program yesterday, so I made the suggested improvements to the program and am happy to announce I managed to reduce the execution time of the program to nearly 1/25th! Still, I would love feedback on the improved state of my program. Thanks to everyone who commented on my previous post!

// Largest palindrome product (4)
#include <iostream>
#include <chrono>

bool is_palindrome(int num);
void compute_palindromes(void);
void save_palindrome(int i, int j, int val);
void log_palindrome(void);
void time_function(void (*func)(void), const char *desc);
void version_one(void);
void version_two(void);

struct Palindrome_storage {
    static int primary;
    static int secondary;
    static int palindrome;
};
int Palindrome_storage::primary = 0;
int Palindrome_storage::secondary = 0;
int Palindrome_storage::palindrome = 0;

int main(void) {
    time_function(version_one, "Program -- Version 1.0");
    time_function(version_two, "Program -- Version 1.1 (yesterday's code)");
    time_function(compute_palindromes, "Program -- All optimizations");
    log_palindrome();
    return 0;
}

bool is_palindrome(int num) { // Determine if a given number is a palindrome or not
    int original = num;
    int reversed = 0;
    while (num > 0) {
        reversed *= 10;
        reversed += num % 10;
        num /= 10;
    }
    return reversed == original;
}
void compute_palindromes(void) {
    int max_palindrome = 0;
    for (int i=999; i>99; --i) {
        if (i < max_palindrome/1000) break; // Optimalization
        for (int j=999; j>=i; --j) {
            int product = i*j;
            if ((product > max_palindrome) && is_palindrome(product)) {
                max_palindrome = product;
                save_palindrome(i, j, product);
                break;
            }
        }
    }
}
void save_palindrome(int i, int j, int val) { // Stores the largest palindrome found in a struct with static variables
    Palindrome_storage::primary = i;
    Palindrome_storage::secondary = j;
    Palindrome_storage::palindrome = val;
}
void log_palindrome(void) { // Outputs the largest palindrome found
    std::cout << "Largest palindrome: " << Palindrome_storage::primary << " * " << Palindrome_storage::secondary << " == " << Palindrome_storage::palindrome << std::endl;
}
void time_function(void (*func)(void), const char *desc) { // Time how long a function takes to execute
    double best_time;

    for (int i=0; i<100; i++) { // Multiple checks to find the lowest (should maybe be average) computing time
        auto begin_time = std::chrono::high_resolution_clock::now();
        func();
        auto end_time = std::chrono::high_resolution_clock::now();
        double elapsed_time = std::chrono::duration_cast<std::chrono::microseconds>(end_time - begin_time).count();
        if (i == 0) best_time = elapsed_time;
        else if (elapsed_time < best_time) best_time = elapsed_time;
    }

    std::cout << desc << ":\n";
    std::cout << "Elapsed time is " << best_time/1000000.0 << " seconds." << '\n' << std::endl;
}

// Previous versions
void version_one(void) {
    int largest_palindrome = 0;
    for (int i=999; i>99; i--) {
        for (int j=999; j>99; j--) {
            int product = i*j;
            if (is_palindrome(product) && product>largest_palindrome) {
                largest_palindrome = product;
            }
        }
    }
}
void version_two(void) {
    int largest_palindrome = 0;
    for (int i=999; i>99; i--) {
        for (int j=999; j>99; j--) {
            if (i < largest_palindrome/1000) { // Optimalization
                i = 0;
                j = 0;
            } else {
                int product = i*j;
                if (is_palindrome(product) && product>largest_palindrome) {
                    largest_palindrome = product;
                    j = 0;
                }
            }
        }
    }
}

Output:

Program -- Version 1.0:
Elapsed time is 0.037895 seconds.

Program -- Version 1.1 (yesterday's code):
Elapsed time is 0.003956 seconds.

Program -- All optimizations:
Elapsed time is 0.000153 seconds.

Largest palindrome: 913 * 993 == 906609
\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

static

Why a struct of static members? Seems awkward. You could instead have a static struct, and having 1 static is better than three:

struct Palindrome_storage {
    int primary;
    int secondary;
    int palindrome;
};
static Palindrome_storage palindrome_storage = { 0, 0, 0 };

static

Having no statics would be even better than 1 static. You could run variations of the algorithm on separate threads without fear of static variables colliding. You are simply returning data; why not just return the structure?

Palindrome_storage compute_palindromes(void) {
    ...
    return Palindrome_storage{ ..., ... , ...};
}

On the plus side, this reduces redundant work. product is being stored in two places: max_palindrome and Palindrome_storage::palindrome.

            max_palindrome = product;
            save_palindrome(i, j, product);

If you simply stored max_palindrome, primary & secondary as local variables, you store them all only once. And you can easily construct & return the structure from these locals.

struct

You don't really need a structure to hold these 3 integers. A std::tuple could work.

std::tuple<int, int, int> compute_palindromes(void) {
    ...
    return std::tuple<int, int, int>{ primary, secondary, max_product };
}

Although you've lost some nice naming the structure gave you.

Loop over the correct range limits

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

What does this loop mean? From 999 down to just before 99. Seems like 9's are significant, but why?

    for (int i=999; i>=100; --i) {

This is the same loop, but now we see we're going from 999 down to 100 inclusive. All of the 3-digit numbers. I think this is slightly clearer.

Optimizations

Why divide by 1000?

    if (i < max_palindrome/1000) break; // Optimalization
    for (int j=999; j>=i; --j) {

What is this optimization really doing for you? If i is less than max_palindrome divide by 1000? Where did that 1000 come from? What does it mean? And can we do better?

What you are really doing is testing against a limit. The maximum product you can form from i and a 3-digit number is i * 999. So why divide by 1000? Is that even correct? Is it too much? Is it not enough? Is this an off-by-one error? The following would be better, clearer, more correct, and if multiplication is faster than division, slightly faster:

    if (i*999 < max_palindrome) break; // Optimization

And yet, we can still do better. For a given value of i, what is the smallest value j can have, and still have i * j > max_palindrome?

    int lower_j_limit = max(i, max_palindrome / i);
    if (lower_j_limit > 999) break;
    for (int j=999; j>=lower_j_limit; --j) {

max_palindrome = 0

Is max_palindrome = 0 the correct initialization? You were testing i < max_palindrome/1000, which is means it was effectively i < 0. Now we're computing the lower limit with max_palindrome / i, which again starts off as 0. Perhaps, since we're looking for 6 digit palindromes, we should initialize max_palindrome = 99999.

It won't make a difference here. But it is something to remember to examine in future problems.

11 fold speed increase.

As L.F. pointed out, since for a 6-digit palindrome, \$abccba\$,

$$a - b + c - c + b - a = 0 = 11 * k, k \in \mathbb{Z}$$

then \$abccba = i * j\$ must be divisible by 11.

Since 11 is prime, when i is not divisible by 11, then j must be, so you can start j at 990, and decrement it by 11. Testing 1/11th of the values gives you an 11-fold speed increase. Of course, when i is divisible by 11, you must start j at 999 and go down by 1's, as usual.

is_palindrome

Your test for a palindrome is fine. Your algorithm reverses the digits of the number, and compares the reversed number to the original. But you are doing twice as much work as necessary.

Consider: When you are reversing 580085, you repeatedly remove the last digit from num, and add it to the last digit of reversed:

num    reversed
580085        0
 58008        5
  5800       58
   580      580  <-- These are equal!
    58     5800
     5    58008
     0   580085

Note the halfway point. After half of the digits have been removed, and reversed, the partial values should be equal if the number is a palindrome. To be general, we'd also have to handle the case of an odd number of digits, by testing for equality both before and after adding the extracted digit to the reversed value.

bool is_palindrome(int num) {
    if (num == 0) return true;
    if (num % 10 == 0) return false;
    int reversed = 0;
    while (num > reversed) {
        int digit = num % 10;
        num /= 10;
        if (num == reversed) return true;   // For odd number of digits
        reversed = reversed * 10 + digit;
        if (num == reversed) return true;   // For even number of digits
    }
    return false;
}

But in this problem, you know exactly how many digits you are expecting. Only six. So you only need to reverse the bottom 3 and compared these to the top 3. Reversing the bottom 3 digits can be done without any loops at all.

bool is_6_digit_palindrome(int num) {
    int top3 = num / 1000;
    int btm3 = num % 1000;
    int btm3_reversed = btm3 % 10 * 99  +  btm3 % 100  +  btm3 / 100;
    return top3 == btm3_reversed;
}

Derivation of the btm3_reversed left as exercise to student.

Tests

There is no guarantee that version_one and version_two are producing the correct results. They produce no output, return no value, and call functions with no side-effect. A truly aggressive optimizer might optimize these functions away completely, and your tests could show them executing in zero time.

\$\endgroup\$
4
  • \$\begingroup\$ You! Thank you! What you said about tuples (removing structs/statics) made a lot of sense and I think I understand it a lot better. The range limits also make sense, although not as important. However I don't quite understand why initializing max_palindrome as 0, why would that matter? Checking if i<0 still wouldn't return incorrect results? Half the amount of work for checking palindromes was clever, I never would have thought of that myself. \$\endgroup\$
    – Th3o4oR
    Commented Sep 3, 2020 at 13:51
  • \$\begingroup\$ The 11-fold speed increase would have been nice, although while I'm trying to optimise my program as much as possible, I'm also trying to keep it flexible and universal, able to work with other ranges of numbers as well. Thus, not restricting the palindromes to six digits (abccba) but potentially a lot more. With some of your revisions to my code I was able to shave another ~0.6ms off of execution time. \$\endgroup\$
    – Th3o4oR
    Commented Sep 3, 2020 at 13:56
  • \$\begingroup\$ Re: max_palindrome = 0. You originally check if (i < max_palindrome/1000) break;. This initially tests i < 0. If max_palindrome was initialized to 99999, then the test would initially check i < 99. My changes added a lower_j_limit = max_palindrome / i, and the lower limit again is initially 0, but with the 99999 initialization raises the limit to 100. Without other optimizations elsewhere, these limit improvements would speed the algorithm up. But as I said, "It won't make a difference here" because there are other things which impose these anyway. \$\endgroup\$
    – AJNeufeld
    Commented Sep 3, 2020 at 14:15
  • \$\begingroup\$ Keeping the algorithm general is a good worthy goal. But note that every even digit palindrome (aa, abba, abccba, abcddcba, ...) is divisible by 11, because the alternating digit sum will always sum to zero, which is a multiple of 11. So in your general purpose algorithm, you should detect the special case of an even number of digits, and apply the optimization for any even digit cases. It is still flexible & universal, but faster when certain conditions are detected. \$\endgroup\$
    – AJNeufeld
    Commented Sep 3, 2020 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.