# 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 20:19 • by Twey (unregistered)
 This is, of course, a one- or two-liner (depending how long you like your lines) in Haskell and probably most other functional languages: ```-- Just for neatness; without this, ((`div` 2) *** (* 2)) can be -- written (\(a, b) -> (a `div` 2, b * 2)) import Control.Arrow ((***)) rus n m = sum . map snd . filter ((/= 0) . (`mod` 2) . fst) . takeWhile ((> 0) . fst) \$ iterate ((`div` 2) *** (* 2)) (n, m) ``` Or adding some labels for clarity: ```rus n m = sum . rightColumn . filter hasOddRight . takeWhile nonZeroLeft \$ makeColumns (n, m) where rightColumn = map snd hasOddRight = (/= 0) . (`mod` 2) . fst makeColumns = iterate multiplyAndDivide multiplyAndDivide = ((`div` 2) *** (* 2)) nonZeroLeft = ((> 0) . fst) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:22 • by Mike McNally (unregistered)
 oops the last 2 lines are busted (great idea to refactor just before posting :-) ``` rsum([M, N} | P], S) -> rsum(P, S + case M rem 2 of 0 -> 0; 1 -> N end). ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:34 • by tdh (unregistered)
 Not the shortest or simplest bit of code, but a pretty elegant way of mirroring the Russian Peasant method, as opposed to looking more like binary multiplication. Python: ```def multiply(a, b): def pairs(): nonlocal a, b while a: yield a, b a //= 2 b *= 2 return sum(j for (i, j) in pairs() if i % 2) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:19 • by brian (unregistered)
 I'm sure this is lost in the haze: ```int peasant(int x, int y) { int result = 0; do { result += (x % 2) * y; x /= 2; y *= 2; } while(x > 0); return result; } ``` Didn't bother with bitshifting. Looking at the generated assembly is an interesting excersize.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:25 • by 0ffh (unregistered)
 I feel daring today and throw this in untested. thx for spoiler alert i did it in a text editor before scrolling down to comment. =) // russian multiply // the usual limitations on result size apply int ru_mul(int fac0,int fac1) { int prod=0; do { prod+=(fac0&1)*fac1; fac1<<=1; } while (fac0>>=1); return prod; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:27 • by 0ffh (unregistered)
 the wtf is of course that my spaces got eaten... =)

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:35 • by Bob (unregistered)
 echo "In soviet russia, multiplication does YOU!"

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:48 • by 0ffh (unregistered)
 nah, the real wtf is: ye shouldnae do sucha thing that i did there: late night surfing on coding sites while not sober. speaking of test-driven development, hihi! i inadvertedly coded for unsingeds... take brians solution!

### Yet another C# version, with tests

2009-07-22 21:50 • by Thomas Eyde (unregistered)
 ```using Microsoft.VisualStudio.TestTools.UnitTesting; namespace RussianPeasantMultiplication { /// /// The biggest WTF, of course, is there are tests! /// [TestClass] public class Multiply_numbers { [TestMethod] public void Multiply_some_numbers() { Assert.AreEqual(18*23, WtfPeasantCalculator.Multiply(18, 23)); Assert.AreEqual(0*1, WtfPeasantCalculator.Multiply(0, 1)); Assert.AreEqual(1*0, WtfPeasantCalculator.Multiply(1, 0)); Assert.AreEqual(11*13, WtfPeasantCalculator.Multiply(11, 13)); } [TestMethod] public void Multiply_with_cryptic_version() { Assert.AreEqual(18*23, CrypticPeasantCalculator.Multiply(18, 23)); } } /// /// What kind of entry would it be, if the expected code quality wasn't posted? /// internal static class CrypticPeasantCalculator { public static long Multiply(int a, int b) { return a < 1 ? 0 : (a%2 != 0 ? b : 0) + Multiply(a/2, b*2); } } /// /// Another WTF is to actually try to write readable, understandable code. /// internal static class WtfPeasantCalculator { public static long Multiply(int a, int b) { if (ThereIsNothingLeftToAccumulate(a)) return 0; return ValueToAccumulate(a, b) + FollowingAccumulatedValues(a, b); } private static bool ThereIsNothingLeftToAccumulate(int a) { return a < 1; } private static int ValueToAccumulate(int a, int b) { return IsOddNumber(a) ? b : 0; } private static bool IsOddNumber(int number) { return number%2 != 0; } private static long FollowingAccumulatedValues(int a, int b) { return Multiply(a/2, b*2); } } } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:00 • by Mr.'; Drop Database -- (unregistered)
 ```def russianpeasants(x, y): print 'Useless waste of time. Any idiot could write this.' def multiply(x, y): if x < 0 and y < 0: x = -x; y = -y elif x < 0 or y < 0: return -multiply(abs(x), abs(y)) if x == 0 or y == 0: return 0 if x == 1 or y == 1: return x+y-1 bits = 0; tempx = x; tempy = y while tempx: tempx >>= 1; bits += 1 while tempy: tempy >>= 1; bits += 1 bits >>= 2 a = x >> bits; b = x & ((1 << bits) - 1) c = y >> bits; d = y & ((1 << bits) - 1) ac = multiply(a, c); bd = multiply(b, d) abcd = multiply(a+b, c+d) return (bd + ((abcd - bd - ac) << bits) + (ac << (bits + bits)))```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:18 • by bluebearr (unregistered)
 Got to add AutoIt: ```Func _RussianMultiplication( \$var1, \$var2) Dim \$iResult=0, \$iLeft = \$var1, \$iRight = \$var2 While Abs(\$iLeft) >= 1 If StringInStr("13579", StringRight(\$iLeft, 1)) > 0 Then \$iResult+=\$iRight \$iLeft = Int(\$iLeft/2) \$iRight *= 2 WEnd If \$var1 < 0 Then \$iResult *= -1 Return \$iResult EndFunc```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:22 • by Joel (unregistered)
 Short recursive C# technique: ```int Russian(int left, int right, int progress){ if(x==0) return progress; return Russian(left/2, right*2, progress+((left%2==1)?right:0)); }```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:44 • by Bruce (unregistered)
 This actually misses adding the first row if the initial lval is odd.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:46 • by Bruce (unregistered)
 (sorry, I meant the first sample given)

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:51 • by J (unregistered)
 Tail-recursive Mathematica implementation: RussianPeasantTimes[x_Integer, y_Integer] := Sign[x] RussianPeasantTimesImpl[Abs[x], y, 0]; RussianPeasantTimesImpl[x_, y_, res_] := RussianPeasantTimesImpl[Quotient[x, 2], 2 y, res + Mod[x, 2] y]; RussianPeasantTimesImpl[1, y_, res_] := res + y; RussianPeasantTimesImpl[0, _, res_] := res;

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:14 • by noSignal (unregistered)
 Scheme: (define peasant (lambda (x y) (letrec ((loop (lambda (ls1 ls2) (if (eq? (car ls1) 1) (apply + (select odd? ls1 ls2)) (loop (cons (quotient (car ls1) 2) ls1) (cons (* 2 (car ls2)) ls2)))))) (loop (list x) (list y)))))

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:17 • by noSignal (unregistered)
 I salute you sir!

### Re: Programming Praxis: Russian Peasant Multiplication

 I found a neat little trick to it. See if you can figure out what I did ;-) : ```uint32_t multiply(uint32_t a, uint32_t b) { uint64_t ab = 0; uint32_t r = 9; while (--r) { ab <<= 4; ab |= ((0xf7b3d591e6a2c480ULL>>((a&0xF)<<2)) & 0xF); a >>= 4; } ab <<= 32; ab |= b; while (ab >> 32) { if (ab >> 63) r += ab; ab <<= 1; ab &= 0xFFFFFFFEFFFFFFFFULL; } return r; } ``` I stress tested this (with 100 million random trials against the * operator) on an x86 and a PPC machine, so it works, trust me.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:20 • by noSignal (unregistered)
 You spent more than 5 minutes on a 3 minute problem. Congratulations.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:25 • by jnz
 Here's a version in C that multiplies two 8-bit numbers and produces a 16-bit result. It requires a 64-bit unsigned type. I know it doesn't look much like the original algorithm but that's because it treats the 64-bit variables as an array of 8-bit values that can be operated on in parallel. ```unsigned int mult(unsigned char a, unsigned char b) { uint64_t x, y; x = a; y = b; x |= x << 7; y |= y << 8; x |= x << 14; y |= y << 16; x |= x << 28; y |= y << 32; x &= 0x0101010101010101ULL; x = (0x8080808080808080ULL - x) ^ 0x8080808080808080ULL; x &= y; x = (x & 0x00FF00FF00FF00FFULL) + ((x & 0xFF00FF00FF00FF00ULL) >> 7); x = (x & 0x0000FFFF0000FFFFULL) + ((x & 0xFFFF0000FFFF0000ULL) >> 14); x = (x & 0x00000000FFFFFFFFULL) + ((x & 0xFFFFFFFF00000000ULL) >> 28); return (unsigned int)x; }```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:28 • by JXO (unregistered)
 C code. FACTOR can be changed to another integer > 1 without breaking the code. ```#define FACTOR 2 unsigned int ruski_mul(unsigned int a, unsigned int b) { unsigned int result = 0; while (a >= 1) { result += (a % FACTOR) * b; a /= FACTOR; b *= FACTOR; } return result; } ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:45 • by zcl (unregistered)
 Yes ,your article is very good, we have the same belief with you,so let me introduce the area to you.Now Juicy Jewelry become more adn more popular within all kind of people. Juicy couture is a kind of juicy series . It won a good reputation. Juicy sale often held its regular discount juicy activities,such as juicy charms,cheap juicy and so on.In these activities juicy couture sale got great success. juicy couture consists of two main aspects, juicy couture jewelry and juicy couture accessories Juicy couture series are worthwhile than other juicy on sales. They have a lot of discounted jewelry,for example discount Juicy Couture necklaces, juicy earrings , juicy bracelets and rings on sale. Benefit from the discount,you can get juicy jewelry save up to 30%, We assure you of our best services at all times.

### Re: Programming Praxis: Russian Peasant Multiplication [JavaScript implementation]

2009-07-23 00:14 • by Chris (unregistered)
 Here my implementation i JavaScript (yeah, I know, not a programming language :D ) Ok, the WTF is also that it doesn't work in IE, and looks funny in Opera. And that it's a bit long, not because of the calculation, but because of the whizbang :) ```
Multiply: By:
Russian Peasant Multiplication
```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:33 • by Julian Calaby (unregistered)
 Bash: abusing the arithmetic evaluation to fit the bulk of the algorithm on one line. (Everything except the line starting with echo is to handle the first argument being negative.) ```#! /bin/bash if [ \$1 -lt 0 ]; then \$0 \$(( \$1 * -1 )) \$(( \$2 * -1 )) else echo \$(( \$([ \$((\$1 & 1)) -eq 1 ] && echo \$2 +) \$(if [ \$1 -gt 1 ]; then \$0 \$((\$1 >> 1)) \$((\$2 << 1)); else echo 0; fi) )) fi``` Remove the outermost arithmetic brackets on the second last line to see the working. (Note that this doesn't work unless it's in an actual script file and called as such)

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:37 • by cmugford
 Couldn't see if this had been done - but anyway how about some F#. ```let rec multiply x y = match x with | 0 -> 0 | 1 -> y | -1 -> -y | x when x % 2 = 0 -> multiply (x / 2) (y * 2) | x when x > 0 -> y + multiply (x / 2) (y * 2) | x when x < 0 -> -y + multiply (x / 2) (y * 2); ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:50 • by James (unregistered)
 If you've got a copy of Excel you can always do it this way, and lets face if, if you've got Excel why wouldn't you? ----- Sub WhyOhWhy() Dim iRowNo As Integer Dim sValue As String iRowNo = 2 sValue = InputBox("Enter first value to mulitply", "Peasant Multiply") If sValue = "" Then MsgBox "You're not playing the game..." Do Until sValue <> "" sValue = InputBox("Enter first value to mulitply", "Peasant Multiply") If Not IsNumeric(sValue) Then MsgBox "You're not playing the game..." sValue = "" Else If CLng(sValue) > 33554431 Then MsgBox "Upper limit on first number is 33,554,431" sValue = "" End If End If Loop End If Cells(iRowNo, 3).Value = CLng(sValue) sValue = InputBox("Enter second value to mulitply", "Peasant Multiply") If sValue = "" Then MsgBox "You're not playing the game..." Do Until sValue <> "" sValue = InputBox("Enter second value to mulitply", "Peasant Multiply") If Not IsNumeric(sValue) Then MsgBox "You're not playing the game..." sValue = "" End If Loop End If Cells(iRowNo, 4).Value = CLng(sValue) Cells(iRowNo, 3).Interior.ColorIndex = 36 Cells(iRowNo, 4).Interior.ColorIndex = 36 Cells(iRowNo, 5).Interior.ColorIndex = 45 Cells(iRowNo, 5).FormulaR1C1 = "=SUM(R[1]C:R[24]C)" iRowNo = iRowNo + 1 Cells(iRowNo, 3).Value = Cells(iRowNo, 3).Value Cells(iRowNo, 4).Value = Cells(iRowNo, 4).Value Cells(iRowNo, 5).FormulaR1C1 = "=IF(RC[-2]<>"""",IF(MOD(RC[-2],2)<>0,RC[-1],0),"""")" For iRowNo = 3 To 26 Cells(iRowNo, 3).FormulaR1C1 = "=IF(OR(R[-1]C=1,R[-1]C=""""),"""",INT(R[-1]C/2))" Cells(iRowNo, 4).FormulaR1C1 = "=IF(RC[-1]<>"""",R[-1]C*2,"""")" Cells(iRowNo, 5).FormulaR1C1 = "=IF(RC[-2]<>"""",IF(MOD(RC[-2],2)<>0,RC[-1],0),"""")" Next iRowNo MsgBox "There you go, the answer is " & Format(Cells(2, 5).Value, "#,##0") End Sub

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:56 • by iamtim2 (unregistered)
 In Newlisp. I came up with & on my own but after reading Tim's version, I used >> and <<. Mine's tested. ; odd? (= (& col1 1) 1) instead of (= (% col1 2) 0) ; half! (>> col1 1) instead of (/ col1 2) ; double! (<< col2 1) instead of (* col2 2) ; because %, / and * are expensive (define (rus col1 col2) (let ((t 0)) (do-until (< col1 1) (if (= (& col1 1) 1) (setq t (+ col2 t))) (println col1 " x " col2) (set 'col1 (>> col1 1) 'col2 (<< col2 1))) (println t)))

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:59 • by jvmbsd7 (unregistered)
 ;; Scheme using the design recipe and optimized for lowest number of iterations (define (russian-multiply m n) (define (russian-multiply* x y p) (if (zero? x) p (russian-multiply* (quotient x 2) (+ y y) (if (odd? x) (+ p y) p)))) (if (< m n) (russian-multiply* m n 0) (russian-multiply* n m 0)))

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 01:29 • by agrif (unregistered)
 these are all in python the first is the most verbose: ```def russian(x, y): def generate_list(x, y): while x != 0: yield x, y x /= 2 y *= 2 def filter_even(i): if i[0] % 2 == 0: return False return True def drop_first_column(i): return i[1] l = generate_list(x, y) l = filter(filter_even, l) l = map(drop_first_column, l) return sum(l) ``` The next one is less verbose, but still easy to follow: ```def russian(x, y): l = [] while x != 0: if x % 2: l.append(y) x /= 2 y *= 2 return sum(l) ``` Personally, I like this one for it's complete incomprehensibility (and that it says "lambda f,a,b:a", which makes me laugh): ```russian = lambda x,y:(lambda f:f(f,x,y))(lambda f,a,b:a and f(f,a/2,b*2)+a%2*b) ``` agrif - 71aaeb8b415a620bf185b6093ebaf5c5

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 01:35 • by Chris Walton (unregistered)
 No branches in the innerloop. Should run pretty fast. C-version: ```int russianMul(int a, int b) { int s = 0; while(a > 1) { b <<= 1; a >>= 1; s += b & -(a & 1); } return s; } ``` x86 Assembly version, as compiled by MSVC ```00401000 xor eax,eax 00401002 cmp ecx,1 00401005 jle russianMul+1Dh (40101Dh) 00401007 push esi 00401008 sar ecx,1 0040100A mov esi,ecx 0040100C and esi,1 0040100F add edx,edx 00401011 neg esi 00401013 and esi,edx 00401015 add eax,esi 00401017 cmp ecx,1 0040101A jg russianMul+8 (401008h) 0040101C pop esi ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 01:38 • by arke
 Chris Walton:... Oops, I probably should have logged in. :) Something to add - my version doesn't need the actual CPU's multiply or divide instructions, making it feasible to implement on some processor that doesn't have that. Also, in its current incarnation, it depends on 2's Complement numbers being used.

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:11 • by sxeraverx
 int mult(int a, int b) { return a*b; } /*because that's how computers do it in hardware, anyway.*/

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:14 • by Mr M (unregistered)
 The question is, why would I want to?

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:23 • by Philipp (unregistered)
 Qwertyuiopas:I know everybody wants it :) Hopefully none of it was removed. Also, everything after the first . is disabled debugging code. Remove the [-] to see what is left of the memory. >>>>>,>>,[->+>+<<]<<[[-[>+<-]>[>+>>>+<<<<-[[<+>-]>[-]<]]<]>>[>>[-]<<[-]]+>[->>>>>++>++<<<<<<]>>]>>>>[-]<<<<<<<[<<<<<]>>>>>[>>[->>>>>+<<<<<]>>>]>>.[-][<<<<<<<[<<<<<]>>>.>.>[.>.>.>.>.>].>.>.] Ok, so how do I run that? I tried the "Brainfuck Interpreter" (http://koti.mbnet.fi/villes/php/bf.php), but I couldn't get any meaningful result. How do I set the input? Otherwise: Coolest solution so far -- imho.

### Re: Programming Praxis: Russian Peasant Multiplication

 zcl: Yes ,your article is very good, we have the same belief with you,so let me introduce the area to you.Now Juicy Jewelry become more adn more popular within all kind of people. Juicy couture is a kind of juicy series . It won a good reputation. Juicy sale often held its regular discount juicy activities,such as juicy charms,cheap juicy and so on.In these activities juicy couture sale got great success. juicy couture consists of two main aspects, juicy couture jewelry and juicy couture accessories Juicy couture series are worthwhile than other juicy on sales. They have a lot of discounted jewelry,for example discount Juicy Couture necklaces, juicy earrings , juicy bracelets and rings on sale. Benefit from the discount,you can get juicy jewelry save up to 30%, We assure you of our best services at all times. Can we please end the off-topic rants about Russian peasant multiplication and get back to our juicy jewelry discussion?

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:32 • by Alex Muscar (unregistered)
 Common Lisp: This time it does the expected thing when the first number is negative instead of looping forever :) ```(defun rpm4 (m n &optional (acc 0)) (do ((aux (abs m) (ash aux -1))) ((= aux 0) (if (< m 0) (- 0 acc) acc)) (incf acc (if (oddp aux) n 0)) (incf n n))) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:45 • by Alex Muscar (unregistered)
 Common Lisp: ```(defun rpm4 (m n) (do ((t1 (abs m) (ash t1 -1)) (t2 n (ash t2 1)) (acc 0 (+ acc (if (oddp t1) t2 0)))) ((= t1 0) (if (< m 0) (- 0 acc) acc)))) ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:08 • by mneimeyer
 This feels a little "me too" at this point but I've tried to follow all the "rules". Here's PHP that accounts for negative numbers, doesn't use * or /, accounts for 0 in either position and generates nifty colored output.
".\$a."".\$b."
x
"; if(!\$a || !\$b) { return 0; } if(\$a < 0) { \$a = (\$a^-1)+1; \$b = (\$b^-1)+1; } return ((\$a <= 1)?(\$a?\$b:0):((intval(\$a&1)?\$b:0)+Russian(intval(\$a>>1),\$b<<1))); } ?>Russian Peasant Quick: ".(\$_GET['a']*\$_GET['b'])."

\n"; echo "\n"; \$c = Russian(\$_GET['a'],\$_GET['b']); echo "\n
Sum:".\$c."
"; echo "\n"; } ?>

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:14 • by Hidayat (unregistered)
 Another using Oracle PL/SQL ```create or replace function russian(p in number, q in number) return number is res number; begin select sum( decode(mod(floor(p/power(2,level-1)),2),0,0,1) * q * power(2,level-1) ) into res from dual where floor(p/power(2,level-1))>0 connect by level

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:15 • by demo (unregistered)
 #include template struct is_odd { enum { value = I % 2 }; }; template struct russian_impl; template struct russian_impl { enum { value = B + russian_impl::value>::value }; }; template struct russian_impl { enum { value = russian_impl::value>::value }; }; template struct russian_impl<1, B, 1> { enum { value = B }; }; template struct russian { enum { value = russian_impl::value>::value }; }; int main(int argc, char* argv[]) { std::cout << russian<18, 23>::value << std::endl; return EXIT_SUCCESS; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:56 • by Don Knisley (unregistered)
 In VBA Function RussianPeasantMultiplication() Dim a As Integer, b As Integer, c As Integer a = 18 b = 23 Debug.Print a & " x " & b Do Until a = 1 a = Int(a / 2) b = b * 2 If a / 2 <> Int(a / 2) Then c = c + b Debug.Print a & vbTab & b & vbTab & b Else Debug.Print a & vbTab & b End If Loop Debug.Print vbTab & vbTab & c End Function

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:59 • by SlyEcho
 CREATE FUNCTION Peasant_Mul (@A INT, @B INT) RETURNS INT AS BEGIN     DECLARE @Result INT;     WITH f AS (         SELECT @A A, @B B         UNION ALL         SELECT A / 2, B * 2 FROM f WHERE A > 1     )     SELECT @Result = SUM(B) FROM f     WHERE A % 2 = 1;     RETURN @Result; END GO

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:04 • by subanark
 Here is my solution in Java. It supports really big numbers and does pretty much what you do in Russian peasant multiplication. public static BigInteger multiply(BigInteger a, BigInteger b) { BigInteger two = BigInteger.valueOf(2); ArrayList numsToAdd = new ArrayList(); while(!a.equals(BigInteger.ONE)) { if(a.mod(two).equals(BigInteger.ONE)) numsToAdd.add(b); a = a.divide(two); b = b.multiply(two); } //trick: b already holds the last line for(BigInteger n : numsToAdd) b = b.add(n); return b; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:07 • by Toby Gray (unregistered)
 In Perl: print "Enter sum in form \"a x b\":\n";\$_=<>; s!(\n|^)(\d+) x (\d+)\n\$!"\$1\$2 x \$3\n".int((\$2)/2)." x ".(\$3 * 2)."\n"!e while!/^1 x \d+\$/m; s!(\n|^)(\d*[24680]) x (\d+)!\$1-(\$2 x \$3)-!g; \$v+=\$2 while/(\n|^)\d+ x (\d+)/g;\$_.="\nTotal: \$v\n"; print "Paper working is:\n\$_";

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:10 • by freewildebeest
 Repost now I've worked out how to create an account... In Perl: print "Enter sum in form \"a x b\":\n";\$_=<>; s!(\n|^)(\d+) x (\d+)\n\$!"\$1\$2 x \$3\n".int((\$2)/2)." x ".(\$3 * 2)."\n"!e while!/^1 x \d+\$/m; s!(\n|^)(\d*[24680]) x (\d+)!\$1-(\$2 x \$3)-!g; \$v+=\$2 while/(\n|^)\d+ x (\d+)/g;\$_.="\nTotal: \$v\n"; print "Paper working is:\n\$_";

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:15 • by astander (unregistered)
 private int RussianMultiply(int input1, int input2) { int retVal = 0; do { retVal += (input1 & 1) * input2; input1 = input1 >> 1; input2 = input2 << 1; } while (input1 > 0); return retVal; }

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:45 • by k1 (unregistered)

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:58 • by k1 (unregistered)
 whoops... k1: 420 PRINT "THE PRODUCT IS "; A 430 END 420 PRINT "THE PRODUCT IS "; A * SIGN There, fixed. CYA

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 05:29 • by Boneist (unregistered)
 Oracle SQL version, showing the working out: ```with my_data as (select :p1 col1, :p2 col2 from dual), list_gen as (select level -1 lvl from my_data connect by power(2,level-1) <= col1), results as (select lvl, floor(col1/power(2,lvl)) col3, col2*power(2, lvl) col4 from my_data, list_gen) select col3, col4, decode(floor(col3/2)*2, col3, null, sum(case when floor(col3/2)*2 != col3 then col4 end) over (order by lvl)) sum_col from results order by lvl ```

### Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 05:49 • by C (unregistered)
 ; EDX:EAX <- ECX * EBX (untested) ; (all other gp registers trashed) MOV ECX, multiplicand MOV EBX, multiplier multiply: XOR EAX, EAX XOR EDX, EDX CMP ECX, EAX JNL .ps NEG ECX NEG EBX .ps: XOR EDI, EDI CMP EBX, EAX SBB EBP, EBP SHR ECX, 1 JZ .nd .lp: SBB ESI, ESI MOV EDI, ESI AND ESI, EBX AND EDI, EBP ADD EBX, EBX ADC EBP, EBP ADD EAX, ESI ADC EDX, EDI SHR ECX, 1 JNZ .lp .nd: SBB ESI, ESI MOV EDI, ESI AND ESI, EBX AND EDI, EBP ADD EAX, ESI ADC EDX, EDI ; done ; ... or just use IMUL
 « 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 »