[tpm] russian peasant multiplication

[Dave Doyle]

and once more recursively:

#!/usr/bin/perl

use strict;
use warnings;
use Test::More qw(no_plan);

# russian peasant multiplication
sub rpm {
    my $left = abs(int(shift));
    my $right = abs(int(shift));

    return 0 if !$left || !$right;
    return $right if $left == 1;
    return ( ($left % 2) == 0 ? 0 : $right) + rpm(int($left/2),$right*2);
}

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



On Wed, Jul 22, 2009 at 10:21 AM, Dave Doyle<dave.s.doyle at gmail.com> wrote:
> 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
>