The Daily WTF: Curious Perversions in Information Technology

2009-07-22 Reply Admin

Is anyone reading this far?

In Perl, implementing the algorithm as described, showing working:

#!/usr/bin/perl -w

use strict;

my $a = shift or die( "need arg 1" ); my $b = shift or die( "need arg 2" ); my $neg = ($a < 0 xor $b < 0) ? -1 : 1; my @nums; for ($a = abs $a, $b = abs $b; $a > 0; push(@nums,{'a'=>$a, 'b'=>$b}), $a >>= 1, $b <<= 1) {} map {print "$->{'a'} + $->{'b'}\n" } @nums; print( "###\n" ); @nums = grep {$->{'a'} % 2} @nums; map {print "$->{'a'} + $->{'b'}\n" ;$a += $->{'b'} } @nums; print( 'sum: ', $a * $neg, "\n" );

2009-07-22 Reply Admin

A Python solution. It could definitely be done in less code, but I'd rather be able to understand it.

import math

def russian_multiply(x, y):
    cols = [(x, y)]
    
    while True:
        x = int(math.floor(x / 2))
        y = int(math.floor(y * 2))

        cols.append((x, y))

        if x <= 1:
            break

    col_sum = sum([c[1] for c in cols if c[0] % 2 != 0])

    return col_sum

print russian_multiply(18, 23)

2009-07-22 Reply Admin

Pretty similar in C;

int l(int l1, int ll) { return l1&-2?l1%2ll+l(l1/2,ll2):ll; }

Looks kind of like a traffic accident, doesn't it?

ajp · 2009-07-22 Reply Admin

I didn't check to see if there was an F# one done yet or not. But here is my attempt.

F# Version 1.9.6.16, compiling for .NET Framework Version v4.0.20506
#light
let isOdd x = 
  (x%2) = 1

let rec mult x y = 
  match x with
  | 1 -> y
  | _ when isOdd x -> y + mult (x/2) (y*2)
  | _ -> mult (x/2) (y*2)

2009-07-22 Reply Admin

I was disturbed by the fact that the Perl uses the multiplication operator when it doesn't need to, so I offer:

sub rp_mult {
  my ($i, $j) = @_;
  my $r = 0;
  do {
    $r += ($j & 1) && $i;
    $i <<= 1;
    $j >>= 1;
   } while ($i);
   $r;
}

Or, moderately golfed:

sub rpmul{($r,$i,$j)=(0,@_);$r+=$j&1&&$i,$i<<=1,$j>>=1while$i;$r;}

Or, from a slightly different angle:

use List::Util 'sum';
sub rp_mult {
  my ($i, $j) = @_;
  sum map $j >> $_ & 1 && $i << $_,
    0 .. log $j / log 2;
}

2009-07-22 Reply Admin

python. Gratuitous use of list comprehensions and generators. Doesn't work for negative numbers. Patches welcome ;-)

a=22
b=66
import math
def half():
    aa=a
    while aa >=1:      
        yield aa
        aa= aa/2 
print sum([y for (x,y) in zip([x for x in half()],[b*(2**(x)) for x in range(0,len([x for x in half()])+1)]) if x%2==1])

2009-07-22 Reply Admin

fun pmulti 1 r t = t + r | pmulti l r t = pmulti (l div 2) (r * 2) (t + r * (l mod 2))

pmulti 3 4 0 will give you 3 * 4, t is just an accumulator

2009-07-22 Reply Admin

In Python:

a,b = 190, 232 if a<0: a=-a; b=-b print sum([b<<s for s in xrange(0,int(math.log(a,2)+1)) if ((a>>s>0) and ((a>>s)%2)) ])

2009-07-22 Reply Admin

def rpmult(a, b):
   rows = []
   while a > 1:
      rows.append( (a, b) )
      a, b = a >> 1, b << 1
   rows.append( (a, b) )
   return reduce(lambda (_, b1), (__, b2): b1 + b2, filter(lambda (a, _): a & 1, rows))

2009-07-22 Reply Admin

(Readable) Ruby version Handles negative numbers (and unlike some of the examples i read, returns correct signs)

class Rpm
  def self.multiply(x1,x2)
    ret = 0
    is_neg = false

    if x1 < 0
      is_neg = true
      x1 = -x1
    end

    if x2 < 0
      is_neg = !is_neg
      x2 = -x2
    end
  
    return 0 if x1 == 0
    
    begin
      ret += x2 if x1 % 2 != 0
      x1 = (x1 / 2).floor
      x2 = x2 * 2
    end while( x1 >= 1)
    
    ret = -ret if is_neg
    return(ret)
  end
end

2009-07-22 Reply Admin

For maximum speed, I pre-allocate the tables I use for storage, and avoid all floating-point multiplies and divides. A complete executable program in Lua; run with an argument (any argument) for the peasant-product, without to use the baseline-for-testing "Gold" function.

function Gold(a, b)
	return a * b
end
function DivideByTwo(n)
local m = n
while m + m > n do
m = m - 1
end
return m
end
function AllocateTable(a)
local t = {}
while a >= 1 do
a = DivideByTwo(a)
t[#t + 1] = {}
end
return t
end
function AllocateColumnTable(t)
for i = 1, #t do
t[i].aColumn = 0
t[i].bColumn = 0
end
end
function AllocateValidTable(t)
for i = 1, #t do
t[i].truth = false
end
end
function TestIsOdd(n)
n = math.abs(n)
while n > 1 do
	n = n - 2
end

if n == 0 then
	return false
elseif n == 1 then
	return true
else
	print("unknown failure")
	os.exit(-1)
end

end
function PopulateTable(t, a, b)
for i = 1, #t do
local j = i - 1
local aC, bC = a, b
while j > 0 do
if TestIsOdd(aC) then
aC = DivideByTwo(aC - 1)
else
aC = DivideByTwo(aC)
end
		bC = bC + bC
		
		j = math.floor(j - 1)
	end
	
	t[i].aColumn = aC
	t[i].bColumn = bC
end

end
function CollectValidRows(t, v)
local n = math.min(#t, #v)
for i = 1, n do
if TestIsOdd(t[i].aColumn) then
v[i].truth = true
end
end
end
function SumValidRows(t, v)
local n = math.min(#t, #v)
local sum = 0
for i = 1, n do
if v[i].truth == true then
sum = sum + t[i].bColumn
end
end
return sum
end
function PeasantProduct(a, b)
local columTable = AllocateTable(a)
local validTable = AllocateTable(a)
AllocateColumnTable(columTable)
AllocateValidTable(validTable)

PopulateTable(columTable, a, b)
CollectValidRows(columTable, validTable)

return SumValidRows(columTable, validTable)

end
function DoTest(f)
-- Generated by fair dice roll. Guaranteed to be random.
math.randomseed(4)
for n = 1, 1000 do
	local a = math.random(1, 200)
	local b = math.random(1, 200)
	print( string.format("%d * %d = %d", a, b, f(a,b)))
end

end
local args = {...}
if args[1] then
print("Peasant")
DoTest(PeasantProduct)
else
print("Baseline")
DoTest(Gold)
end

ikegami · 2009-07-22 Reply Admin

As a circuit diagram

[image]

(Handles 4-bit unsigned integers)

The selection of input wires for AND gates perform the right shifts. The AND gates perform the oddness test. The selection of input wires for the adders perform the left shifts.

Addendum (2009-07-22 23:27): I forgot to mention this was done in MS Paint

2009-07-22 Reply Admin

Take your pick:

(defun multiply (x y)
  (loop
    with result = 0
    for first = x then (floor first 2)
    for second = y then (* second 2)
    if (oddp first)
    do (incf result second)
    if (= first 1)
    do (return result)))

(defun trmultiply (x y)
  (labels
    ((inner
       (x y acc)
       (if (> x 0)
     (inner (floor x 2)
            (* y 2)
            (if (oddp x) (+ y acc) acc))
     acc)))
    (inner x y 0)))

2009-07-22 Reply Admin

Speccy basic, recursive:

  10 DEF FN m(a,b)=VAL ((("FN m(
"+STR$ a+"*2,INT ("+STR$ b+"/2))
+("+STR$ b+"-2*INT ("+STR$ b+"/2
))*"+STR$ a) AND b<>1)+(STR$ a A
ND b=1))

mol1111 · 2009-07-22 Reply Admin

Originally I thought about sending 1235th boring C# version or 436th Python version but then I realized that there is no GUI version (except for few PHP or JS versions with HTML WUI [Web User Interface :-) ]). So I created one using my all-time favourite library: Turbo Vision (so it's really TUI and not GUI). Tested with BP7 and recent FreePascal.

program RussianMultiplicationTV;

uses App, Dialogs, Drivers, Menus, MsgBox, Objects, Validate, Views;

const
  cmCalculate = 1001;

type
  TRussMultApp = object(TApplication)
    procedure InitMenuBar; virtual;
    procedure HandleEvent(var Event: TEvent); virtual;
    procedure ExecuteMainDlg;
  end;

  PMainDlg = ^TMainDlg;
  TMainDlg = object(TDialog)
    ResultListBox: PListBox;
    FirstInputLine: PInputLine;
    SecondInputLine: PInputLine;
    constructor Init;
    procedure HandleEvent(var Event: TEvent); virtual;
  end;

function Calculate(x, y: longint): PCollection;
type
  TFormatRec = record
    Line, X, Y, Extra: longint;
  end;
var
  List: PStringCollection;
  TempStr: String;
  FormatRec: TFormatRec;
begin
  New(List, Init(10, 10));
  List^.Insert(NewStr(#0 + 'Step    First   Second    Extra'));
  FormatRec.Line := 1;
  FormatRec.Extra := 0;
  while (x > 0) do begin
    FormatRec.X := x;
    FormatRec.Y := y;
    Inc(FormatRec.Extra, (x mod 2) * y);
    FormatStr(TempStr, '%5d %8d %8d %8d', FormatRec);
    List^.Insert(NewStr(TempStr));
    x := x shr 1;
    y := y shl 1;
    Inc(FormatRec.Line);
  end;
  List^.Insert(NewStr(' ------'));
  Str(FormatRec.Extra, TempStr);
  List^.Insert(NewStr(' Result = ' +  TempStr));
  Calculate := List;
end;

procedure TRussMultApp.ExecuteMainDlg;
var
  Dlg: PMainDlg;
begin
  New(Dlg, Init);
  ExecuteDialog(Dlg, nil);
end;

procedure TMainDlg.HandleEvent(var Event: TEvent);
var
  x, y: longint;
  code: integer;
begin
  inherited HandleEvent(Event);
  if (Event.What = evCommand) and (Event.Command = cmCalculate) then begin
    Val(FirstInputLine^.Data^, x, code);
    if code <> 0 then begin
      MessageBox('Please put valid number into the first input field.', nil,
        mfError or mfOKButton);
      exit;
    end;
    Val(SecondInputLine^.Data^, y, code);
    if code <> 0 then begin
      MessageBox('Please put valid number into the second input field.', nil,
        mfError or mfOKButton);
      exit;
    end;
    ResultListBox^.NewList(Calculate(x, y));
    ClearEvent(Event);
  end;
end;

procedure TRussMultApp.HandleEvent(var Event: TEvent);
begin
  inherited HandleEvent(Event);
  if ((Event.What = evCommand) and (Event.Command = cmNew)) then begin
    ExecuteMainDlg;
    ClearEvent(Event);
  end;
end;

procedure TRussMultApp.InitMenuBar;
var
  R: TRect;
begin
  GetExtent(R);
  R.B.Y := R.A.Y + 1;
  MenuBar := New(PMenuBar, Init(R, NewMenu(
    NewItem('~C~alculator', '', kbNoKey, cmNew, 0,
    NewItem('E~x~it', 'Alt+X', kbAltX, cmQuit, hcExit,
    nil)))));
end;

constructor TMainDlg.Init;
var
  R: TRect;
  ScrollBar: PScrollBar;
  S: String[8];
begin
  R.Assign(0, 0, 60, 20);
  inherited Init(R, 'Russian Multiplication');
  Options := Options or ofCentered;

  R.Assign(2, 2, 12, 3);
  New(FirstInputLine, Init(R, 8));
  FirstInputLine^.SetValidator(New(PRangeValidator, Init(1, 1000)));
  Str(Random(9999) + 1, S);
  FirstInputLine^.SetData(S);
  Insert(FirstInputLine);
  R.Assign(14, 2, 26, 3);
  New(SecondInputLine, Init(R, 8));
  SecondInputLine^.SetValidator(New(PRangeValidator, Init(1, 1000)));
  Str(Random(999) + 1, S);
  SecondInputLine^.SetData(S);
  Insert(SecondInputLine);
  R.Assign(27, 2, 45, 4);
  Insert(New(PButton, Init(R, 'Calculate!', cmCalculate, bfDefault)));
  R.Assign(57, 4, 58, 19);
  New(ScrollBar, Init(R));
  Insert(ScrollBar);
  R.Assign(2, 4, 57, 19);
  New(ResultListBox, Init(R, 1, ScrollBar));
  Insert(ResultListBox);

  { Selects first input box }
  SelectNext(False);
end;

var
  RussMultApp: TRussMultApp;

begin
  Randomize;
  RussMultApp.Init;
  RussMultApp.Run;
  RussMultApp.Done;
end.

Addendum (2009-07-22 21:05): Download (Source+binaries for DOS and Windows)

2009-07-22 Reply Admin

#!/usr/bin/env python

def rus_mult(A, B): if A == 1: return B else: return rus_mult(A / 2, B * 2) + (A % 2) * B

def run_tests(): tests = [(18, 23), (12, 3), (1, 1), (15, 2), (8, 22), (7, 13), (9, 20)]

    for (A, B) in tests:
            print "Test", A, "*", B, "Result:", rus_mult(A, B) == A * B

if name == "main": run_tests()

2009-07-22 Reply Admin

C#, handles negative numbers 0, 1.

And, as usual, the most elegant solution is the recursive one.

private int RussianPeasant(int a, int b)
{
    int c;
    if (a < 0)
    {
        a = -a;
        b = -b;
    }
    for (c = (a & 1) * b; (a > 1); c += ((a >>= 1) & 1) * (b <<= 1)) ;
    return c;
}

private int RecursiveRussianPeasant(int a, int b)
{
    if (a < 0)
        return RecursiveRussianPeasant(-a, -b);
    return (a == 0) ? 0 : ((a & 1) * b) + RecursiveRussianPeasant(a >> 1, b << 1);
}

2009-07-22 Reply Admin

theres some ruby code for you

def rmul(a,b)
  ret = 0
  begin
    ret = (a<0) ? ret-b : ret+b if a%2==1 or a%2==-1
    a = (a<0) ? a/2 + a%2 : a/2
    b = b*2
  end while a != 1 and a != -1 and a != 0 
  ret = (a<0) ? ret-b : ret+b if a%2==1 or a%2==-1
  ret
end

puts rmul(-10,20)
puts rmul(10,20)
puts rmul(-3,500)
puts rmul(1002,343)

2009-07-22 Reply Admin

Here's one in Motorola 68000 assembly:

.xdef __mulsi3
__mulsi3:
move.l 4(%a7),%d1
move.l 8(%a7),%d2
moveq.l #0,%d0
0:
lsr.l #1,%d1
bcc.s 1f
add.l %d2,%d0
1:
add.l %d2,%d2
tst.l %d1
bne.s 0b
rts

Note that this one is actually useful, it can be used if you don't have a working libgcc for your target. :-) Though that one is faster. ;-)

That said, on CPUs like the Z80 which don't have a native multiplication instruction, Russian Peasant is actually extremely useful.

2009-07-22 Reply Admin

def Mul(a,b): return DirectionsFromLeaders( "mul", a, b )

example:

Mul(3,56) : Illegal Question, Caller terminated

2009-07-22 Reply Admin

My Perl-solution with optimization, a bit of math and several tests. It also handles negative numbers.

#/usr/bin/perl
use strict;
use warnings;

if ((@ARGV != 2) || ($ARGV[0]!~m/\d/) || ($ARGV[1]!~m/\d/)) {
	print "Missing or wrong arguments! Need two integers\n";
	exit(0);
}

my ($left,$right)=@ARGV;

if ($right lt $left) {
	my $temp=$right;
	$right=$left;
	$left=$temp;
}

my $negative=1;

if ($left==1) {
	print $right."\n";
	exit(0);
}
elsif ($left==0) {
	print "0\n";
	exit(0);
}
elsif (($left lt 0) && ($right lt 0)) {
	$left*=-1;
	$right*=-1;
}
elsif (($left lt 0) || ($right lt 0)) {
	$left=abs($left);
	$right=abs($right);
	$negative=-1;
}

my $result=0;
for (my $iteration=int(log($left)/log(2));$iteration>=0;$iteration--) {
	if ($left%2!=0) {
		$result+=$right;
	}
	$left=int($left/2);
	$right*=2;
}
print $negative*$result."\n";

2009-07-22 Reply Admin

ath:

Same thing in python:

def is_odd(n):
    return (n % 2) != 0
def rmul(x, y):
s = 0
while(x != 1):
if is_odd(x):
s += y
x /= 2
y *= 2
return y + s

Funnily enough, I did the same thing... then realized that is_odd() can be superseded by the simple statement "if (num%2)". Mine prints output, but it's basically the same. I wasn't aware that Python supported +=, though.

2009-07-22 Reply Admin

#include <libgen.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    int lhs, rhs;
    int res;

    if (argc != 3) {
        printf("usage: %s <lhs> <rhs>\n", basename(argv[0]));
        return (1);
    }

    lhs = atoi(argv[1]);
    rhs = atoi(argv[2]);

    res = 0;
    while (lhs > 1) {
        if (lhs % 2 == 1) {
            res += rhs;
        }
        lhs /= 2;
        rhs *= 2;
    }

    res += rhs;

    printf("result: %d\n", res);

    return (0);
}

PatrickBeebe · 2009-07-22 Reply Admin

In c#

    public static int RussianMultiplication(int x, int y)
    {
        if ((y >> 31 | 1) * y < (x >> 31 | 1) * x)
            y = (x + y) - (x = y);

        int result = 0;
        for (result = 0; x != 0; x /= 2, y >>= 1)
            result += ((x >> 31) | 1) * ((0 - (x & 1)) & y);

        return result;
    }

Handles 0, negatives, and optimizes which digits to place in which column.

And. Fast.

Addendum (2009-07-23 13:39): Whoops, that should have been:

    public static int RussianMultiplication(int x, int y)
    {
        if ((y >> 31 | 1) * y < (x >> 31 | 1) * x)
            y = (x + y) - (x = y);

        int result = 0;
        for (result = 0; x != 0; x /= 2, y += y)
            result += ((x >> 31) | 1) * ((0 - (x & 1)) & y);

        return result;
    }

mwchase · 2009-07-22 Reply Admin

Bah, one-liners. I figured I'd write my code in true WTF style.

#!/usr/bin/env python

def mult(a, b):
   d = {a: b}
   if d.keys() == [0] or d.values() == [0]:
       return 0
   if d.keys() < [0]:
       return mult(*(increment(~d.keys()[0]), increment(~d.values()[0])))
   extend(d)
   [d.__delitem__(k) for k in d.keys() if not k&1]
   return sum(d.values())

def extend(d):
   d[min(d.keys())>>1] = (d[min(d.keys())])<<1
   if min(d.keys()) != 1 and min(d.keys()) != 0:
       extend(d)
   return

def increment(x, p=0):
   if x & (1<<p):
       return increment(x^(1<<p), increment(p))
   return x | (1<<p)</pre>
Note that I only used arithmetic-related stuff on the lists.  Everything else is done bit-wise.  See if you can spot the weird abuses and seemingly-random edge cases!  (Hint: if there's code that doesn't seem to serve much of a purpose, especially in an if-statement, it's probably deflecting execution around an infinite loop.  Either that or I thought it would be funny.)
Addendum (2011-01-30 17:48):
Looking back on this, it turns out I could have made parts of it even worse.  The if-statement in extend, for example, could use instead "min(d.keys())&-2" (or ~1, if you like.  The values are equivalent)
I think the lesson to take away from this is, if any potential employers decided to see if Google knew about my python experience, this is all a joke.

LeCoyote · 2009-07-22 Reply Admin

Two PHP functions in there: the first one does the maths, the second one displays a (very) barren page detailing the steps.

<?php
<span style="color:blue;">function motherland($a,$b)
{
  $r=0 ;
  while($a)
  {
    ($a%2) && $r+=$b ;
    $a>>=1 ;
    $b<<=1 ;
  }
  return $r ;
}

function motherland2($a,$b)
{
  $r = 0 ;
  $o = "";
  while($a)   
  {  
    $t = " text-decoration: line-through" ;
    $o .= "";
    $a >>= 1 ;   
    $b <<= 1 ;
  }
  $o .= "$a x $b
$r";
  return $o ;
}
echo motherland2(167, 24);
echo motherland(167, 24);
?>

Fun :-) Syntax highlighting was just ... too much free time ;)

2009-07-22 Reply Admin

ikegami:
As a circuit diagram [image]
(Handles 4-bit unsigned integers)

The selection of input wires for AND gates perform the right shifts. The AND gates perform the oddness test. The selection of input wires for the adders perform the left shifts.

This one rocks! But you need to expand adders as well, either on a separate sheet or the same one. Also show the transistor logic for each AND gate and adders.

2009-07-22 Reply Admin

$ perl -E'($i,$j)=@ARGV;while($i){($i!=int($i/2)2||!int($i/2))&&($k+=$j);$j=2;$i=int($i/2)}say$k' 18 23 414 $

2009-07-22 Reply Admin

Here's my code in python:

def mul(a,b):
 	m=[(a,b)]
 	while(m[-1][0]<>1):
 		m.append((m[-1][0]/2, m[-1][1]*2))
 	return sum([x[1] for x in m if x[0]%2==1])

dee · 2009-07-22 Reply Admin

I'm a little disappointed that I haven't seen any submissions in the language actually used to perform Important tasks involving numbers: COBOL.

       IDENTIFICATION DIVISION.
       PROGRAM-ID.  RussianPeasantMultiplication.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 FirstNumber    PIC S9(18).
       01 SecondNumber   PIC S9(18).
       01 Result         PIC S9(18) VALUE 0.
       01 ResultFormat   PIC ------------------9.

       PROCEDURE DIVISION.
       MAIN.
           PERFORM DATA-ACQUISITION.
           PERFORM PEASANT-MULTIPLICATION-PROCEDURE.
           STOP RUN.

       DATA-ACQUISITION.
           DISPLAY "First number: " WITH NO ADVANCING.
           ACCEPT FirstNumber.
           DISPLAY "Second number: " WITH NO ADVANCING.
           ACCEPT SecondNumber.
            
       PEASANT-MULTIPLICATION-PROCEDURE.
           IF FirstNumber IS NEGATIVE THEN
               COMPUTE FirstNumber = - FirstNumber
               COMPUTE SecondNumber = - SecondNumber
           END-IF.

           PERFORM UNTIL FirstNumber IS ZERO 
               IF FUNCTION MOD(FirstNumber 2) = 1 THEN
                   ADD SecondNumber TO Result
               END-IF
               DIVIDE FirstNumber BY 2 GIVING FirstNumber
               ADD SecondNumber TO SecondNumber GIVING SecondNumber
           END-PERFORM.

           MOVE Result TO ResultFormat.
           DISPLAY 'Result: ' ResultFormat.

Tested with OpenCobol 1.0.

2009-07-22 Reply Admin

Or shorter : $ perl -E'($i,$j)=@ARGV;while($i){($i%2||!$i/2)&&($k+=$j);$j*=2;$i=int($i/2)}say$k' 18 23 414 $

2009-07-22 Reply Admin

IMO, the peasants aren't actually multiplying and dividing by two, rather, they're doubling and halving numbers, a less generic but far simpler operation, that's why using * and / is cheating.

Anyway, some more Haskell. This one handles negative numbers (don't think any Haskell entry so far does that,) is tail recursive AND uses type classes!

import Data.Bits (shiftL, shiftR, Bits)

rmult :: (Integral a, Bits a) => a -> a -> a
rmult a b | a < 0     = - (rmult (-a) b)
          | a < 0     = - (rmult a (-b))
          | otherwise = go 0 a b where
                go acc 0 b = acc
                go acc a b = go (acc + if odd a then b else 0)
                                (a `shiftR` 1)
                                (b `shiftL` 1)

2009-07-22 Reply Admin

Oops, that second | a < 0 ... should be | b < 0 ...!

RayS · 2009-07-22 Reply Admin

Updated from earlier post that I never bothered to updeate correctly.

done in wonderful VBA, and just like in the article, shows full manual working out table in the debug window. Works with negatives, zeros, hopefully everything really. I stuck to the principle and process of the manual process instead of taking shortcuts.

Public Function RussianMultiply(x As Long, y As Long) As Long
    Dim vals() As Long
    ReDim vals(1 To Round(Sqr(Abs(x)), 0) + 1, 1 To 2) As Long
    Dim i As Long, j As Long, c As Long, Msg As String, s As Long
    s = Sgn(x) * Sgn(y)
    i = 1
    Do Until x = 0
        vals(i, 1) = x
        vals(i, 2) = y
        i = i + 1
        x = x \ 2
        y = y * 2
    Loop
    For j = 1 To i - 1
        If vals(j, 1) / 2 = vals(j, 1) \ 2 Then
            Msg = " X"
        Else
            c = c + (s * Abs(vals(j, 2)))
            Msg = s * Abs(vals(j, 2))
        End If
        Debug.Print vals(j, 1) & vbTab & vals(j, 2) & vbTab & Msg
    Next
    Debug.Print vbCrLf & "=" & vbTab & c
    RussianMultiply = c
End Function

Sample output

>RussianMultiply 18,23

18  23   X
9   46  46
4   92   X
2   184  X
1   368 368

=   414

2009-07-22 Reply Admin

package test;

import java.util.ArrayList; import java.util.List;

public class RussianMultiplication {

public RussianMultiplication() {}

public long multiply(long parameter1, long parameter2) {
	if (parameter2 < parameter1) {
		return handleMultiplication(parameter2, parameter1);
	} else {
		return handleMultiplication(parameter1, parameter2);
	}
}

private long handleMultiplication(long lhs, long rhs) {
	List<RussianNumber> numberList = new ArrayList<RussianNumber>();
	numberList.add(new RussianNumber(lhs, rhs));
	while (lhs > 1) {
		lhs = lhs / 2;
		rhs = rhs * 2;
		numberList.add(new RussianNumber(lhs, rhs));
	}
	long result = 0;
	for (RussianNumber number : numberList) {
		if (number.getLhs() % 2 != 0) {
			result = result + number.getRhs();
		}
	}
	return result;
}

public static void main(String[] args) {
	RussianMultiplication rm = new RussianMultiplication();
	long result = rm.multiply(23, 18);
	System.out.println("Result: " + result);
}

private class RussianNumber {
	private long lhs;
	private long rhs;
	
	public RussianNumber(long lhs, long rhs) {
		this.lhs = lhs;
		this.rhs = rhs;
	}

	public long getLhs() {
		return lhs;
	}

	public void setLhs(long lhs) {
		this.lhs = lhs;
	}

	public long getRhs() {
		return rhs;
	}

	public void setRhs(long rhs) {
		this.rhs = rhs;
	}

	public String toString() {
		return lhs + "::" + rhs;
	}
}

}

DFHawthorne · 2009-07-22 Reply Admin

Another Oracle SQL Example:

SQL> VARIABLE left_num NUMBER
SQL> VARIABLE right_num NUMBER
SQL> BEGIN
   :left_num := 18;
   :right_num := 23;
END;
PL/SQL procedure successfully completed.
Elapsed: 00:00:00.06
SQL> SELECT     SUM (DECODE (MOD (TRUNC (:left_num / POWER (2, ROWNUM - 1), 0), 2),
                        1, :right_num * POWER (2, ROWNUM - 1)
                       )
               ) AS RESULT
      FROM DUAL
CONNECT BY TRUNC (:left_num / POWER (2, ROWNUM - 1), 0) > 0

    RESULT
----------
       414


1 row selected.
Elapsed: 00:00:00.06

2009-07-22 Reply Admin

In Python, aiming for readability.

def russian_peasant(x,y):
    steps=[(x,y)]
    while x>1 or x<-1:
        x/=2
        y*=2
        steps.append((x,y))
    return sum([y for x,y in steps if x % 2 == 1]) * x # * x is there to give the correct sign for the result

# Test it    
print russian_peasant(18,23), 18*23 
print russian_peasant(18,0), 18*0
print russian_peasant(-2,400), -2*400
print russian_peasant(40,-30), 40*-30
print russian_peasant(40,30), 40*30

mjomble · 2009-07-22 Reply Admin

How about a good dose of OOM?

The code's too long to post here, but beyond this link you can enjoy it in fully highlighted PHP syntax: http://justas.ggcmedia.com/MultiplicationFramework.html (usage example at the end of the file)

Sample output:

Multiplying 18 by 23 Russian peasant style:

Numeric result: 414

Full result:
18 x  23 |   0 +
 9 x  46 |  46 +
 4 x  92 |   0 +
 2 x 184 |   0 +
 1 x 368 | 368 =
----------------
    Total: 414

...hmm, I need to go clean my hands now.

2009-07-22 Reply Admin

int mul_rus(int a, int b) { int c = 0;

while (a != 1)
{
    if (a & 1)
        c += b;
    
    a >>= 1;
    b <<= 1;
}

return b + c;

}

2009-07-22 Reply Admin

Here's a fairly straightforward implementation in common lisp:

(defun mult (x y)
  (if (= x 1)
    y
    (+ (if (= (rem x 2) 0) 0 y) (mult (floor (/ x 2)) (* y 2)) )
  )
)

It could be all on one line, but that'd be harder to read. If someone has suggestions on how to simplify it, that'd be great. :)

2009-07-22 Reply Admin

In PDP-8 assembly language. Untested

X, 0 Y, 0 Z, 0

RUSMUL, 0 // entry point CLA DCA Z / clear total

LP, TAD X SNA JMP DONE

ROR
DCA	X
SZL  CLA
TAD	Y
TAD	Z
DCA	Z
TAD	Y
ROL
DCA	Y
JMP	LP

DONE, TAD Y TAD Z JMP I RUSMUL

2009-07-22 Reply Admin

Sloppy JS version with animated step-by-step output: http://crindigo.com/stuff/praxis.html

2009-07-22 Reply Admin

Uses NO math operations, only regex and string operations. Almost all major work is kept in the global $_ variable. Numbers are represented internally using a base-30-like system, then converted directly back to decimal at the end of each operation. Some assumptions about collating sequence were made (e.g. \d == [0-9]).

#!/usr/bin/perl
$_ = join(' ', @ARGV);
m#^\s*-?\d+\s*x\s*-?\d+\s*# or die('Input should be in "#### x ####" format.');
$sign = '+'; while(s#-##) { $sign =~ tr#+-#-+#; }
s#\s##g;
s#$#=0#;
while(!m#^0*x#)
	{
	s#(?<!\d)(\d)#0$1#g;
	if(m#\d+[13579]x#)
		{
		s#(.*x)(.*)(=.*)#$1$2$3+$2#;
		while(m#(.*)(\d)([a-jA-J]?)([a-jA-J]*\+\d*)(\d)(.*)#)
			{
			my($a, $b, $c, $d, $e, $f);
			$a = $1; $b = $2; $c = $3; $d = $4; $e = $5; $f = $6;
			while($e =~ m#[^a0]#)
				{
				$e =~ tr#1-9#a1-8#;
				$b =~ tr#0-9a-jA-I#b-jAb-jA-J#;
				}
			$e =~ tr#0#a#; $b =~ tr#0-9#a-j#;
			$c =~ m#[A-J]# and $b =~ tr#0-9a-jA-J#b-jAb-jA-J#;
			$_ = $a . $b . $c . $d . $e . $f;
			s#=(?!0)#=0#;
			}
		while(m#(.*)(\d)([A-J].*\+)#)
			{
			$x = $2;
			$x =~ tr#0-9#b-jA#;
			$_ = $1 . 0 . $x . $3;
			}
		tr#a-jA-J#0-90-9#;
		s#\+.*##;
		}
	if(m#^(\d)(.*)#)
		{
		$x = $1;
		$x =~ tr#0-9#aAbBcCdDeE#;
		$_ = $x . $2;
		}
	while(m#^([A-Ja-j]*?)([A-Ja-j]?)(\d)(.*)#)
		{
		my($a, $b, $c, $d);
		$a = $1; $b = $2; $c = $3; $d = $4;
		$b =~ m#[a-j]# and $c =~ tr#0-9#aAbBcCdDeE#
			or $c =~ tr#0-9#fFgGhHiIjJ#;
		$_ = $a . $b . $c . $d;
		}
	tr#A-Ja-j#0-90-9#;
	if(m#^(.*)(\d)(=.*)#)
		{
		$x = $2;
		$x =~ tr#0-9#acegiACEGI#;
		$_ = $1 . $x . $3;
		}
	while(m#(.*?)(\d)([A-Ja-j]?)([A-Ja-j]*=.*)#)
		{
		my($a, $b, $c, $d);
		$a = $1; $b = $2; $c = $3; $d = $4;
		$c =~ m#[a-j]# and $b =~ tr#0-9#acegiACEGI#
			or $b =~ tr#0-9#bdfhjBDFHJ#;
		$_ = $a . $b . $c . $d;
		}
	tr#A-Ja-j#0-90-9#;
	s#(?<!\d)0+(?=\d|0(?!\d))##g;
	}
s#.*=##;
s#^#$sign#;
s#^\+##;
s#$#\n#;
print;</pre>

2009-07-22 Reply Admin

--SQL Server using Common Table Expression

DECLARE @number1 int; DECLARE @number2 int;

SET @number1 = 18; SET @number2 = 23;

WITH Multiplication (Row, Factor1, Factor2) AS ( SELECT 1, @number1, @number2 UNION ALL SELECT Row + 1, Factor1 / 2, Factor2 * 2 FROM Multiplication WHERE Factor1 > 1 ) SELECT SUM(Factor2) FROM Multiplication WHERE Factor1 % 2 = 1;

2009-07-22 Reply Admin

func(a, b): if(a == 1) return b if(a%2 == 1) return b2 + func(a/2, b2) else return func(a/2, b*2)

Had to do it with recursion. I can't think of a reason why not to do it that way. I also haven't looked at the comments. Someone probably came up with this solution or it has already been shown to be wrong. I could also shrink it to be a single line but then it wouldn't be nearly as readable.

2009-07-22 Reply Admin

--It works better as a stored procedure

SET ANSI_NULLS ON GO SET QUOTED_IDENTIFIER ON GO -- ============================================= -- Author: Paul N -- Create date: 7/22/2009 -- Description: multiplies two numbers using -- Russian Peasant Multiplication -- ============================================= CREATE PROCEDURE dbo.[Russian Peasant Multiplication] -- Add the parameters for the stored procedure here @number1 int, @number2 int AS BEGIN -- SET NOCOUNT ON added to prevent extra result sets from -- interfering with SELECT statements. SET NOCOUNT ON;

-- Insert statements for procedure here
	WITH Multiplication (Row, Factor1, Factor2) AS 
	(
		SELECT 1, @number1, @number2
		UNION ALL
		SELECT Row + 1, Factor1 / 2, Factor2 * 2
		FROM Multiplication
		WHERE Factor1 > 1
	)
	SELECT SUM(Factor2) FROM Multiplication
	WHERE Factor1 % 2 = 1;

END GO

2009-07-22 Reply Admin

open List

let oddcar (n, _) = (n land 1) = 1 let sum = fold_left (+) 0

let rec do_mul = function | (x,_) :: _ as lst when x == 1 -> sum (map snd (filter oddcar lst)) | (x,y) :: _ as lst -> do_mul ((x / 2, y * 2) :: lst)

let mul x y = do_mul [x,y]

Veryth · 2009-07-22 Reply Admin

C# + LINQ

int Multiply(int x, int y)
{
	return Enumerable.Range(0, (int)(1.0 + Math.Log(x)/Math.Log(2)))
		.Select(i => new {x = x >> i, y = y << i})
		.Where(p => p.x > 0 && p.x % 2 == 1)
		.Sum(p => p.y);	
}

Addendum (2009-07-23 01:23): More LINQ-ish:

int Multiply(int x, int y)
{
	return (
		from i in Enumerable.Range(0, (int)(1.0 + Math.Log(x)/Math.Log(2)))	
		where (x >> i) % 2 == 1
		select y << i
	).Sum();	
}

2009-07-22 Reply Admin

simple erlang:

-module(rmult).
-export([rmult/2]).

rmult(M1, M2) -> rmult(M1, M2, [{M1, M2}]).

rmult(1, _, P) -> rsum(P, 0); 
rmult(M1, M2, P) ->
  M1n = M1 div 2, M2n = M2 * 2,
  rmult(M1n, M2n, [{M1n, M2n} | P]).

rsum([], S) -> S;
rsum([{M, _} | P], S) ->
  rsum(P, S + case M rem 2 of 0 -> 0; 1 -> M end).

2009-07-22 Reply Admin

; Rabbit 2000 assembler
; Inputs in A, B
; Result in HL

    	ld d, 0
    	ld e, b 		;; DE = second operand
    	ld hl, 0		;; accum = 0
    	or a
    	;; For the first iteration, we need to just test whether the second
    	;; operand is even, rather than using a side effect of the rotate
    	bit 0, a
..mul_loop:
    	jr nc, ..odd
    	add hl, de
..odd:
    	or a			;; CF = 0
    	jr z, ..done	;; A = 0?
    	rl de			;; DE *= 2
    	rr a			;; A /= 2. CF can't be nonzero as that would imply overflow
    	jr ..mul_loop	;; CF from A is used on next iteration
..done:
    	;; result in HL

Russian Peasant Multiplication

Leave a comment on “Russian Peasant Multiplication”