[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