10
\$\begingroup\$

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;
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ FYI, a lot of the Euler projects have mathematical solutions that do not require any iteration. Most of the questions are designed so that you can attempt to figure out the mathematical "trick" involved. \$\endgroup\$ Aug 30 '20 at 19:46
  • 1
    \$\begingroup\$ @PaulMcKenzie Would you figure out and explain to simpler folks the mathematical trick involved, in this special case? Thank you! \$\endgroup\$ Aug 31 '20 at 14:37
  • \$\begingroup\$ @ProfessorVector Paul may have one in mind, but it seems a little out of scope. I hate to be "that guy," but you can Google this to see if anyone else has found "tricks" to it rather than brute force attempts. I only mention it because A) This is a very well known set of problems, others probably have discussed it B) The poster of this question may want to avoid "spoilers" for better solutions. I see they included a timer so they may be trying to optimize it for speed (again, maybe not, but they didn't explicitly ask to help make it faster is why I say this). \$\endgroup\$ Aug 31 '20 at 18:53
  • \$\begingroup\$ Note: A followup question appears here \$\endgroup\$
    – AJNeufeld
    Sep 1 '20 at 16:30
11
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Also the one's digits for the two multiplicands must multiply to a number ending in 9. That is (1,9), (9,1), (3,3), (7,7) \$\endgroup\$
    – qwr
    Aug 31 '20 at 6:06
  • \$\begingroup\$ "meaning our assumption would be invalid." - Well, a priori that assumption is unjustified and might miss the solution. In the end, you are "lucky" \$\endgroup\$ Aug 31 '20 at 17:53
  • 3
    \$\begingroup\$ @HagenvonEitzen: If we change the message from "No result found" to "Assumption that there is an answer above 900000 is incorrect", would you be satisfied? \$\endgroup\$ Aug 31 '20 at 18:44
  • \$\begingroup\$ @HagenvonEitzen Indeed, if the assumption turns out to be invalid, we need to perform another search with different optimization methods. A better phrasing might state that this search finds solutions above 900000. I've modified the output message. \$\endgroup\$
    – L. F.
    Sep 1 '20 at 2:15
9
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ This is exactly the kind of answer I was hoping for! Thank you for taking the time to review my code, kind stranger. You make some excellent points (tweaks that completely went over my head but make so much sense in hindsight), and I thank you. Regarding the execution time, this program takes about 0.005 seconds to execute (not counting command line output), so flushing the output stream (buffer? I'm can't quite remember which is which) so palindromes are shown immediately wouldn't really matter. Again, thank you! \$\endgroup\$
    – Th3o4oR
    Aug 30 '20 at 20:39
7
\$\begingroup\$

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.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I would try to get rid of the macro. You can use a std::vector<sol> with a large enough reserved capactiy, and instead of SAVE you can then write solvec.push_back({i, j, product}), which should then be almost as efficient. \$\endgroup\$
    – G. Sliepen
    Aug 31 '20 at 6:35
4
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ The 3-digit numbers don't have to be palindromes; only the product of the two 3-digit numbers needs to be a palindrome. Moreover, if you just use 3-digit palindrome numbers, you will not find the correct answer. Furthermore, this answer does not provide any review of the OP's actual code, which is a requirement for answers on this Code Review site. \$\endgroup\$
    – AJNeufeld
    Aug 31 '20 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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