[tpm] russian peasant multiplication
Dave Doyle
dave.s.doyle at gmail.com
Wed Jul 22 07:21:47 PDT 2009
I know at least one other monger has seen this:
http://thedailywtf.com/Articles/Programming-Praxis-Russian-Peasant-Multiplication.aspx
Anyone take a crack at it? I did just for fun... and a desperate need
to do something other than PHP right now. It can, of course, be made
much shorter. I used a hashref with left and right keys to make it a
little easier to read instead of just using arrayrefs.
#!/usr/bin/perl
use strict;
use warnings;
use Test::More qw(no_plan);
# russian peasant multiplication
sub rpm {
my @data = ({
left => abs(int(shift)),
right => abs(int(shift)),
});
return 0 unless $data[0]{left} && $data[0]{right};
# half the left, double the right
while (1) {
my $row = $data[$#data];
last if $row->{left} == 1;
push(@data, {
left => int($row->{left} / 2),
right => $row->{right} * 2,
} );
}
# calc total by adding right columns to total where left is odd
my $total = 0;
$total += ( ($_->{left} % 2) == 0 ? 0 : $_->{right} ) foreach @data;
return $total;
}
my @pairs = ( [11,12], [13,14],[999,1],[4252,5723], [0,1],[1,0],[0,0]);
is(
rpm(@{$_}),
$_->[0] * $_->[1],
"$_->[0] * $_->[1] = " . $_->[0] * $_->[1]
) foreach @pairs;
--
dave.s.doyle at gmail.com
More information about the toronto-pm
mailing list