Finding palindromic numbers most efficiently

Question

After reading why is my project euler #4 program not working?, I was contemplating the most efficient way to approach this (finding the target palindrome as early as possible).

Is this snippet about as efficient as it gets? I am only considering the merits of the logic, not the choice of language. It would be easier (but not as efficient) to brute-force it with two nested loops.

Also, is this logic common enough for it to have a name?

#!/usr/bin/perl
use strict;
$^W = 1;
$\ = "\n";

my ($n) = @ARGV;
$n = 3 if (! defined $n || $n < 2 || $n > 8);
my ($lo,$hi,$lm);
$lo = substr('10000000000',0,$n);
$hi = substr('99999999999',0,$n);
$lm = substr('100000000000000000000',0,$n*2);

my ($a,$b,$x) = ($hi,$hi);
for (;;) {
    $x = $a*$b;
    if ($x eq reverse $x) {
        print "$x is $a * $b" if ($x > $lm);
        last if ($n > 3); # show them all for small numbers
    }
    next if (!(--$a < $lo) & !(++$b > $hi)); # no short-cut operator here
    ++$a; --$b;
    print "  edge $a $b" if ($n < 3); # show edge for small numbers
    $a += $b; $b = int --$a/2; $a -= $b;
    last if ($a*$b < $lm);
}

Answer 1

What you have shown is twisted spaghetti code full of misguided micro-optimizations. Your algorithm is not at all obvious. This is it cleaned up, so that we can analyze it:

#!/usr/bin/env perl
use strict;
use warnings;
use feature 'say';

my $n = 3;
my $lo = 10**($n - 1);
my $hi = (10**$n) - 1;
my $smallest_product = 10**(2*$n - 2);
my $index = 0;

for (my $sum = 2*$hi; ; $sum--) {
    my $a = int $sum/2;
    my $b = $sum - $a;

    last if $a*$b < $smallest_product;

    while ($lo <= $a and $b <= $hi) {
        $index++;
        my $candidate = $a * $b;
        if ($candidate eq reverse $candidate) {
            say "$candidate = $a * $b (candidate $index)"
                if $candidate > $smallest_product;
            exit if $n > 2;
        $a--;
        $b++;
    }
}

For this specific problem, your algorithm is actually quite fast, and the solution is found very early. But the search method is flawed, and in the grand scale of things very inefficient.

The below image illustrates how you walk through your search space.

Your primary search direction is through the sums of \$a + b\$. Then you vary \$a\$ and \$b\$ for each constant sum within the bounds \$a, b \in [lo, hi]\$. This means that you visit every pair \$(a, b)\$ in the shaded area. The problem is that most of these \$(hi - lo)^2 / 2 > 400000\$ visited points will not form palindromic products – there are only \$1800\$ palindromes with 5 or 6 digits.

Since you visit all possible products, you will encounter many palindromes more than once (in total, roughly half of your results are duplicates).

You will not see all palindromes in descending order. For each sum, when you only vary \$a\$ and \$b\$, the products will descend since their product is largest when they are closest. But between different sums, there is no ordering.

Let's look at this in an example with smaller numbers. In the following table, I have entered the products of their coordinates:

5|              25  hi = 5
 |                  lo = 1
4|           16 20
 |
3|         9 12 15
 |
2|      4  6  8 10
 |
1|   1  2  3  4  5
 |
0|0__0__0__0__0__0_
  0  1  2  3  4  5

And this table looks at the descending sums and the order in which these sums find products:

SUM : SEQUENCE
 10 : 25
  9 : 20
  8 : 16, 15
  7 : 12, 10
  6 :  9,  8, 5
  5 :  6,  4
  4 :  4,  3
  3 :  2
  2 :  1

Oh look, we came across 4 twice! What a waste. Also, the total sequence of elements is 25, 20, 16, 15, 12, 10, 9, 8, 5, 6, 4, 4, 3, 2, 1 – note that 5 preceded 6. So if both 5 and 6 were solutions and we'd stop at the first solution, we would not have found the largest solution.

Given that this diagonal search has a few very important flaws (the first solution isn't guaranteed to be the largest solution), we could have used a far simpler search that shares all its advantages and shortcomings, e.g. searching primarily by descending \$a\$ value and secondarily by descending \$b\$:

Yes, this is exactly brute-forcing via two nested loops, but that is exactly equivalent to what your current algorithm is doing. The search space is the same, only the order is simplified.

---

I mentioned earlier that there are less than 2000 possible palindromes in that search space. In general, it would be far more efficient to generate these palindromes, and then check whether two integer factors \$a\$ and \$b\$ exist which fall inside certain bounds. Generating the palindromes is trivial (for a fixed length with nested loops, otherwise by recursion), the difficult part is calculating the divisors. A palindrome-driven search will need less than half as many iterations for this search space, but might (in this specific case) lose the race to the first palindrome by a few iterations.

Answer 2

Here, you first check if $x is palindrome, but then you will only print it if $x > $lm:

if ($x eq reverse $x) {
    print "$x is $a * $b" if ($x > $lm);
    last if ($n > 3); # show them all for small numbers
}

It would be more efficient to do the other way around, checking $x > $lm first:

if ($x > $lm) {
    if ($x eq reverse $x) {
        print "$x is $a * $b";
        last if ($n > 3); # show them all for small numbers
    }
}

With \$n = 3\$, this makes a big difference: it saves reversing $x 23602 times.

I also tried rewriting the reverse operation, somewhat inspired by the the duck's comment: instead of comparing an entire string with its reverse, it should be more efficient to compare its first half with the reverse of its second half:

sub is_palindrome {
    my ($word) = (@_);
    my $l = length($word);
    foreach my $i (0 .. $l / 2) {
        if (substr($word, $i, 1) ne substr($word, $l - $i - 1, 1)) {
            return;
        }
    }
    return 1;
}

Although this function does only half of the comparisons as in $x eq reverse $x, at least as interpreted code, this cannot compete with the speed of the compiled reverse function. Using this function the script runs much slower, unfortunately.