# 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 11:34 • by antelopelovefan
 Here's another VBScript version meant to run as an Excel macro. It assumes the values to be multipled are in cells A2 and B2 of the first Worksheet and it stores all of the intermediate numbers in the cells below as it calculates. The final output is put in cell C2 ```Public Sub CalculateRussianPeasant() Dim curSheet As Worksheet Dim curRow: curRow = 2 Dim bDone Dim i As Integer Dim total Set curSheet = Worksheets(1) Rows("3:65536").Select Selection.Delete Shift:=xlUp While Not bDone curSheet.Cells((curRow + 1), 1).Value = CInt(curSheet.Cells(curRow, 1).Value / 2) curSheet.Cells((curRow + 1), 2).Value = CInt(curSheet.Cells(curRow, 2).Value * 2) curRow = curRow + 1 If curSheet.Cells(curRow, 1).Value = 1 Then bDone = True End If Wend curSheet.Cells(2, 3).Value = 0 For i = 2 To curRow If curSheet.Cells(i, 1).Value Mod 2 <> 0 Then curSheet.Cells(2, 3).Value = curSheet.Cells(2, 3).Value + curSheet.Cells(i, 2).Value ElseIf i > 2 Then Range("A" & i & ":B" & i).Select With Selection.Font .Strikethrough = True .ColorIndex = 3 End With End If Next Range("C2").Select End Sub ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:35 • by Quxxy (unregistered)
 A version for the D programming language; both as an interative function and a template: ```// Regular version. Can also be used in compile-time code. long multiply(long a, long b) { if( a == 0 || b == 0 ) return 0; if( a < 0 ) return -multiply(-a, b); if( b < 0 ) return -multiply(a, -b); long acc = 0; do { if( a % 2 == 1 ) acc += b; a /= 2; b *= 2; } while( a >= 1 ); return acc; } // Template version template Multiply(long a, long b) { static if( a == 0 || b == 0 ) const Multiply = 0L; else static if( a < 0 ) const Multiply = Multiply!(-a, b); else static if( b < 0 ) const Multiply = Multiply!(a, -b); else static if( a == 1 ) const Multiply = b; else static if( a % 2 == 1 ) const Multiply = b + Multiply!(a/2, b*2); else const Multiply = Multiply!(a/2, b*2); }```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:35 • by f3nd3r (unregistered)
 Wow, you make PHP look good, that is pretty impressive.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:37 • by Amadan (unregistered)
 In Ruby, ```class Fixnum def *(b) a, k = self, 0 a, b = -a, -b if a < 0 while a != 0 k += b if a & 1 == 1 a >>= 1 b <<= 1 end k end end ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:37 • by Northpole (unregistered)
 Ruby, one line, non-recursive: `a,b,res=a/2,b*2,(res||0)+(a&1)*b while a>0`

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:42 • by campkev
 Second attempt at C#, this works with negative numbers: public int RussianMultiply(int operand1, int operand2) { int res = 0; while (operand1 != 0) { if (operand1 % 2 == 1) res += operand2; else if (operand1 % 2 == -1) res -= operand2; operand1 /= 2; operand2 *= 2; } return res; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:42 • by jweir77
 Different twist on a Ruby solution: ```class Fixnum def rum n product = 0 self.to_s(2).reverse.split(//).each_with_index do |bit, pos| product += ( n << pos ) if bit.to_i == 1 end product end end p 3.rum(2) p 2.rum(3) p 18.rum(23) p 23.rum(18) p 76.rum(45) p 45.rum(76) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:43 • by halber_mensch
 Josh Bohde:Python 2.6 `m=lambda a,b:sum(a<>n&1)` 51 characters I'd argue it's not quite the russian algorithm though, since you've both reversed the operands and you are evaluating a-log2(a) more iterations than would be done in the real algorithm. For example, if I were to feed 5,4 into the russian algorithm, it would make 3 iterations (the left column being 5,2,1). Taking into account that you've swapped the parameters, your algorithm would evaluate 5 iterations (the left column being 5,2,1,0,0), or two more (5 - log2(5)) iterations than you should if you were adhering to the real algorithm, which stops evaluating when reaching 1 in the left column. Your solution also fails for negative values of a.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:43 • by campkev
 second attempt at C# recurisive, this works with negative numbers: public int RecursiveRussianMultiply(int operand1, int operand2) { return operand1 == 0 ? 0 : RecursiveRussianMultiply(operand1 / 2, operand2 * 2) + (operand1 % 2 == 1 ? operand2 : 0) + (operand1 % 2 == -1 ? -operand2 : 0); }

### Have a Linqy day!

2009-07-22 11:45 • by Floyd (unregistered)
 ```using System; using System.Collections.Generic; using System.Text; using System.Linq; namespace RussianPeasant { class RussianPeasant { static void Main(string[] args) { if (args.Length != 2) { Console.Error.WriteLine("Peasants can't multiply " + args.Length + " operands!"); return; } int left = 0; int right = 0; if ((!int.TryParse(args[0], out left)) || (!int.TryParse(args[1], out right))) { Console.Error.WriteLine("Peasants can't multiply non-numeric operands!"); } int solution = (from pair in GetColumns(left, right) where pair.First() % 2 != 0 select pair).Sum(p => p.ElementAt(1)); Console.WriteLine(solution); Console.Read(); } public static IEnumerable> GetColumns(int left, int right) { yield return new int[] { left, right }; while (left > 0) { left = left >> 1; right = right * 2; yield return new int[] { left, right }; } } } } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:46 • by Alex Guzman (unregistered)
 int first = 18; int second = 23; int result = 0; while ((first = first / 2) >= 1) { second = second * 2; if (first % 2 != 0) result += second; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:47 • by kastein
 Rootbeer: Herman:this is the exact implementation of the multiply function on binary computing hardware Is this so? I had assumed that most CPUs with MULtiply opcodes used hardware lookup tables, in order to achieve a fast and constant O(1) execution time, but perhaps I am mistaken. It's certainly a less sensible approach with 32- or 64-bit operands than it would have been with 8- or 16-bit operands. Yeah... it isn't really a good idea. I thought it was more sane until I considered the results... for 8 bit multiplication we have two 8 bit inputs and a 16 bit output, so the table is 2^16 bits long with 16 bit entries... that's 1M transistors without the decoders/addressing logic. The average 8 bit CPU has a few thousand to a few tens of thousands of transistors. It just gets worse from there - multiplying two 16 bit numbers requires 4G 32-bit entries (128G transistors!) and multiplying two 32 bit numbers requires 1024E transistors... multiplying 64 bit numbers using a lookup table would require more transistors than there are on the planet (by at least a factor of 1 pentillion based on my napkin calculations...) If you want to know how processors multiply, several methods are listed here: wikibooks: multiply Booth's Algorithm some more are listed here, not all easily applicable to microprocessor design: multiplication algorithms More (basically the peasant's method in hardware!) binary multiplier

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:48 • by Jürgen (unregistered)
 Python: ```def rpmul(a, b): return ((a == 1) and b or (a % 2) * b + rpmul(a/2, 2*b)) ``` Ruby: ```def rpmul a, b (a == 1) ? b : (a % 2) * b + rpmul(a/2, 2*b) end ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:53 • by Bryan (unregistered)
 All we need is a SAS submission and this thread will be complete.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:53 • by Alex Muscar (unregistered)
 Common Lisp Imperative/iterative and functional solutions. Ain't it nice that Lisp's so versatile? :P ```(defun rpm (m n) (do ((t1 m (ash t1 -1)) (t2 n (ash t2 1)) (r 0 (+ r (* (mod t1 2) t2)))) ((= t1 0) r))) ``` ```(defun rpm-r (m n) (labels ((rec (acc m n) (if (= m 0) acc (rec (+ acc (* (mod m 2) n)) (ash m -1) (ash n 1))))) (rec 0 m n))) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:55 • by Josh Bohde (unregistered)
 halber_mensch: Josh Bohde:Python 2.6 `m=lambda a,b:sum(a<>n&1)` 51 characters I'd argue it's not quite the russian algorithm though, since you've both reversed the operands and you are evaluating a-log2(a) more iterations than would be done in the real algorithm. For example, if I were to feed 5,4 into the russian algorithm, it would make 3 iterations (the left column being 5,2,1). Taking into account that you've swapped the parameters, your algorithm would evaluate 5 iterations (the left column being 5,2,1,0,0), or two more (5 - log2(5)) iterations than you should if you were adhering to the real algorithm, which stops evaluating when reaching 1 in the left column. Your solution also fails for negative values of a. Yeah, I was saving some characters (at the cost of a lot of memory). Here's a recursive version that is 48 characters `m=lambda a,b:[0,b][a&1]+m(a>>1,b<<1)if a else 0`

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:56 • by Sal (unregistered)
 Postscript: /rmul{0{2 index 0 eq{exit}if exch dup 1 bitshift 4 1 roll 3 -1 roll dup -1 bitshift 5 1 roll 1 and 1 eq {add}{pop}ifelse}loop exch pop exch pop}def

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:58 • by AdT (unregistered)
 Osno:All the people using multiplication and division instead of shifting (except in languages where there is no shifting) also fail. All the people who don't know what an optimizing compiler is also fail.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:59 • by Alex Muscar (unregistered)
 Common Lisp: Shorter version of the recursive implementation: ```(defun rpm-r1 (m n &optional (acc 0)) (if (= m 0) acc (rpm-r1 (ash m -1) (ash n 1) (+ acc (* (mod m 2) n))))) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:59 • by Murray (unregistered)
 public String multiply(int a, int b){ return "Murray is awesome"; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:03 • by PopeHappyCat (unregistered)
 Damn, you beat me too it. But here you can has lolcode spec 1.2 (Untested) HAI 1.2 CAN HAS STDIO? I HAS A X I HAS A Y I HAS A MULTIPL X R NUMBR Y R NUMBR VISIBLE "CAN HAS X?:)" GIMMEH X VISIBLE "CAN HAS Y?:)" GIMMEH Y HOW DUZ I RPM YR X AN YR Y I HAS A MUTLIPL ITZ 0 I HAS A MODD I HAS A LOLCAT ITZ MAEK WIN A NUMBR BTW IS DUMMY VARIABLE FOR L00P IM IN YR RPMLOOP UPPIN YR LOLCAT WILE DIFFRINT X AN 1 X R MAEK QUOSHUNT OF X AN 2 A NUMBR Y R PRODUKT OF Y AN 2 MODD R MOD X AN 2 BOTH SAEM MODD AN 1, O RLY? YA RLY, MULTIPL R SUM OF MULTIPL AN Y NO WAI, BTW NOTHING HAPPENS OIC IM OUTTA YR RPMLOOP FOUND YR MULTIPL IF U SAY SO MULTIPL R RPM X Y VISIBLE "PRODUKT OF " N X N " N " N Y N " IZ " N MULTIPL N ":)" KTHXBYE

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:03 • by Fooba (unregistered)
 C implementation: int russian(int a, int b) {int c=0,d=a^b;a*=(a<0)?-1:1;for(a<<=1;(a>>=1)!=0;b<<=1)c+=a&0x1?b:0;return((c^d)<0?-c:c);}

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:03 • by koblas
 Another python version ```def mult(a, b) : v = [] while a != 0 : v.append((a % 2 != 0, b)) print a%2, a, b a >>= 1 b <<= 1 print reduce(lambda x, y: x+y, [p[1] for p in v if p[0]]) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:06 • by Bosshog (unregistered)
 ``` ; 6502 Assembler ; Runs on NES, BBC, C64, Atari 2600 and Apple II :) ; This is the 16-bit version to handle the example 18x23! ; \$0002 contains unsigned 8-bit operand 1 (not preserved) ; \$0004 contains unsigned 8-bit operand 2 (not preserved) ; \$0001:0000 will contain HI:LO bytes of 16-bit answer LDA #0 STA \$00 STA \$01 STA \$03 LDX #0 loop: CPX \$04 BEQ done CLC LSR \$04 BCC skip CLC LDA \$00 ADC \$02 STA \$00 LDA \$01 ADC \$03 STA \$01 skip: CLC ASL \$02 ROL \$03 JMP loop done: ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:07 • by halber_mensch
 Josh Bohde: halber_mensch: Josh Bohde:Python 2.6 `m=lambda a,b:sum(a<>n&1)` 51 characters I'd argue it's not quite the russian algorithm though, since you've both reversed the operands and you are evaluating a-log2(a) more iterations than would be done in the real algorithm. For example, if I were to feed 5,4 into the russian algorithm, it would make 3 iterations (the left column being 5,2,1). Taking into account that you've swapped the parameters, your algorithm would evaluate 5 iterations (the left column being 5,2,1,0,0), or two more (5 - log2(5)) iterations than you should if you were adhering to the real algorithm, which stops evaluating when reaching 1 in the left column. Your solution also fails for negative values of a. Yeah, I was saving some characters (at the cost of a lot of memory). Here's a recursive version that is 48 characters `m=lambda a,b:[0,b][a&1]+m(a>>1,b<<1)if a else 0` m(-1,2) .... File "", line 1, in File "", line 1, in RuntimeError: maximum recursion depth exceeded =(

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:08 • by Timepass (unregistered)
 ```package com.timepass; public class RussianMultiply { private int mulTotal = 0; RussianMultiply(){ super(); } private void multiply(int first,int second, boolean isFirstTime){ if(first == 0 || second ==0){ return; } if(isFirstTime && first%2!=0){ mulTotal = mulTotal + second; } int tempFirst = first/2; int tempSecond = second*2; if(tempFirst%2!=0){ mulTotal = mulTotal + tempSecond; } if(tempFirst != 1){ multiply(tempFirst,tempSecond,false); } } public void multiply(int first,int second){ multiply(first,second,true); } public void clearMulTotal(){ setMulTotal(0); } public int getMulTotal() { return mulTotal; } public void setMulTotal(int mulTotal) { this.mulTotal = mulTotal; } /** * @param args */ public static void main(String[] args) { RussianMultiply rm = new RussianMultiply(); rm.clearMulTotal(); rm.multiply(18, 23); System.out.println("Multiplication of 18 and 23:" + rm.getMulTotal()); rm.clearMulTotal(); rm.multiply(13, 13); System.out.println("Multiplication of 13 and 13:" + rm.getMulTotal()); } } ``` result: Multiplication of 18 and 23:414 Multiplication of 13 and 13:169

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:08 • by chriswatson
 C# using the delightful LINQ to objects ```using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace RussianPeasantMultiplication { class Program { static void Main(string[] args) { Console.WriteLine("Russian Peasant Multiplication"); Console.Write("Number 1: "); int number1 = Convert.ToInt32(Console.ReadLine()); Console.Write("Number 2: "); int number2 = Convert.ToInt32(Console.ReadLine()); List steps = new List(); steps.Add(new Gimley(number1, number2)); Console.WriteLine("Mutiply {0} by {1}", number1, number2); while (steps.Last().Left != 1) { Gimley lastStep = steps.Last(); int newLeft = lastStep.Left / 2; int newRight = lastStep.Right * 2; steps.Add(new Gimley(newLeft, newRight)); Console.WriteLine("Interim step: {0}, {1}", newLeft, newRight); } // discard even lefts and sum remaining rights decimal answer = (from g in steps where g.Left % 2 != 0 select g.Right).Sum(); Console.WriteLine("Answer is: {0}", answer); Console.ReadLine(); } class Gimley { public int Left { get; set; } public int Right { get; set; } public Gimley(int left, int right) { Left = left; Right = right; } } } } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:11 • by Jürgen (unregistered)
 Alex thats nice, and very similiar to my ruby/python versions, except where summarization occurs. I didn't bother with the 3rd acc parameter because ruby/python don't do tail-end optimization on recursive calls any way. That's probably why many diss recursive solutions, but my profiler tells me theres little difference especially if you compare to solutions using python list comprehensions or ruby's .each iteration.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:11 • by Anonymous (unregistered)
 NO U!

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:12 • by Rob W. (unregistered)
 #!/usr/bin/env python import sys try: sys.argv[1] sys.argv[2] except IndexError: numbers = raw_input("Please enter the two integers you wish to multiply separated by a space: ").split(' ') else: numbers = sys.argv[1:3] left = int(numbers[0].strip()) right = int(numbers[1].strip()) product = 0 while left != 0: if left % 2 != 0: product += right left /= 2 right*= 2 print "The product of " + numbers[0].strip() + " x " + numbers[1].strip() + " is " + str(product)

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:13 • by serg (unregistered)
 Some thoughts... ------------8<------------------- int mult(int a, int b) { int result = 0; while(a) { if(a & 0x01) { result += b; } a >>= 1; b <<= 1; } return result; } ------------8<------------------- int mult2(int a, int b) { int result = 0; if(a != 0) { result = mult2(a >> 1, b << 1); if(a & 0x01) { result += b; } } return result; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:13 • by Jannik Jochem (unregistered)
 My functional-style java version... ```public static int multiply(int a, int b) { if (a == 0 || b == 0) return 0; else if (a == 1) return b; else return multiply(a/2, b*2) + ((a % 2 == 1) ? b : 0); } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:14 • by Osno (unregistered)
 All the people who don't know what an optimizing compiler is also fail. So you're basically agreeing with the " a * b " solution? Because defining multiplication by using multiplication is kind of weird (ok, I agree is in the spec, but anyway). And no, when you're using rounding in vb.net (or the "\" operator) I can assure you that doesn't get optimized. And C# doesn't get optimized, at least not in IL (but maybe at the JIT level).

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:14 • by wolf550e (unregistered)
 http://www.phy6.org/outreach/edu/roman.htm This is not a Russian method but an ancient Roman one.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:17 • by tirerim
 ```#!/usr/bin/perl use integer;(\$a,\$b)=@ARGV;while(\$a){\$a%2and\$r+=\$b;\$a/=2;\$b*=2;}print \$r;``` I admit that this takes a bit of a shortcut: it checks each pair of numbers as it comes up, and adds the second to the result if necessary at that time, rather than saving them all and waiting for the end. For anyone who really likes whitespace: ```#!/usr/bin/perl use integer; (\$a, \$b) = @ARGV; while (\$a) { \$a % 2 and \$r += \$b; \$a /= 2; \$b *= 2; } print \$r; ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:17 • by SimonY (unregistered)
 let peasant a b = let rec peasant a b acc = if a = 1 then b + acc else match a%2 with | 0 -> peasant a/2 b*2 acc | 1 -> peasant a/2 b*2 acc+b in peasant a b 0

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:18 • by Dave Havlicek (unregistered)
 ruby: ```class Fixnum def *(num) cols = Array.new cols.push([self, num]) while cols.last[0] != 1 do cols.push([cols.last[0] / 2, cols.last[1] + cols.last[1]]) end cols.inject(0) { |sum, n| (n[0] % 2 == 1) ? sum + n[1] : sum } end end```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:19 • by Thuktun
 Well, that's freakishly easy. ```public class RussianPeasantMultiplication { public static int multiply(int left, int right) { int sum = 0; while (left > 0) { System.out.println("left=" + left + " right=" + right); if ((left & 1) == 1) { // if odd sum += right; // collect this row } left >>= 1; // divide by two right <<= 1; // multiply by two } return sum; } public static void main(String[] args) { int left = Integer.parseInt(args[0]); int right = Integer.parseInt(args[1]); int result = multiply(left, right); System.out.println("result=" + result); } } left=18 right=23 left=9 right=46 left=4 right=92 left=2 right=184 left=1 right=368 result=414```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:23 • by JoLoCo (unregistered)
 Here, for the sake of it, is a Sinclair BASIC version. ```10 LET a=18: LET b=23 20 LET tot=0 30 IF a<0 THEN LET a=0-a: LET b=0-b 40 IF (a/2) <> INT (a/2) AND a>0 THEN LET tot=tot+b 50 LET a= INT (a/2) 60 LET b=b*2 70 IF a>0 THEN GO TO 40 80 PRINT tot ``` Is this the first entry to feature line numbers?

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:23 • by Patrick Simpson (unregistered)
 An F# quicky: ```let rec RussianPeasantMultiplication a b = if a < 0 then -(RussianPeasantMultiplication (-a) b) else (if a % 2 = 1 then b else 0) + (if a > 1 then RussianPeasantMultiplication (a / 2) (b * 2) else 0)```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:24 • by idle (unregistered)
 untested Java, quick and dirty... public static int mult(int x, int y){ Integer x1 = new Integer(x); int result = 0; for(int i = 0; i < Integer.toBinaryString(x1).length(); i++){ if(Integer.toBinaryString(x1).endsWith("1")) result += y * (int)Math.pow(2, i); x1 = Integer.rotateRight(x1, 1); } return result; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:25 • by halber_mensch
 Extrapolated from discussion with Josh Bohde: m=lambda a,b:b*(a&1)+m(a>>1,b<<1) if abs(a)>1 else a*b 55 chars... not as short but handles all integers.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:25 • by Noah Easterly (unregistered)
 Haskell: ```let peasantMultiply a b = f a b 0 where f a b s | a < 0 = f (negate a) (negate b) s | a == 0 = s | otherwise = let (a',r) = a `divMod` 2 in f a' (2*b) (if r == 1 then s + b else s) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:26 • by klagdon (unregistered)
 Accounts for either argument being zero, also throws an exception if trying to multiply a negative number. Tested with given main() method ``` public static long multiply(long first, long second) { if(first < 0 || second < 0) { throw new IllegalArgumentException("May only multiply positive numbers"); } else if(first == 0 || second == 0) { return 0; } else if(first == 1) { return second; } else if(first % 2 == 1) { return second + multiply(first / 2, second * 2); } else { return multiply(first / 2, second * 2); } } public static void main(String[] args) { Random r = new Random(); for(int i = 0 ; i < 1000000 ; i++) { long first = (long)Math.abs(r.nextInt()); long second = (long)Math.abs(r.nextInt()); if((first * second) != multiply(first,second)) { System.out.println("Failed for " + first + " * " + second + "\t" + (first * second) + "\t" + multiply(first,second)); } } } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:26 • by Chad M (unregistered)
 ```def russian_mult(l, r): """Use Russian-peasant multiplication method. They don't understand zero or negative numbers very well, according to the description. We fix that with simple rules. If left side has negative sign, change sign of result. tdwtf at chad org """ rows = list() rows.append((l, r)) while abs(l) > 1: l = l // 2 r = r * 2 rows.append((l, r)) if l < 0: return 0 - sum(r for l, r in rows if l%2==1) else: return sum(r for l, r in rows if l%2==1) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:26 • by Dave van der Brugge (unregistered)
 So many nice solutions, yet nobody has offered a solution using XSLT yet. So here is mine. The xsl and xml code can be seen here: http://damastabrain.mine.nu/RPA/highlight.php For a better highlight function (at least Firefox), view the xsl itself: http://damastabrain.mine.nu/RPA/russianPeasantAlgorithm.xsl And ofcourse to show the outcome: http://damastabrain.mine.nu/RPA/russianPeasantAlgorithm.xml Note: it Does work with negative numbers, on either one of the two or both sides. (Integer only)

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:28 • by jjs105 (unregistered)
 ```function russian_multiply_true_lookup (left, right) { if (left == 0) return 0; if (left == 1) return right; var lookup = [{left: left, right: right}]; while (left > 1) { left = Math.floor(left / 2); right = right * 2; lookup.push({left: left, right: right}); } var result = 0; for (var index = 0; index < lookup.length; index++) if (lookup[index].left % 2 == 1) result += lookup[index].right; return result; } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:29 • by darklajid
 Forget about the sticker, I played a lot with F# today. Thanks for the motivation. ```let russianMultiplication x y = let rec l a b = seq { yield (a, b); yield! l (a>>>1) (b<<<1) } l x y |> Seq.takeWhile (fun c -> fst c > 0) |> Seq.fold (fun acc (x,y) -> if x % 2 = 1 then acc + y else acc ) 0 ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:31 • by imhe
 Accounts for 0 and negative numbers, tested with main //Earlier posted as guest, now posting as member} ```package com.timepass; public class RussianMultiply { private int mulTotal = 0; private boolean isMulTotalNegative = false; RussianMultiply(){ super(); } private void multiply(int first,int second, boolean isFirstTime){ // if any number 0 return if(first == 0 || second ==0){ return; } //check for negative numbers if(isFirstTime){ if(first < 0 && second < 0) { isMulTotalNegative = false; first = first*-1; second = second * -1; } if(first < 0){ isMulTotalNegative = true; first = first*-1; } if(second < 0){ isMulTotalNegative = true;second = second * -1; } } // first time and odd number add to total if(isFirstTime && first%2!=0){ mulTotal = mulTotal + second; } // 1st column not even , add to total int tempFirst = first/2; int tempSecond = second*2; if(tempFirst%2!=0){ mulTotal = mulTotal + tempSecond; } // first colum not 1, do it again if(tempFirst != 1){ multiply(tempFirst,tempSecond,false); } } public void multiply(int first,int second){ multiply(first,second,true); } public void clearMulTotal(){ setMulTotal(0); } public int getMulTotal() { if(isMulTotalNegative()){ return -1*this.mulTotal; } return this.mulTotal; } public void setMulTotal(int mulTotal) { this.mulTotal = mulTotal; } /** * @param args */ public static void main(String[] args) { RussianMultiply rm = new RussianMultiply(); rm.clearMulTotal(); rm.multiply(18, 23); System.out.println("Multiplication of 18 and 23:" + rm.getMulTotal()); rm.clearMulTotal(); rm.multiply(13, 12); System.out.println("Multiplication of 13 and 12:" + rm.getMulTotal()); rm.clearMulTotal(); rm.multiply(12, 12); System.out.println("Multiplication of 12 and 12:" + rm.getMulTotal()); rm.clearMulTotal(); rm.multiply(-12, -12); System.out.println("Multiplication of -12 and -12:" + rm.getMulTotal()); rm.clearMulTotal(); rm.multiply(-12, 12); System.out.println("Multiplication of -12 and 12:" + rm.getMulTotal()); } public boolean isMulTotalNegative() { return isMulTotalNegative; } // public void setMulTotalNegative(boolean isMulTotalNegative) { // this.isMulTotalNegative = isMulTotalNegative; // } } ``` Multiplication of 18 and 23:414 Multiplication of 13 and 12:156 Multiplication of 12 and 12:144 Multiplication of -12 and -12:144 Multiplication of -12 and 12:-144

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:32 • by Codism (unregistered)
 Yet another Linq solution: public static int rpm(int a, int b) { return Enumerable. Range(0, a < 2 ? 1 : (int)Math.Ceiling(Math.Log(a % 2 == 0 ? a + 1 : a, 2))) .Select(i => new { L = a / (1 << i), R = b * (1 << i) }) .Where(x => x.L % 2 != 0).Sum(x => x.R); }
 « 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 »