Re^2: Largest palindrome number for a 3 digit product of 2 numbers

Thanks . Have some confusion here . If none of the condition in the Inner Loop satisfies , Does the loop continue to execute the next iteration of the Outer loop or Is in't supposed to repeatedly execute the inner loop for each of the value of Inner loop ($i here)

I have added a print debugger statement in the Inner for loop and here is what I get for the first few iterations

So 999 x 999 doesn't satisfy the conditions in the Inner Loop and I was then expecting i to be 999 and j to be 998 , But I see the print giving I as 998 and j as 999 .. Can you please help walkover this algorithm if possible ?

  my $c = 0;
  I: for (my $i = $max; $i >= $min; $i--) {
 J: for (my $j = $max; $j >= $i; $j--) {
        my $prod = $i * $j;
        $c++;
        print "Iteration: $c, I: $i, J: $j Product: $prod\n";
..............
.............

Iteration: 1, I: 999, J: 999 Product: 998001
Iteration: 2, I: 998, J: 999 Product: 997002
Iteration: 3, I: 998, J: 998 Product: 996004
Iteration: 4, I: 997, J: 999 Product: 996003
Iteration: 5, I: 997, J: 998 Product: 995006
Iteration: 6, I: 997, J: 997 Product: 994009
Iteration: 7, I: 996, J: 999 Product: 995004
Iteration: 8, I: 996, J: 998 Product: 994008
Iteration: 9, I: 996, J: 997 Product: 993012
[download]

Comment on Re^2: Largest palindrome number for a 3 digit product of 2 numbers Download Code

Replies are listed 'Best First'.
Re^3: Largest palindrome number for a 3 digit product of 2 numbers by salva (Canon) on Jul 06, 2017 at 07:52 UTC
Multiplication is a commutative operation (ab and ba are the same quantity). That means that we can eliminate half of the operations making the inner `J` loop stop when `$j` becomes lesser than `$i`. You can see that explicit as the condition of the `J` loop. Other trick used to trim the search space is taking into account that for natural numbers if a >= b then ac >= bc, so as soon as we found a `$j` that makes a palindrome we can stop the `J` loop. Finally whatever becomes `$prod <= $best` we can also stop `J`; or even `I` if `$j` is still at 999.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: Largest palindrome number for a 3 digit product of 2 numbers
by salva (Canon) on Jul 06, 2017 at 07:52 UTC

J

$j

$i

J

Other trick used to trim the search space is taking into account that for natural numbers if a >= b then a*c >= b*c, so as soon as we found a $j that makes a palindrome we can stop the J loop.

Finally whatever becomes $prod <= $best we can also stop J; or even I if $j is still at 999.

[reply]
[d/l]
[select]