Palindrone tester

When I wrote this, I didn't even think about that point. I guess I forgot about the whole 3 digit requirement haha.

I wanted to iterate backwards because I figured I would find the largest palindrome that way. I originally had this so it stopped after finding the first palindrome, but then realized that wasn't going to work so I redid it. Currently, I don't think the direction of iterating matters.

After looking this up, there is actually some math behind palindromes. I had no idea about that.

EDIT:
Dropping the bottom 100 numbers took off half a second of run time.

Last edited on

See the edit to my previous post, too.

Hmm, I think I understand what you're saying. I guess these project require you to think about everything mathematically lol. I'm gonna give your idea a shot and come back with what I have

Oh, also I think you're spending too much time converting integers to strings. Even without the optimization I mentioned earlier, my program finishes in 136 ms. Try writing the conversion function yourself and using stack arrays.
You could also try comparing the factor to your current maximum before checking if it's a palindrome, since that's a much faster check.

Yet another optimization you can do is combine my last suggestion with your original downwards iteration. Since the largest factors are likely to be found near the upper right corner of the plane, by starting your search there you'll be able to reduce the search space more quickly.

Interesting, simply inlining the conversion function shaves off another half second on my work computer (which is slower than my personal, cant test that until tonight).

I'm currently experimenting with ways to to convert from int to string faster. I do believe most of my time is getting stuck there.

EDIT:
And adding -O3 flag on G++ does almost nothing. Takes off about .05 seconds on average.

Changing to this:

//Int to string
    std::stringstream ss;
    ss << n;
    std::string strProd = ss.str();

Actually speeds it up a bit. About .4 seconds. I remember reading about compiler optimisations if you kept variable declarations close to where they are used, but I assume to speed came from strProd being initialized on declaration. Also:

std::string strProd(ss.str());

Is actually slower. *Cough* Framework *cough*. I was kind of surprised about that. Figured initializing the value with the constructor would speed things up.

Sadly, I don't think I can squeeze any more speed out of sstream. Time for a new idea.

Last edited on

Holy shit! So I had a thought on this, and I don't even believe the results here. This had to be too good to be true. Tell me what is wrong here:

int main()
{
    unsigned long int product = 0, answer = 0;
    unsigned int operand1 = 0, operand2 = 0;
    for(unsigned int i = 999; i > 99; i--)
    {
        for(unsigned int j = i; j > 99; j--)
        {
            if((i + j) < (operand1 + operand2))
                    continue;
            else
            {
                product = i * j;
                if(is_palindrome(product) && product > answer)
                {
                        answer = product;
                        operand1 = i;
                        operand2 = j;

                }
            }

        }
    }

    std::cout << "Answer is: " << answer << "\tProduct of " << operand1 << " and " << operand2;
    return 0;
}

As you can see, I went back to the calculation loop. I had an idea that if (i + j) is less than (operand1 + operand2), then there's no way that that product is going to be greater than the current product, so that bypasses a lot of int to string conversions. The speed went from ~2.6 seconds average, to ~.125 second average. I was blown away.

EDIT:
It's actually running at roughly .05 now for some reason.

Last edited on

I'll go ahead and post the entire updated program, if anyone is interested and running it.

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

inline bool is_palindrome(unsigned long int n)
{
    //Int to string
    std::stringstream ss;
    ss << n;
    std::string strProd = ss.str();

    //Creates reversed copy.
    std::string reversed;
    int sz = strProd.size();
    for(int i = sz-1; i > -1; i--)
    {
        reversed.push_back(strProd[i]);
    }

    //Checks for palindrome
    bool palindrome = true;
    for(unsigned int i = 0; i < strProd.size(); i++)
    {
        if(strProd[i] != reversed[i])
        {
            palindrome = false;
            break;
        }
    }
    return palindrome;
}

int main()
{
    unsigned long int product = 0, answer = 0;
    unsigned int operand1 = 0, operand2 = 0;
    for(unsigned int i = 999; i > 99; i--)
    {
        for(unsigned int j = i; j > 99; j--)
        {
            if((i + j) < (operand1 + operand2))
                    continue;
            else
            {
                product = i * j;
                if((product > answer) && is_palindrome(product))
                {
                        answer = product;
                        operand1 = i;
                        operand2 = j;

                }
            }

        }
    }

    std::cout << "Answer is: " << answer << "\tProduct of " << operand1 << " and " << operand2;
    return 0;
}

EDIT:
Changed one line. Now consistently runs at .05 seconds.

Last edited on

Here is an example of what I did. I was really confused about how to handle a palindrome when I first typed this so I made more of a static function. It could be better to create a palindrome function that will accept any size variable and possibly use a vector instead of an array. But here is the code:

#include <iostream>

bool IsPalindrome(int number);

int main() {
    for (int i = 999; i > 900; i --)
        for (int j = 999; j > 900; j --)
            if (IsPalindrome(i * j)) {
                std::cout << i << " * " << j << " = " << (i * j) << "\n";
                i = 0;
                j = 0;
            }
    return 0;
}

bool IsPalindrome(int number) {
    int array[6];
    // number has 6 digits
    if (number / 100000 > 0) {
        array[0] = number / 100000;
        number %= 100000;
        array[1] = number / 10000;
        number %= 10000;
        array[2] = number / 1000;
        number %= 1000;
        array[3] = number / 100;
        number %= 100;
        array[4] = number / 10;
        number %= 10;
        array[5] = number / 1;
        number %= 1;
        if ((array[0] == array[5]) && (array[1] == array[4]) && (array[2] == array[3]))
            return true;
    }
    if (number % 10000 > 0)
        return false;
    return false;
}

I think the seperation of the number into an array/vector is a faster way to go. The compile time (on my netbook) is 0.281 seconds. I also think it's better to count down than it is to count up.

I do think it is better to decremement in the loops, as the highest palindrome is likely to be at the top.

Your inner for loop, you could have it as for (int j = i; j > 900; j --)
This would cut down on all of the duplicate calculations. Also, try inlining your palindrome function. I noticed a decent speed increase from it.

I managed to do this project right after I got back into C++ so the logic isn't the most obvious. Also, running on my netbook makes for a long runtime since it's a micro 1.6gHz processor. It was fast, 10 years ago, but I can't complain because I now have a small portable compiler =D

As for the inline, I want to optimize the Palindrome function before I worry about increasing the overall speed. If you find a way to test Palindrome...ness?...more effectively, let me see the code and I'll see if I can add to it. I <3 PE problems =)

I think when it comes down to testing palindromic numbers, you can either choose flexibility or speed. I would say my way is more flexible, but not as fast as yours.

And I just ran yours on my machine to test. You run at about 1/4 to 1/5 of the time as mine (yours runs at 0.01 seconds on average). I figured the division modulus way was going to be faster.

Last edited on

I know the string direction is just slower overall due to the amount of overhead. I think the best way to make mine more flexible is to just make a vector out of each position, and since it's only a palindrome, it doesn't matter if the first number is stored last or vise versa (12345 can be stored as 54321) since it's only creating a vector to test for palindrome.

I'd also suggest removing the bool variable from your function, it might save you a few ms over a long test. I like using multiple exit points in a function such as a long loop since it just makes sense to me.

I have an hour before I have to get ready for work, maybe I can type this up quickly.

I don't think vector is going to speed anything up. I have a feeling it'll have the same, if not worse, performance here.

Yea now that you mention it, I don't need that bool at all. It's not really doing anything.

Actually using the vector, it cut my time from 0.281 seconds down to .071 seconds. Here is my final code:

#include <iostream>
#include <vector>

bool IsPalindrome(int number);

int main() {
   for(int i = 999; i > 900; i --)
      for(int j = i; j > 900; j --)
         if(IsPalindrome(i * j)) {
            std::cout << i << " * " << j << " = " << (i * j) << "\n";
            return 0;
         }
   return 0;
}

bool IsPalindrome(int number) {
   std::vector<int> myPalindrome;
   while(number) {
      myPalindrome.push_back(number % 10);
      number /= 10;
   }
   for(unsigned int i = 0; i < myPalindrome.size() / 2; i ++)
      if(myPalindrome[i] != myPalindrome[myPalindrome.size() - i - 1])
         return false;
   return true;
}

I'm getting the same speeds on my computer. Using G++ 4.4 with the -o3 flag on.

G++ 4.6.2 with -o2 = .078s
G++ 4.6.2 with -o3 = .063s

It was weird, I was actually getting slower times with the -o3 parameter. I am just chalking that up to the netbooks processor though. It is running pretty hot right now too -.-

Volatile Pulse: You're cheating by using a priori knowledge about where the solution is. Using the same logic, the program could be made even faster:

#include <iostream>

int main(){
    std::cout <<"906609\n";
}

This uses all the optimizations I mentioned above. On my computer it takes less than 3 ms. on average. Most of the speed comes from minimizing the number of calls to is_palindrome() by reducing the search space as quickly as possible.

#include <ctime>
#include <iostream>
#include <algorithm>

typedef unsigned main_type;

main_type evaluated=0,
	is_palindrome_called=0;

bool is_palindrome(main_type n){
	is_palindrome_called++;
	if (!n)
		return 1;
	//Enough for 332-bit integers.
	char digits[100]={0};
	size_t s=0;
	while (n){
		digits[s++]=n%10;
		n/=10;
	}
	if (s<3)
		return 1;
	//reusing n:
	n=s/2+s%2;
	for (size_t a=0;a<n;a++)
		if (digits[a]!=digits[s-a-1])
			return 0;
	return 1;
}

struct result_t{
	main_type candidate,x,y;
};

#define N 999

result_t get(){
	bool found=0;
	result_t result;
	for (main_type x=N;x>0;x--){
		main_type end=99;
		if (found)
			end=result.candidate/x;
		for (main_type y=N;y>end;y--){
			evaluated++;
			if (found && x*y<=result.candidate)
				continue;
			if (!is_palindrome(x*y))
				continue;
			if (!found || x*y>result.candidate){
				result.candidate=x*y;
				result.x=x;
				result.y=y;
				found=1;
				end=result.candidate/x;
			}
		}
	}
	return result;
}

int main(){
	result_t r;
	clock_t t0=clock();
	const unsigned repeats=1000;
	main_type max_evaluated=0,
		max_is_palindrome_called=0;
	for (unsigned a=0;a<repeats;a++){
		r=get();
		max_evaluated=std::max(max_evaluated,evaluated);
		evaluated=0;
		max_is_palindrome_called=std::max(max_is_palindrome_called,is_palindrome_called);
		is_palindrome_called=0;
	}
	clock_t t1=clock();
	std::cout <<r.candidate<<std::endl;
	std::cout <<max_evaluated<<std::endl;
	std::cout <<max_is_palindrome_called<<std::endl;
	std::cout <<double(t1-t0)/repeats<<std::endl;
	return 0;
}

I understand what you're saying, and I am going to have to plop that into my IDE so I can see the syntax highlighting better, but I was more focused about getting the function correct. Also, a lot of that seems like it would make it do more work. I also have no clue what kind of computer you have, but my simple Hello World programs take 5 ms...