7
\$\begingroup\$

This is my solution to Project Euler #4, which asks for the largest palindrome that can be made from a product of 2 3-digit numbers. I have done a brute force method, but it takes around 10-20 seconds to run. It works by looping through 2 variables, finding its product, and converting it to a string to check for palindromity. What steps can I take to improve the computational speed of this program?

#include <cmath>
#include <string>
#include <sstream>
#include <iostream>
int main()
{
int ans=0;
for(int i=100;i<1000;i++)
    for(int j=100;j<1000;j++)
    {
        int num_to_test=i*j;
        int num_of_digits=floor(log10(num_to_test))+1;
        string num_stringstream;
        ostringstream convert;
        convert << num_to_test;
        num_stringstream=convert.str();
        int counter=0;
        for(int i=0;i<num_of_digits;i++)
        {
            if(num_stringstream[i]==num_stringstream[num_of_digits-i-1])
            {
                counter++;
                if(counter==num_of_digits)
                    num_to_test>ans?ans=num_to_test:ans=ans;
            }
        }
    }
cout << ans << endl;
char quit;
cin >> quit;
}
\$\endgroup\$
  • \$\begingroup\$ How should I compile your code? \$\endgroup\$ – Caridorc Sep 4 '15 at 11:48
11
\$\begingroup\$

Speeding things up

There are several things you could do to speed things up:

  1. Instead of looping from 100..999, go from 999..100 instead. That way, if you find a palindrome, you can break from the j loop because any lower values of j will not beat the one you just found.
  2. Once you loop backwards, you can also check i*j versus the best answer you've found so far. If i*j <= best, you can break from the j loop.
  3. You don't have to use log10 to find the number of digits. Since you are already converting the number to a string, just use num_stringstream.length().
  4. The j loop can start at i instead of 999, because any j higher than i will already have been tested.

Cleaning things up

It would make your program look a lot more readable if you moved all of the palindrome checking logic to its own function.

This line here is very hard to read:

num_to_test>ans?ans=num_to_test:ans=ans;

Putting it all together

Here is what I think your code should look like. I removed the cin << quit part because I wanted to time the program without requiring user input.

#include <string>
#include <sstream>
#include <iostream>

bool is_palindrome(int num)
{
    ostringstream convert;
    convert << num;
    string num_stringstream = convert.str();
    int num_of_digits = num_stringstream.length();
    for (int i=0; i < num_of_digits; i++)
    {
        if (num_stringstream[i] != num_stringstream[num_of_digits-i-1])
            return false;
    }
    return true;
}

int main(void)
{
    int best = 0;
    for (int i = 999; i >= 100; i--)
    {
        for (int j = i; j >= 100; j--)
        {
            int num_to_test = i * j;

            if (num_to_test <= best)
                break;

            if (is_palindrome(num_to_test)) {
                best = num_to_test;
                break;
            }
        }
    }
    cout << best << endl;
}

Using gcc -O3, this program ran in 0.03 seconds on my computer as opposed to 1.06 seconds, for around a 30x speedup.

\$\endgroup\$
  • \$\begingroup\$ Is it bad to do the hard to read line if I just have an if statement with one command? (compiler wise, not readibility) Also, I really need that palindrome checking in my function instead of outside, because I am organizing my project Euler code as int prob1(){} int prob2(){} etc and additional functions would make a problem harder to find. Thanks for suggesting the reverse loops, they are intuitive and easy to understand. \$\endgroup\$ – Teoc Aug 18 '15 at 4:26
  • \$\begingroup\$ @VladimirLenin That hard to read statement was just a max in disguise. Simpler would be ans = num_to_test > ans ? num_to_test : ans;. Or if younhave the macro, ans = max(ans, num_to_text); \$\endgroup\$ – JS1 Aug 18 '15 at 4:52
  • \$\begingroup\$ Repeatedly constructing the ostringstream comes at a cost. Make it static and follow with the line convert.str("") to get another 30% speed up. \$\endgroup\$ – Keith Aug 18 '15 at 6:26
  • \$\begingroup\$ Also, more importantly for palindromes in general, both OP and this code check every digit twice. Change to iteration to i < num_of_digits/2 to only check once. \$\endgroup\$ – Keith Aug 18 '15 at 6:36
  • \$\begingroup\$ @Keith Good advice. I tried the code from 200_success's answer and got a very large speedup also. \$\endgroup\$ – JS1 Aug 18 '15 at 6:39
7
\$\begingroup\$

Your method of testing for palindromes uses floating point (for log10()) and stringification, both of which are inefficient. The following approach should be much faster:

#include <cstdlib>

long reverse(long n) {
    long m = 0;
    while (n) {
        ldiv_t divmod = ldiv(n, 10);
        m = 10 * m + divmod.rem;
        n = divmod.quot;
    }
    return m;
}

…

num_to_test == reverse(num_to_test)

Note that converting a number to a base-10 string of digits requires a similar sequence of divisions by 10; it's just hidden inside convert << num_to_test;.

I've used long instead of int because int is only guaranteed to hold numbers up to 32767, which is not enough for 999 * 999.

\$\endgroup\$
  • \$\begingroup\$ Is there any reason to use the ldiv_mod instead of just taking n mod 10 and adding 10 times to m? Also for me ints are 2^31-1, short ints are 2^15-1? Thanks for the reversing suggestion though, appreciate it. \$\endgroup\$ – Teoc Aug 18 '15 at 4:18
  • \$\begingroup\$ When doing n % 10 and n % 10, you're doing two divisions, and throwing away half the work each time. ldiv() is supposed to give you both results with one operation. \$\endgroup\$ – 200_success Aug 18 '15 at 4:36
  • 2
    \$\begingroup\$ int is commonly 32 bits these days, but the spec only guarantees that it is at least 16 bits. \$\endgroup\$ – 200_success Aug 18 '15 at 4:37
2
\$\begingroup\$

If you want to convert to string, then test whether the result is a palindrome, you can simplify the code quite a bit:

bool is_palindrom(long in) {
    auto b = std::to_string(in);
    auto half_len = b.length() / 2;
    return std::string(b.begin(), b.begin() + half_len) ==
           std::string(b.rbegin(), b.rbegin() + half_len);
}
\$\endgroup\$
0
\$\begingroup\$

JS1 provided a great answer, but on my system i got an 80% speed up by using the code i wrote below. My goal was to avoid using strings if possible and stick with integer values.

All of the points made by JS1 still stand, but instead of using

bool is_palindrome(int num)
{
    ostringstream convert;
    convert << num;
    string num_stringstream = convert.str();
    int num_of_digits = num_stringstream.length();
    for (int i=0; i < num_of_digits; i++)
    {
        if (num_stringstream[i] != num_stringstream[num_of_digits-i-1])
            return false;
    }
    return true;
}

to calculate whether or not a number is a palindrome i used a function to reverse the input number using integer operations (its somewhat falsely named palindrome since it technically only reverses any number input into it).

#include <ctime>
#include <iostream>

int palindrome(int x) 
{
    int n = 0;//dummy variable
    while (x) 
    {
        n *= 10; n += x % 10; x /= 10; //this function simply reverses the input x
    }
    return n;
}

int main() {

    //start clock stuff
    std::clock_t start;
    double duration;
    start = std::clock();
    //end clock stuff

    int final = 0; //final is our biggest value found so far

    for (int x = 999; x >= 100; --x) {
        for (int y = 999; y >= 100; --y) {

            const int n = x * y;

            if (n <= final) //if the number being checked is less than the current best then we dont bother seeing if its a palidrome (saves calcuation of reverse of number)
                break;   
            if (n == palindrome(n)) //if the number is the same as the reverse of the number
            {
                final = n; //update best number found
                break;
            }
        }
    }

    //print our output
    std::cout << final << std::endl;

    //finish clock stuff
    duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;

    //print time to run program
    std::cout<<"Elasped time: "<< duration <<'\n';

    return 0;
}

On my system using integer operations instead of string based ones and compiling with g++ i had an average time of 0.001 for my version and 0.0019 for JS1's version over 10 runs. Using the icc compiler i actually got slightly faster times for both programs, but the difference between them was similar.

Neither implementation is bad, but i think the one i submitted is worth looking at. The reversing done is a lot simpler (in my opinion) and should be faster on your computer as well.

\$\endgroup\$

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.