Hello again everyone. Time to tackle Project Euler question #4:

Question #4:

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.

Well, let’s see if we can’t crack this nut.

Prime: Like most of my attempts, I start with brute force and refine from there. The code:

double Run()
{
	int limit = 99;
	int max = 999;

	_int64 num1 = max, num2, total, biggest = 0;

	while(num1 > limit)
	{
		num2 = max;
		while(num2 > limit)
		{
			total = num1 * num2;
			if(total == Reverse(total) && total > biggest)
				biggest = total;

			num2--;
		}
		num1--;
	}

	return biggest;
}

_int64 Reverse(_int64 num)
{
	_int64 inv = 0;

	while (num > 0)
	{
			inv = inv * 10 + (num % 10);
			num = num / 10;
	}

	return inv;
}

Results:

Digits:        Speed:
3 digits       130 milliseconds
4 digits       18 seconds
5 digits       unknown
6 digits       unknown

First and foremost, I tried many different variations on the conversion and comparison of the variable “total”. When I first produced this code in VB so long ago, I converted the number to a string, reversed the string, compared them, and then converted back. That process ended up being much slower in C++. Instead, I simply use an algorithm to reverse the number. (The original algorithm can be found here. I modified it to use int64). At first, I assumed that since the variables num1 and num2 were ticking downward, that the first palindrome found would be the largest. After thinking on that a bit I realized that it wasn’t true, and had to write in the “biggest” variable and comparison. At this point, Prime finds the answer in 130 milliseconds. Just for comparison’s sake, I decided the find the largest palindrome number that is a result of the multiplication of two 4 digit numbers as well. The number 99,000,099 was found in 8 seconds.

Optimization 1: My first step was to reduce the amount of redundancy in the iterations. For instance, in the first series of iterations, 999 * 998 is tested. Then, the very first test of the second series of iterations is 998 * 999. This continues all throughout the iterations and adds many useless loops. Looking through the patterns of multiplication, you can see that since we multiply all numbers by 999 (num1) in the first series, num2 will not need to be 999. Then, in the second series, we multiply everything by 998, and so num2 will not need to be 999 or 998. Once this pattern is noticed, we can modify the algorithm to set num2 equal to num1 every series (not equal to 999). This drastically reduces the number of iterations performed. I won’t bother listing the code, just change the line “num2 = 999” to “num2 = num1”.

Results:

Digits:        Speed:                 Speed Ratio:
3 digits       64 milliseconds        1:2 (over prime)
4 digits       8 seconds              1:2.25 (over prime)
5 digits       unknown
6 digits       unknown

Optimization 1 found the solution to the question is 64 milliseconds (roughly 2 times as fast). It also found the solution to our larger problem in 8 seconds (roughly twice as fast again).

Optimization 2: This optimization is where the money’s at, and no real work needs to be done. Since we are not cycling down both iterators (num1 and num2) at the same time, the first palindrome number we find will be the largest. The result? We don’t need to test to see if the palindrome we found is the largest. This significantly reduces the time it takes to calculate.

double Run()
{
	int limit = 99;
	int max = 999;

	_int64 num1 = max, num2, total;

	while(num1 > limit)
	{
		num2 = num1;
		while(num2 > limit)
		{
			total = num1 * num2;
			if(total == Reverse(total))
				return total;

			num2--;
		}
		num1--;
	}

	return -1;
}

_int64 Reverse(_int64 num)
{
	_int64 inv = 0;

	while (num > 0)
	{
			inv = inv * 10 + (num % 10);
			num = num / 10;
	}

	return inv;
}

Results:

Digits:        Speed:                 Speed Ratio:
3 digits       664 microseconds       1:195 (over prime)
4 digits       22 microseconds        1:818181 (over prime)
5 digits       105 milliseconds
6 digits       64 milliseconds

The initial answer was found in 664 microseconds. The 4 digits palindrome was found in 22 microseconds. At this point I got adventurous and found the largest palindrome of 5 and 6 digit numbers. 5 digits were found in 105 milliseconds while 6 digits were found in 64 milliseconds. We now can see something interesting emerge. We are finding some more complicated number sets faster than some simpler number sets. For instance, 6 digits are found faster than 5 digits. This has to do entirely with how close the palindrome is to the “surface” (biggest num1 and num2). The algorithm started off increasing in time as the number sets increased. Now, the time required is indifferent to the size of the number sets (For the most part. Larger math still takes more time. If we could magically erase that factor, time would be completely independent of size).

Optimization 3: When I originally wrote this article many years ago, I stopped at optimization2. Since then I have learned a bit and decided to try and make it faster. Thus, I bring you optimization3. This optimization requires us to look at what a palindrome is. Let’s look at a simple 4 digit palindrome:

abba

Let us pretend the letters above represent some unknown numbers (like 1001, or 2332). We can represent this palindrome as:

1000a + 100b + 10b + a

Or

1001a + 110b

Now, we might be able to see that both 1001 and 110 are divisible by 11 (a prime) so let’s factor it out:

11(91a + 10b)

What this means to us is that at least one of the two numbers used to make any palindrome is divisible by 11. Don’t believe me? Let’s try an 8 digit palindrome:

abcddcba

Can be represented as:

10000000a + 1000000b + 100000c + 10000d + 1000d + 100c + 10b + a

Or

10000001a + 1000010b + 100100c + 11000d

Which is divisible by 11:

11(909091a + 90910b + 9100c + 100d)

Armed with this new knowledge, we can improve our algorithm:

double Run()
{
	int limit = 99;
	int max = 999;

	_int64 num1 = max, num2, total;

	while(num1 > limit)
	{
		num2 = max % 11 == 0? max : max - 9;
		while(num2 > limit)
		{
			total = num1 * num2;
			if(total == Reverse(total))
				return total;

			num2 -= 11;
		}
		num1--;
	}

	return -1;
}

_int64 Reverse(_int64 num)
{
	_int64 inv = 0;

	while (num > 0)
	{
			inv = inv * 10 + (num % 10);
			num = num / 10;
	}

	return inv;
}

Results:

Digits:        Speed:                 Speed Ratio:
3 digits       60 microseconds        1:11 (over optimization2)
4 digits       13 microseconds        1:1.6 (over optimization2)
5 digits       10 milliseconds        1:10 (over optimization2)
6 digits       130 microseconds       1:492 (over optimization2)

As you can see we need only start num2 as the largest multiple of 11 in the set and then decrease it by 11 each iteration. The largest multiple of 11 will alternate between max and max minus 9 (thus: 99, 990, 9999, 99990, etc.).  This algorithm saves us 11 tests every cycle. As a result we find out solution in 60 microseconds, we find 4 digits in 13 microseconds, 5 digits in 10 milliseconds, and 6 digits in an amazing 130 microseconds. I am sure we can do more with the palindrome insight we found above, but this will suffice for now.