Finding product palindromes

Question

I am new to perl and want some help in tuning this script if possible cause it takes time if I increased my array. also if I use warnings I get a lot of warnings which I'm unable to handle. I'm using perl (v5.24.0) built for darwin-thread-multi-2level.

Here is an example of what I want to achieve: The number 886 is like 8*86 = 688, if we reverse it 886 which is the original number. Also the same for 920781, 9*20781 = 187029, reverse 920781, etc...

my $start_run = time();
use strict;
foreach (1..1000000000) {
   if ($_==reverse(substr($_, 0, 1) * substr($_, 1)))
      { print $_."\n" ;}
    if ($_==reverse(substr($_, 0, 2) * substr($_, 2)))
    { print $_."\n" ;}
    if ($_==reverse(substr($_, 0, 3) * substr($_, 3)))
    { print $_."\n" ;}
    if ($_==reverse(substr($_, 0, 4) * substr($_, 4)))
    { print $_."\n" ;}
    if ($_==reverse(substr($_, 0, 5) * substr($_, 5)))
    { print $_."\n" ;}
    if ($_==reverse(substr($_, 0, 6) * substr($_, 6)))
    { print $_."\n" ;}
    if ($_==reverse(substr($_, 0, 7) * substr($_, 7)))
    { print $_."\n" ;}
}
my $end_run = time();
my $run_time = $end_run - $start_run;
print "Time taken: ".$run_time." sec\n";

Answer 1

I want some help in tuning this script if possible cause it takes time if I increased my array

Yes, the script can be tuned. I will discuss optimizing you script at the end of this post.

The warnings pragma

also if I use warnings I get a lot of warnings which I'm unable to handle

Yes correct, you will get many warnings in case you add the statement use warnings. Using the warnings pragma is highly recommended, see for example:

• Why use strict and warnings?

• Why not use strict and warnings in Perl?

In short, the warnings pragma help you find bugs in your code. If you add the use warnings to the top of your program, the first warning you get is

Argument "" isn't numeric in multiplication (*) 

This happens because in the first iteration of the for loop, $_ will be equal to 1, and at line 4 of your program where you mulitply the substrings:

substr($_, 0, 1) * substr($_, 1))

the first substring will be "1" and the second will be the empty string "". When you try multiply with the empty string (and warnings are disabled) it will be converted silently to a zero, see perldata. To demonstrate:

$ perl -E 'say 1 + ""'
1

but if you turn on warnings (use the -w flag):

$ perl -wE 'say 1 + ""'
Argument "" isn't numeric in addition (+) at -e line 1.
1

you will get the warning Argument "" isn't numeric.

The next warning you get will be

substr outside of string

this happens because substr returns an undefined value if the substring is beyond either end of the string. In this case, substr will also produce a warning (if you have enabled warnings with use warnings). The reason why you get the warning is that $_ is equal to "1" and at line 6 of your script you try call substr $_, 2. To demonstrate:

$ perl -wE '$_="1"; my $s  = substr $_, 2'
substr outside of string at -e line 1.

The next warning you will get is:

Use of uninitialized value in multiplication (*)

This happens also at line 6, where you have

substr($_, 0, 2) * substr($_, 2)

Here the first substring will be "1" ( since $_ is equal to "1" in the first iteration of the for loop), whereas the second substring will be undefined, as discussed above. Now if you try multiply 1 * undef you will get 0, and a warning (if you have enabled warnings). To demonstrate:

$ perl -wE 'say 1 * undef'
Use of uninitialized value in multiplication (*) at -e line 1.
0

The problem with the code

From the above discussion, it should be clear that the problem with the code that causes the warnings are that it does not use substr correctly when the numbers ( i.e $_ in the for loop ) are less than 8 digits long. If the numbers are more than 8 digits long another problem arises. In this case, the problem is of logical nature in that the program will fail to check all possible palindromes. For example, for a 9 digit number there is no check

if ($_ == reverse(substr($_, 0, 8) * substr($_, 8))) { ... }

Fortunately, these problems can be solved easily using nested for loops:

for (1 .. $max_integer) {
    for my $length ( 1 .. ((length $_) - 1) ) {
        say if $_ == reverse (substr ($_, 0, $length) * substr ($_, $length) );
    }
}

Here, I have defined a variable $max_integer which should be set to the highest integer to check for. For your case, it should be set to 1 billion:

my $max_integer = 1_000_000_000;

The inner for loop takes care of all the if statements in your original code.

Programming style

In Perl there is more than one way to do it (TMTOWTDI). The language was designed with this idea in mind, in that it "doesn't try to tell the programmer how to program". Still, in my experience (I started programming Perl 3 years ago) there are certain programming style guidelines that have been adopted by the community. I have seen these programming styles in practice reading source code of CPAN modules and looking at answers at the Perl tag at stackoverflow.com. Some of these guidelines are described in perlstyle, in Chapter 21 of Programming Perl and in the book Perl Best Practices.

1. Put all use statements at the top of your program. Since all use statements occur at compile time, it often does not matter for the Perl interpreter where in the source file you place them¹. To demonstrate:

    $ perl -E 'say getcwd(); use Cwd'
   

   The above code works fine, even if use Cwd comes after its exported function getcwd is called in the code. However, the above code will likely confuse humans. You can read more about compile time versus run time in Chapter 16 of the book Programming Perl.

   Perl pragmas are a subclass of Perl modules that can have a lexical scope. Since these pragmas only stay in effect within the scope in which they are used, their position in the code is important also to the Perl interpreter. However, these pragmas are typically used at the package scope ( to enable them in the whole source file ), so pragmas are also commonly placed at the top of the source file, to enhance readability and maintainability for a humans.

   So for your use case, you should move the use strict to the top of the file, and add a use warnings below it (it also help for a human reader if you keep them in sorted order):

   use strict; 
   use warnings;
   

2. Variable naming conventions. I think snake_case is the most common style for a lexical variable, though I have seen many CPAN authors that have used camelCase naming convention. I also prefer snake_case since I believe it easier to read.

   Funny enough, I changed my habits several times during my career. I remember I used to make most of my variables camelCase in the beginning, and I could not understand why someone would prefer a variable name like $max_iterations instead of $maxIterations. Two things were disturbing me: first, I thought shorter names were better, and second, I didn't like the idea of using three keystrokes when I could use two keystrokes. However, the shift came after reading stuff and meeting other developers and seeing other people's code, I gradually realialized that code is read much more often than it is written and the benefits of improved readability far outweigh the disadvantage of typing an extra character. Also, I think it is wise to stick to the snake_case convention used by the majority of the Perl community, because consistency is a good thing.

   For your case, you already follow the snake_case naming convention for lexical variable (for example in the first line you have my $start_run = time()) so in my opinion: just keep it up.

3. Spaces around operators. I prefer

   if ($_ == gen_number()) { ... }
   

   or even

   if ( $_ == gen_number() ) { ... }
   

   to

   if ($_==gen_number()) { ... }
   

   The reason is that I find the former easier to read. Adding spaces around most operators is also advocated in perlstyle.

   For your case, you could consider adding more spaces around operators in your code.

4. Indent style. Placement of braces. In Perl "uncuddled elses" and "K&R" style for indenting control constructs is used and recommended almost exclusively (as far as I know). See wikipedia article on indent style and perlstyle. Example of K&R style with uncuddled elses:

   if ( $a == 1 ) {
       ....
   }
   else {
       ....
   }
   

   For you case, you have indentation that does not conform with this style. For example:

   if ($_==reverse(substr($_, 0, 1) * substr($_, 1)))
         { print $_."\n" ;}
   

   this should be better written to conform with the style guidelines as:

   if ( $_ == reverse (substr($_, 0, 1) * substr($_, 1)) ) {
       print $_ . "\n"; 
   }
   

Optimization

I cannot see how the Perl script itself can be made run substantially faster, however I think the algorithm can be programmed to run much faster in C than in Perl. If the algorithm is only part of a larger program in Perl, it is not necessary to convert the whole program to C. By using the CPAN module Inline::C you can incorporate small pieces of C code into a larger Perl program.

I tested this on Ubuntu 16.04, Perl version 5.22, and found that the version using Inline::C can be approximately 25 times faster than the pure Perl version. Example:

use feature qw(say);
use strict;
use warnings;
use Benchmark qw( cmpthese );
use Inline C => './ppalin_c.c';

my $max = 10_000;

my %sub_info = (
    c    => sub { ppalin_c( $max ) },
    perl => sub { ppalin( $max ) },
);

cmpthese( -3, \%sub_info );

sub ppalin {
    my ( $max ) = @_;

    for (1 .. $max) {
        for my $length (1 .. length($_) - 1) {
            say if $_ == reverse (substr ($_, 0, $length) * substr ($_, $length) );
        }
    }
}

where ppalin_c.c is:

void ppalin_c( int max ) {
    char buf[256];

    for ( int i = 1; i <= max; i++ ) 
    {
        int a = i;
        char *ptr = buf;
        do {
            int b = a % 10;
            a /= 10;
            *ptr++ = b + '0';
        } while ( a );
        int len = ptr - buf;
        for ( int j = 1; j < len; j++ ) 
        {
            int fact1 = getfactor( buf, j );
            int fact2 = getfactor( buf+j, len - j);
            int reverse = fact1 * fact2;
            int match = 1;
            char *ptr2 = buf + len;
            for (int k = 0; k<len; k++) 
            {
                int b = reverse % 10;
                reverse /= 10;
                if ( *--ptr2 != (b + '0') ) {
                    match = 0;
                    break;
                }
            } 
            if ( match ) printf( "%d\n", i );
        }
    }
}

int getfactor( char *ptr, int len ) 
{
    int pow = 1;
    int b = 0;
    while (len--) {
        int c = (*ptr++ - '0');
        b += c * pow;
        pow *= 10;
    }
    return b;
}

The output:

       Rate  perl     c
perl 97.5/s    --  -96%
c    2544/s 2509%    --

which shows that the C version is 2509% faster than the Perl version for this particular run.

Footnotes:

^{1. The position of use statements in the source file could be important for the interpreter in some special cases. For example, if compile time code in one module depended on compile time code in another module.}

Answer 2

I don't think you can do very much to make it faster, but I've fixed the warnings - which were caused by you taking sub-strings from strings that weren't long enough for the indices that you were using.

I've also abstracted out some repetition into another loop.

#!/usr/bin/perl

use strict;
use warnings;

my $start_run = time();

foreach (1 .. 1_000_000) {
  foreach my $length (1 .. length($_) - 1) {
    if ($_ == scalar reverse(substr($_, 0, $length) * substr($_, $length))) {
      print "$_\n";
    }
  }
}
my $end_run = time();
my $run_time = $end_run - $start_run;
print "Time taken: ".$run_time." sec\n";

It's still painfully slow though :-(

Update: To answer the questions in the comments.

1. Experienced Perl programmers will always have use strict and use warnings in their code. They are Perl's "safety nets". use strict turns on three separate safety checks - the most important of which is forcing you to pre-declare your variables and use warnings looks for a number of potentially problematic programming practices. The example I always use in training courses is that use warnings will tell you when you are trying to write to a filehandle which is open in read-only mode.
2. The advantages of my extra level of abstraction are harder to justify. But there was some obviously repetitive code which (to my mind at least) was crying out to be optimised. For example, there was a bug in this code (when we were taking substrings using invalid indices) - without the abstraction, that would have needed to be fixed in seven places.