UnPerlish UnLaziness

Every now and then you come across other people's code. Perl being Perl this means that it can range from brilliantly obscure over brilliantly clear to brilliantly hillarious.

The first kind you ignore, the second kind you nod off and the encounter of the third kind you normally mock.

But not today. Today we look at addition of numbers. analyzing the following routine which is supposed to add a number to a big number:

sub add {
    my ( $big_num_str, $to_add) = @_;

    return ....
}

The big number $big_num_str is handed in as string as these can have an arbitrary length. The number $to_add is a normal Perl scalar. The routine is supposed to be invoked via

print add ("23", 10000018) ;

just to return

10000041

Look Ma: I Can Do It All By Myself

Well, the first obvious observation is that there is actually a well-tested, longstanding solution for this on CPAN: Math::BigInt . And that would even deal with negative numbers correctly.

But one trait of non-Perl programmers is that they are eager, in contrast to lazy Perl programmers. Eager to reinvent the wheel. These people also do not shy away to open sockets, just to launch an HTTP request. And they are even proud of that.

Look Ma: I am Writing Loops!

The way the programmer - I am thinking Java, but am politely writing PHP ... just to be doubly mean ... though normally mean for me - proceeds is to first generate the digits as list, with the least significant digit first:

my @big_num = split(//, reverse($big_num_str));

Then the first digit is added to the number, a new digit produced and the rest carried over:

my $i = 0;
## adding the number with array
for($i = 0; $i <= $#big_num  ; $i++){
    my $tmp = $big_num[$i] + $to_add;
    $big_num[$i] = $tmp % 10;
    $to_add = int( $tmp / 10 );
}

Now $to_add may contain still significant digits. They have to be appended to the @big_num array:

while($to_add){
    $big_num[ $i++ ] = $to_add % 10;
    $to_add = int( $to_add / 10 );
}

At the end the digits have be glued together and returned in reverse order:

return reverse( join("", @big_num) );

Easy enough, you say?

Why Not a Single Line?

Let's see how we can sanitize this. What are your guesses how short we can make it? Without scrolling down, that is.

The first cheap trick is to remove the second loop. It is pretty retarded to split the $to_add into its digits, just to add them character by character to the @big_num list. So this becomes

return $to_add . reverse join("", @big_num);

If you are concerned that $to_add gives you a leading 0, then a more sophisticated ($to_add or "") will protect you from that.

4 lines less.

The explicit join is lovely, but completely superfluous. What also works is to take the list, reverse it, and then interpret it in scalar context. And concatenation provides scalar context:

return ($to_add or "") . reverse @big_num;

Sic.

Mopping, mopping

But also the first loop is pretty artificial. It can be easily rewritten into

my @big_num;
foreach my $d (split(//, reverse($big_num_str))) {
   ($d2, $to_add) = map { $_ % 10, int($_ / 10) }
                    ($d + $to_add);
   push @big_num, $d2;
}

Not only we got rid of the childish index, we also integrated the splitting into the loop. And it is also clearer what happens: After adding, two values are derived: one which is the new digit, the other the add carry.

2 more lines saved.

Looking at our solution we see that the driving data are the incoming digits and the result are digits too. So this is effectively a list to list operation. The modification of the $to_add variable is only a side-effect.

For list-to-list operations Perl has grep and map operators which allow to write

my @big_num =
    map {
        map { defined ($to_add = int($_ / 10)) and $_ % 10 }
        ($_ + $to_add)
    } split (//, reverse($big_num_str));
return ($to_add or "") . reverse @big_num;

For me the intention now is clearer, rather than meandering through any variable jungle.

And this is 5 lines (or so) and not 12. In fact, I would move the reverse up, just to make the procedure consistent:

my @big_num =
    reverse
    map {
        map { defined ($carry = int($_ / 10)) and $_ % 10 }
        ($_ + $carry)
    } split (//, reverse($big_num_str));
return ($carry or "") . @big_num;

I have also renamed the remaining variable appropriately, so that both actually mean what they say.

The Full Yards

You might also consider to get rid of the @big_num variable altogether and do everything in one go, as in

return ($to_add or "")
     . reverse map { ... } split (//, reverse($big_num_str));

The problem here is the side-effect for $to_add: First the second string of the concatenation would have to be computed. But that will not happen.

The closest thing of a one-liner would be

return reverse
   (
     ( map {                       # pass on digits
           map { defined ($to_add = int($_ / 10)) # carry
                 and $_ % 10 }     # produce one digit
           ($_ + $to_add)          # add digit to number
       }
       reverse split //, $big_num_str # split into digits
     ),
     reverse split //, $to_add     # split into digits
   );

but the split of $to_add is quite unnecessary, so I would leave it there.

And The Speed?

How do the two solutions compare in speed? Like everything in Perl this trivial to figure out:

use Benchmark qw(:all) ;
timethese(100000, {
    'His'  => 'add ("23", 10000018)',
    'Mine' => 'add2("23", 10000018)'
});

And that would show (abbreviated):

Benchmark: timing 100000 iterations
  His:   4 wallclock secs ( 4.24 usr ) 23529.41/s
  Mine:  2 wallclock secs ( 1.78 usr ) 55865.92/s

And Why Would I Care?

Not because I'm nice. Definitely not. >;->

Posted In

In the "Mopping, mopping"

In the "Mopping, mopping" section you should leave the return as

return ($to_add or '') . reverse @big_num;

because if you take out the reverse that will end up concatenating the size of @big_num to ($to_add or '')

Anonymous (not verified) | Fri, 05/08/2009 - 21:44

Re: you should leave the return

... ou should leave the return as

return ($to_add or "") . reverse @big_num;

You're right!

rho | Sat, 05/09/2009 - 06:26