# Comment On Russian Peasant Multiplication

Ever since the first OMGWTF Programming Contest, I've always wanted to bring back some element of "coding challenges" to the site. Ideally, this would be in the form of a second contest... but considering that contests require a ton of work, and the fact that interns around town have come to learn that interning at Inedo basically mean means shipping mugs, mailing stickers, testing contest entries, and acting as human ottomans, we'll have to go with something a bit scaled back. And that's where Programming Praxis will come in. [expand full text]
 « Prev Page 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 | Page 9 | Page 10 | Page 11 | Page 12 | Page 13 | Page 14 | Page 15 | Page 16 Next »

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 16:59 • by qoo3h (unregistered)
 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" );

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:03 • by Lee Crabtree (unregistered)
 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) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:04 • by J.I. (unregistered)
 Pretty similar in C; int l(int l1, int ll) { return l1&-2?l1%2*ll+l(l1/2,ll*2):ll; } Looks kind of like a traffic accident, doesn't it?

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:09 • by ajp
 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)```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:10 • by Andrew Rodland (unregistered)
 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; } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:11 • by sdeek (unregistered)
 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]) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:13 • by Michael Clark (mjac.co.uk) (unregistered)
 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

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:15 • by opussf (unregistered)
 In Python: a,b = 190, 232 if a<0: a=-a; b=-b print sum([b<>s>0) and ((a>>s)%2)) ])

### Python Solution with some lambda

2009-07-22 17:25 • by KukkerMan (unregistered)
 ```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)) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:26 • by Jimmy Selgen (unregistered)
 (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```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:29 • by Tiogshi (unregistered)
 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```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:31 • by ikegami
 As a circuit diagram (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

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:31 • by Eric (unregistered)
 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)))```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:31 • by Yorick (unregistered)
 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)) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:35 • by mol1111
 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)

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:36 • by Edinburgh Mike (unregistered)
 #!/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()

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:42 • by Lernin ur codez (unregistered)
 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); } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:47 • by Redredredredredred (unregistered)
 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)```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:48 • by Kevin Kofler (unregistered)
 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.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:52 • by Rasmus (unregistered)
 def Mul(a,b): return DirectionsFromLeaders( "mul", a, b ) example: > Mul(3,56) : Illegal Question, Caller terminated

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:58 • by H2 (unregistered)
 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";```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 17:59 • by Ben (unregistered)
 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.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:07 • by Sam (unregistered)
 ```#include #include #include int main(int argc, char **argv) { int lhs, rhs; int res; if (argc != 3) { printf("usage: %s \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); } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:08 • by PatrickBeebe
 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; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:11 • by mwchase
 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<

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:11 • by LeCoyote
 Two PHP functions in there: the first one does the maths, the second one displays a (very) barren page detailing the steps. ```>=1 ; \$b<<=1 ; } return \$r ; } function motherland2(\$a,\$b) { \$r = 0 ; \$o = ""; while(\$a) { \$t = " text-decoration: line-through" ; \$o .= "
\$ax\$b
\$r
"; \$a >>= 1 ; \$b <<= 1 ; } \$o .= ""; return \$o ; } echo motherland2(167, 24); echo motherland(167, 24); ?> ``` Fun :-) Syntax highlighting was just ... too much free time ;)

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:17 • by AshG (unregistered)
 ikegami:As a circuit diagram (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.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:24 • by Florent (unregistered)
 \$ 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 \$

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:29 • by Adrian (unregistered)
 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]) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:34 • by dee
 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.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:35 • by Florent (unregistered)
 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 \$

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:37 • by valderman (unregistered)
 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)```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:38 • by valderman (unregistered)
 Oops, that second | a < 0 ... should be | b < 0 ...!

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:47 • by RayS
 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```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:55 • by Fred Dagg (unregistered)
 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 numberList = new ArrayList(); 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; } } }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 18:55 • by DFHawthorne
 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 ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:00 • by Jukka (unregistered)
 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 ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:04 • by mjomble
 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.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:14 • by spiderlama (unregistered)
 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; }

### clisp implementation

2009-07-22 19:23 • by unit3 (unregistered)
 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. :)

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:24 • by Gumpy Guss (unregistered)
 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

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:29 • by Crindigo (unregistered)
 Sloppy JS version with animated step-by-step output: http://crindigo.com/stuff/praxis.html

### Final "No Math" Perl Version

2009-07-22 19:30 • by Warr (unregistered)
 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#(?

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:48 • by Paul N (unregistered)
 --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;

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:53 • by Wheaties (unregistered)
 func(a, b): if(a == 1) return b if(a%2 == 1) return b*2 + func(a/2, b*2) 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.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 19:56 • by Paul N (unregistered)
 --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

### ocaml version

2009-07-22 19:59 • by yowzer (unregistered)
 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]

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:12 • by Veryth
 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(); } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:12 • by Mike McNally (unregistered)
 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). ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:19 • by bd_ (unregistered)
 ```; 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```
 « Prev Page 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 | Page 9 | Page 10 | Page 11 | Page 12 | Page 13 | Page 14 | Page 15 | Page 16 Next »