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-24 06:25 • by Yorick (unregistered)
 Perl, entirely without arithmetic. (\$_,\$b)=map{'.'x\$_}@ARGV; /^(.+)\1(.?)\$/,(\$_,\$b,\$c)=(\$1,\$b.\$b,\$c.(\$2&&\$b))while/../; print length\$b.\$c;

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 06:36 • by ClaudeSuck.de (unregistered)
 Matthew Verleger:int RussianSum( int A, int B ){ return A ? RussianSum(A>>2,B<<2) + (!!(A&1))*(B): 0; } "RussianSum(A>>2,B<<2) + (!!(A&1))*(B): 0;" looks more like a swearing Russian @!#&^\$

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 06:40 • by Marlon (unregistered)
 Finally the most aesthetic esoteric False version: 0 23 18 [\$\$2/2*\-[@@\$@+\@]?\$1>][2/\2*\]#%%.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 07:02 • by mol1111
 Yorick: mol1111:C Nonsense in BASIC, 20:1 Do you mean it didn't work when you tried it? I may have made a mistake when transcribing it from the emulator window, but I think I checked it thoroughly. If you type it in, please take care to use tokens for DEF FN, VAL, FN, STR\$, INT, AND and <> instead of spelling them out. Sorry, it was my mistake, I had not used tokens for keywords inside strings. Now it works perfectly! Great job! And I thought that deffn is useless...

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 08:31 • by cofiem
 Javascript version: Russian Peasant Multiplication

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 08:44 • by Corpsegrinder (unregistered)
 And a solution in AppleScript set res to 0 display dialog "First value:" default answer "" buttons {"OK"} default button 1 set firstVal to text returned of the result display dialog "Second value:" default answer "" buttons {"OK"} default button 1 set secondVal to text returned of the result repeat while secondVal is greater than or equal to 1 if secondVal mod 2 is 1 then set res to res + firstVal end if set firstVal to firstVal * 2 set secondVal to round secondVal / 2 rounding down end repeat display dialog res buttons {"OK"} default button 1

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 08:49 • by Corpsegrinder (unregistered)
 and to provide negative multipliers add if secondVal is less than 0 then set firstVal to firstVal * -1 set secondVal to secondVal * -1 end if after the first two dialogs

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 09:13 • by PopeHappyCat (unregistered)
 Another lolcode, this time following the letter of the challenge more than the spirit. LOLCODE 1.2X. Extends LOLCODE 1.2, by having a BUKKIT (array) and shift operators: SHIFTROFL BTW shift x right y bits SHIFTLOL BTW shift x left y bits HAI 1.2X OBTW THIS IS EXTENSHUN OF 1.2 IT HAS BUKKIT N SHIFT TLDR CAN HAS STDIO? I HAS A X I HAS A Y I HAS A MULTIPL VISIBLE "CAN HAS X?:)" GIMMEH X VISIBLE "CAN HAS Y?:)" GIMMEH Y X R MAEK X A NUMBR Y R MAEK Y A NUMBR HOW DUZ I RPM YR X AN YR Y I HAS A THING THING IS NOW A BUKKIT I HAS A MUTLIPL ITZ 0 I HAS A DUMMY I HAS A COUNTR ITZ 0 IM IN YR RPMLOOP UPPIN YR COUNTR WILE DIFFRINT X AN 1 DUMMY R PRODUKT OF COUNTR AN 2 THING[DUMMY] R X THING[SUM OF DUMMY AN 1] R y X R SHIFTROFL X AN 1 Y R SHIFTLOL Y AN 1 IM OUTTA YR RPMLOOP IM IN YR RPMLOOPAGAIN NERFIN YR COUNTR WILE BOTH SAEM COUNTR AN BIGGR OF COUNTR AN 0 DUMMY R PRODUKT OF COUNTR AN 2 X R THING[DUMMY] Y R THING[SUM OF DUMMY AN 1] MOD X AN 2 BOTH SAEM IT AN 1, O RLY? YA RLY, MULTIPL R SUM OF MULTIPL AN Y NO WAI, BTW NOTHING HAPPENS OIC IM OUTTA YR RPMLOOPAGAIN 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-24 09:14 • by asd (unregistered)
 > perl wtf.pl 101 6 606 eval eval '"'. ('`'| '-'). ('['^'"').('{'^'[').'(' .'\\'.'\$'.('`'|'!').',' .'\\' .'\$'. ('`'|'"').')'.('{'^'[') .'='.('{'^'[').'\\'.'@' .('`' ^'!') .('{' ^')') .('`' ^"'") .("\{"^ '-'). ';'.( "\`"| '-'). ('['^'"') .('{' ^'[') .'\\'.'\$'.('[' ^'/') .';'. ('['^ ','). ('`'| '(').('`'|')') .('`'|',' ).(('`')| '%'). "\(". ('\\'). ('\$').( "\`"| '!'). "\)". '\\'. "\{". '\\'. '\$'.( "\["^ '/').'+'.'='.'\\'.'\$'.( '`'|'"').'*'."\(".'\\'. '\$'.( "\`"| '!').'&'.('^'^('`'|'/') ).')'.';'.'\\'.'\$'.('`' |'!') .'>'. "\>". '='.( '^'^( "\`"| "\/")). "\;". '\\'. '\$'.( "\`"| '"').'*'. '='.( '^'^( '`'|',')).'\\' .'}'. ('['^ '+'). ('['^ ')'). ('`'|')').('`' |('.')).( '['^'/'). ('{'^ '['). ('\\'). ('\$').( "\["^ '/'). ';'.( "\!"^ '+'). ('!'^ '+'). "\""; \$:='.'^'~';\$~='@'|"\("; \$^=')'^'[';\$/='`'|"\."; (\$,)= "\("^ '}';\$\='`'|'!';\$:="\)"^ '}';\$~='*'|'`';\$^="\+"^ "\_"; (\$/)= "\&"| "\@"; (\$,)= "\["& '~';\$\= "\,"^ "\|"; (\$:)= "\."^ ('~');\$~= "\@"| "\("; \$^=')'^'[';\$/= "\`"| "\."; (\$,)= "\("^ "\}"; \$\='`'|'!';\$:= ')'^"\}"; \$~=('*')| "\`"; (\$^)= '+'^'_' ;\$/='&' |'@'; (\$,)= "\["& "\~"; (\$\)= "\,";

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 09:22 • by Dascandy
 flax:Nobody has submitted ARM code yet that I have seen. Does this win for smallest number of instructions? ; multiplicands in r0 and r1 mov r2,#0 loop movs r0,r0,lsr #1 addcs r2,r1 mov r1,r1,asl #1 bne loop Yours is second (I posted mine way too soon) but it is shorter and probably better tested. You don't have a return though, which I do have. IIRC I only have one opcode more though, so that would be the return.

Re: Failing Russian Peasant Multiplication

2009-07-24 09:29 • by Tachyon

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 11:19 • by Jason (unregistered)
 one line recursive c# version: static int OneLineRussian(int a, int b) { return (a==0)?0:(a%2==0)?OneLineRussian(a/2,b* 2):b+OneLineRussian(a/2,b*2); }

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 11:25 • by Ed (unregistered)
 Fairly elegant functional JavaScript 1.8 one-liner: function russian(a, b) [d for ([c, d] in function(c, d) { do { yield [c, d]; } while (d <<= 1, c >>= 1) }(a, b)) if (c & 1)].reduce(function(p, c) p + c, 0); Might work in Firefox 3; I just used the JavaScript shell.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 11:33 • by kramthegram (unregistered)
 Here is my pretty schweet python version with a test script!(sorry for any the tabs, I prefer them) def peasant(a,b): oddnums=[] while(a>1): if((a%2)!=0): oddnums.append(b) a=a/2 b=b*2 for num in oddnums: b=b+num return b for a in range(1,100): for b in range(a,100): if(peasant(a,b)!=(a*b)): print "fail!", a, b else: print "schweet!"

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 11:35 • by kramthegram (unregistered)
 Drat! Two spaces it is then! def peasant(a,b): oddnums=[] while(a>1): if((a%2)!=0): oddnums.append(b) a=a/2 b=b*2 for num in oddnums: b=b+num return b for a in range(1,100): for b in range(a,100): if(peasant(a,b)!=(a*b)): print "fail!", a, b else: print "schweet!"

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 11:44 • by kramthegram (unregistered)
 Double Drat! bbcode, I hates you def peasant(a,b): oddnums=[] while(a>1): if((a%2)!=0): oddnums.append(b) a=a/2 b=b*2 for num in oddnums: b=b+num return b for a in range(1,100): for b in range(a,100): if(peasant(a,b)!=(a*b)): print "fail!", a, b else: print "schweet!"

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 12:08 • by Nix Nada (unregistered)
 Got it to one line in a function on VBA. My proudest moment. Function RussedRightUp(nr1 As Long, nr2 As Long) As Long If nr1 > 0 Then RussedRightUp = RussedRightUp(nr1 \ 2, nr2 * 2) + nr2 * (nr1 Mod 2) End Function

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 13:49 • by curtmack
 Well, here's mine in Perl. The order of statements in the iterate function is a bit confusing, but it's all to ensure that it works in all of the unusual cases (namely, when 1 or 0 is given as the left operand). Also, it doesn't work at all when given negative numbers... but that's a flaw inherent in the method itself, not necessarily in my implementation. #!/usr/bin/perl use POSIX qw/ceil floor/; my (\$op1, \$op2) = @ARGV; sub iterate { my (\$left, \$right, \$sum) = @_; \$sum += \$right if \$left % 2; return \$sum if \$left <= 1; \$left = floor(\$left / 2); \$right *= 2; &iterate (\$left, \$right, \$sum); } my \$product = &iterate (\$op1, \$op2, 0); print "\$product\n";

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 13:58 • by Joe (unregistered)
 Excel Array Formula: =SUM(MOD(INT(A\$1/POWER(2,ROW(A1:OFFSET(A1,INT(LN(A1)/LN(2)),0))-1)),2)*POWER(2,ROW(A1:OFFSET(A1,INT(LN(A1)/LN(2)),0))-1)*\$B\$1) When pasting in the formula, instead of hitting enter, you need to press CTRL-SHIFT-ENTER to tell excel it's an array formula. First number goes in A1 Second number goes in B1

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 14:01 • by Cale Gibbard (unregistered)
 Here's a Haskell implementation using a list comprehension: multiply x y = sum [v | (u,v) <- zip (takeWhile (> 0) \$ iterate (`div` 2) x) (iterate (*2) y), odd u]

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 14:26 • by JS ROX! (unregistered)
 I LOVE me some js. Wait, is this thing on? Is there anybody still here?? Well, here are my two favorites, in js one-liners :function grif(x,y){ return x>1?(x&1?y:0)+grif(x>>1,y<<1):y; } function firg(x,y){ for(var r=0;x&1?r+=y:1;x>>=1,y<<=1)if(!x)return r; } firg is almost twice as fast as grif. and only half to a third as fast as straight multiplication, depending on the script engine. here's the instrumentation (works in WSH, or browser):]//instrumentation if(typeof(WScript!='undefined'))alert=function(msg){WScript.echo(msg);} function straight(x,y){ return x*y; } function timeMethod(method,args,loop){ var start=new Date(); for(var i=0;i

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 14:37 • by curtmack
 For an encore, I did 6502 assembly as well. It should work, but I can't test it, because I don't know enough 6502 assembly to make a program that actually does something. There's also the issue of whether or not BIT can actually be used the way I use it. The reference I used wasn't clear on the subject. Frankly, if BIT can't use constants as operands, I am going to invent a time machine, go back to 1975, and storm into MOS Technology with a pitchfork demanding to know why the hell it can't. PHA LDA #00 STA \$03 LDA \$00 _ITER BIT #01 BNE _ROLL CLC STA \$00 LDA \$03 ADC \$02 STA \$03 LDA \$00 _ROLL ASL \$02 LSR A BNE _ITER PLA RTS

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 15:26 • by raony (unregistered)
 python: f = lambda x,y, h = lambda x,y: x%2 != 0 and y or 0, g = lambda x,y: x > 1 and f(x/2, y*2) or 0: h(x,y) + g(x,y)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 16:04 • by Joel Klein (unregistered)
 Mathematica version that tries to match the algorithm as described: RussianPeasantMultiply[i_, j_] := Total@Map[#[[2]]&, DeleteCases[ NestWhileList[ Function[args, {Floor[args[[1]]/2.], args[[2]]*2}], {i, j}, First[#] =!= 1 &], {_?EvenQ, _}]] The innermost call is NestWhileList, having the form NestWhileList[f, {i,j}, test]. If you use the NestWhileList expression with {12,23} as in the example you get a matrix representing the rows and columns: {{12, 23}, {6, 46}, {3, 92}, {1, 184}} Next is the DeleteCases expression, which uses a pattern {_?EvenQ, _} to delete rows where the first element is even. Next out from that is Map[#[[2]]&, rows], which gives us just the 2nd column. Finally, the numbers from the 2nd column are passed to Total.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 17:07 • by Just another Russian peasant (unregistered)
 Just a bit on the "curious" nature of the algorithm: doubling or halving a number using abacus is fast, even faster than adding or subtracting two numbers. For example, here is the doubling algorithm: for every digit from the least significant to the most do: if digit >=5 do subtract 5 from this digit carry 1 to next digit (propagate if needed) end if double this digit continue to next digit It may look complex, but actually doesn't involve counting beads (due to the most types of abaci being bi-quinary, including the Russian one), and therefore as fast as one could move his hand. Addition or subtraction requires either counting beads, or messing with decimal half-carry (that is 4-bead wire on Russian abacus is really for; counting quarter-copecs is a marginal use).

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 18:16 • by Bob (unregistered)
 This is exercise 1.18 in Structure and Interpretation of Computer Programs

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 20:31 • by ikegami
 curtmack:For an encore, I did 6502 assembly as well. Wow, that's very similar to Varian72 (as in 1972). I helped write a number of control programs in Varian72 assembler. They're used to control CANDU nuclear power reactors and the 100s of valves of the attached boiler system. This is what's being used today! Varian72 has a richer instruction set, and supports constants (bit 15 of the address field = 1: constant; bit 15 of the address field = 0: address) For common constants, we used low memory which could be addressed using a single-word instructions. * RMUL - Russion Multiply * * Inputs: * A-REG: Multiplier * B-REG: Multiplicand * X-REG: Anything * * Outputs: * A-REG: Product * B-REG: Destroyed * X-REG: Unchanged RMUL ENTR STA MULTER Save the multiplier TZA A-REG = 0 STA PROD Init the product to zero. LDA MULTER A-REG = Multiplier RMUL01 BTA0 BT0,RMUL02 Jump over add if multiplier is even or zero TBA A-REG = Multiplicand ADD PROD A-REG = Product STA PROD Save product. LDA MULTER A-REG = Multiplier RMUL02 LSLB 1 Double the multiplicand LSRA 1 Half the multiplier STA MULTER Save the multiplier JANZ RMUL01 Loop if multiplier is non-zero RMULEX LDA PROD A-REG = Product RETU* RMUL PROD BSS 1

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 20:31 • by Dale King (unregistered)
 Features: - excessive use of goto - no bitwise operations - no mul/div/mod operations #include int peasantiply(int a, int b) { int r = 0; int h, d; firstodd: h = a; while (h > 1) { h -= 2; } d = b; if (h == 1) goto addodd; start: if (a == 0) goto done; halve: h = 0; while (a > 1) { h++; a -= 2; } a = h; doubleup: d = b; while (d > 0) { d--; b++; } d = b; addodd: h = a; while (h > 1) { h -= 2; } if (h == 1) { while (d >0) { d--; r++; } } goto start; done: return r; } int main() { printf("%d\n", peasantiply(18, 23)); }

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-24 20:34 • by mol1111

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 01:33 • by iamtim2 (unregistered)
 ;Done in Newlisp without using variables to store calculations. Making it purely functional, I believe. (define (odd? x) (= (& x 1) 1)) (define (half! x) (>> x 1)) (define (double! x) (<< x 1)) (define (b x y) (cond ((= 1 x) y) ((and (< 1 x) (odd? x)) (+ y (b (half! x) (double! y)))) ((< 1 x) (b (half! x) (double! y)))))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 06:00 • by Serpardum (unregistered)
 This is what I slapped together. It's fairly simply actually. This is C++ code but the only thing I notice right away keeping it from becoming C code is the use of bool. A friend are I were discussing the fact he would use a & 1 to check for odd/even where I would use a % 2 == 1. just because I think it's more self explanitory. #include int russianMultiply( int a, int b ) { // Multiplication on the chip may be innaccurate. // Lets use the manual way to multiply to ensure we // receive accurate results bool aneg = a < 0; if ( aneg ) a = -a; int result = 0; if ( a % 2 == 1 ) { result += b; } while ( a > 1 ) { a /= 2; b <<= 1; // I don't even trust *2 to be accurate if ( a % 2 == 1 ) { // is a odd? result += b; // It is so add our current multicant } } if ( aneg ) result = -result; return result; } int main() { std::cout << russianMultiply( 18, 23 ) << "\n"; std::cout << russianMultiply( -18, 23 ) << "\n"; std::cout << russianMultiply( 18, -23 ) << "\n"; std::cout << russianMultiply( -18, -23 ) << "\n"; }

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 06:00 • by mr.DUDA (unregistered)
 Did anyone try High-Level Shader Language? With modern video cards the program can run entirely on GPU and take no CPU time at all. Here it goes (uncomment mul operation to apply results to any 3D model; leave it commented out for screen-aligned quad): uniform float A = 37; uniform float B = 258; uniform float4x4 worldViewProj; float3 numbers[] = { { 0, 1, 0 }, { 1, 0, 1 }, { 1, 0, 1 }, { 1, 0, 1 }, { 0, 1, 0 }, { 0, 1, 0 }, { 1, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 }, { 1, 1, 1 }, { 0, 1, 0 }, { 1, 0, 1 }, { 0, 0, 1 }, { 0, 1, 0 }, { 1, 1, 1 }, { 1, 1, 1 }, { 0, 0, 1 }, { 0, 1, 0 }, { 0, 0, 1 }, { 1, 1, 1 }, { 1, 0, 1 }, { 1, 0, 1 }, { 1, 1, 1 }, { 0, 0, 1 }, { 0, 0, 1 }, { 1, 1, 1 }, { 1, 0, 0 }, { 1, 1, 0 }, { 0, 0, 1 }, { 1, 1, 0 }, { 0, 1, 1 }, { 1, 0, 0 }, { 1, 1, 0 }, { 1, 0, 1 }, { 1, 1, 0 }, { 1, 1, 1 }, { 0, 0, 1 }, { 0, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 }, { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 }, { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 1 }, { 0, 0, 1 }, { 1, 1, 0 } }; void vs_main(float4 pos : POSITION, float2 t : TEXCOORD0, out float4 oPos : POSITION, out float3 oT : TEXCOORD0) { // russian multiplication goes here float a = A, b = B, c = 0; do { float a2 = a / 2; float a2f = floor(a2); c += b * (1 - step(a2, a2f)); a = a2f; b *= 2; } while (a > 0); // pass outputs to pixel shader, convert pos to 0..1 up-down left-right oPos = pos;// mul(pos, worldViewProj); --- TODO: leave commented out for screen-space quad oT = float3(t, c); } float4 ps_main (float3 t : TEXCOORD0) : COLOR { // # of digits in result float x = t.x, y = t.y, result = t.z; float maxDigits = 1 + floor(log10(result)); // determine value and index of digit in result float idigit = (maxDigits - 1) - floor(x * maxDigits); float digit = floor(result * pow(10, -idigit)); float nonempty = digit > 0; digit -= 10 * floor(digit * 0.1); // get row and column of output number float3 row = numbers[floor((y + digit) * 5)]; float col = row[4 * fmod(x * maxDigits, 1)] * nonempty; return float4(col.xx, 1, 1); } technique { pass { VertexShader = compile vs_3_0 vs_main(); PixelShader = compile ps_3_0 ps_main(); ZEnable = false; ZWriteEnable = false; CullMode = NONE; AlphaBlendEnable = false; } } P.S. the graphic is ASCII-style but is capable to display numbers of any width

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 07:01 • by Stalker
 No hardware implementations yet? Oh well, VHDL isn't really my field (haven't done anything real in it ever) but this actually seem to work. Put factors on input and then pulse start, the result can then be read from prod on rising edge of done. library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_unsigned.all; use ieee.numeric_std.all; entity RusMulUnit is port ( clk : in std_logic; fac0 : in std_logic_vector( 19 downto 0 ); fac1 : in std_logic_vector( 19 downto 0 ); start : in std_logic; prod : out std_logic_vector( 39 downto 0 ) := (others => '0'); done : out std_logic := '0' ); end RusMulUnit; architecture bdf_type of RusMulUnit is signal fac0i : std_logic_vector( 19 downto 0 ) := (others => '0'); signal fac1i : std_logic_vector( 19 downto 0 ) := (others => '0'); signal sumi : std_logic_vector( 39 downto 0 ) := (others => '0'); begin process( clk ) begin if rising_edge( clk ) then if start = '1' then fac0i <= fac0; fac1i <= fac1; sumi <= (others => '0'); done <= '0'; else fac0i <= '0' & fac0i(19 downto 1); -- shift right fac1i <= fac1i(18 downto 0) & '0'; -- shift left if fac0i(0) = '1' then sumi <= sumi + fac1i; end if; if fac0i = 0 then done <= '1'; end if; end if; end if; if falling_edge( clk ) then if start = '1' then prod <= (others => '0'); else if fac0i = 0 then prod <= sumi; end if; end if; end if; end process; end bdf_type;

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 07:41 • by The_Assimilator (unregistered)
 Was going to submit a HLSL version as well but I thought I'd leave it up to someone more competent in HLSL than myself. :)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 10:51 • by mr.DUDA (unregistered)
 Hey, feel free to submit your version as well! My code isn't well optimized, e.g. some calculations can be moved into vertex pipeline rather than perform per-pixel; also, if еру screen quad geometry is highly tesselated, everything can perform at per-vertex basis; also, by using a texture with baked numbers we can just tex2D instead of messing with ASCII-like-grid-symbols etc. :)

standard ml version

2009-07-25 13:18 • by Kennie Nybo Pontoppidan (unregistered)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 15:11 • by Rusty Nail (unregistered)
 No hardware implementations yet? There's a schematic version and a verilog version way back in the flood of posts :)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 15:25 • by mol1111
 Rusty Nail:No hardware implementations yet? There's a schematic version and a verilog version way back in the flood of posts :) ikegami circuit diagram 278370 Rusty Nail Verilog 279040

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 16:49 • by Ben (unregistered)
 A bit late to this party, but here's my take: #include #define is_odd(num) (num % 2 != 0) /* Multiply two numbers together, in the manner of Russian peasants. */ /* This method expects and accepts only non-negative integers. */ int multiply(int lh, int rh) { assert(lh >= 0 && rh >= 0); int total = 0; while (lh > 0) { if (is_odd(lh)) total += rh; lh /= 2; rh *= 2; } return total; }

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 19:20 • by mol1111
 Does anybody has some idea in what language is this entry: Wheaties 278426 written? I was able to indentify all others, but this one remains mystery.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 20:05 • by Stalker
 Oops. Guess I fell asleep after a few hundred posts. Anyway, here's an implementation in a language having some neat functions but otherwise severely lacking (no bitwise and, no shift etc). function integer mul: integer f0, integer f1 begin mul = 0; while f0 > 0 do // Just because we can function boolean isEven: integer n begin isEven = n == (n / 2) + (n / 2); end; if !isEven( f0 ) then mul = mul + f1; end; f0 = f0 / 2; f1 = f1 + f1; end; end; procedure main: begin // Test it for x = 0 to 100 do for y = 100 to 0 step -1 do output x * y; output mul( x, y ); end; end; end;

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-25 20:34 • by Paul Marfleet (unregistered)
 Solution in F#: let multiply a b = let rec getWorkings a b lst = match a with | 1 -> lst | _ -> let c, d = a / 2, b * 2 getWorkings c d (lst @ [(c, d)]) let result = getWorkings a b [] |> Seq.filter (fun (a, b) -> a % 2 = 1) |> Seq.map (fun (a, b) -> b) |> Seq.fold (fun acc b -> acc + b) 0 result printf "%d" (multiply 18 23)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-26 00:40 • by fuggit (unregistered)
 Haskell! mul 0 y = 0 mul x y | x < 0 = -(mul (- x) y) mul x y = mul (x `div` 2) (y * 2) + if (even x) then 0 else y

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-26 05:43 • by Paul Marfleet (unregistered)
 Refined F# solution: let multiply a b = let rec getResult a b sum = match a with | 1 -> sum | _ -> let c, d = (a / 2), (b * 2) match c with | x when c % 2 = 1 -> getResult c d (sum + d) | _ -> getResult c d sum match a with | 0 -> 0 | 1 -> b | _ -> getResult a b 0

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-26 06:25 • by f_ranek (unregistered)
 Writen in Java, works for both nonnegative and negative numbers. Int type can be used as well as long. long multiply(long a1, long a2) {     long res = 0;     for (; a1 != 0; a1 >>>= 1, a2 <<= 1)         if ((a1&1) != 0)             res += a2;     return res; }

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-26 09:28 • by f_ranek (unregistered)
 @echo off :: WindowsXP CMD script :: Usage: save to file multiply.cmd, call multiply.cmd -13 56 :: Correct negative numbers handling set result=0 set a=%1 set b=%2 if %a% lss 0 ( set /a a = -a set /a b = -b ) :loop if %a% equ 0 goto :endx set /a tmp = "a & 1" if not %tmp% equ 0 set /a result += b set /a "a >>= 1" set /a "b <<= 1" goto loop :endx echo %result%

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-26 10:28 • by Alex Muscar (unregistered)
 Common Lisp: This is a long one :). Assuming that function composition and unfold are provided by a library (eventually sigfun too, but it's not such a useful function after all) the implementation would be made out of rpm5-aux and rpm5. This is just because i wanted the implementation to be functional (sorta'). (declaim (inline comp)) (defun comp (f g) (lambda (&rest args) (funcall f (apply g args)))) (defun unfold* (f &rest s) (multiple-value-bind (c s) (apply f s) (when c (cons c (apply #'unfold* f s))))) (declaim (inline sigfun)) (defun sigfun (n) (if (minusp n) #'- #'+)) (defun rpm5-aux (m n) (when (> m 0) (values (list m n) (list (ash m -1) (ash n 1))))) (defun rpm5 (m n) (let* ((ns (unfold* #'rpm5-aux (abs m) n))) (reduce (sigfun m) (delete-if (comp #'evenp #'car) ns) :initial-value 0 :key #'cadr)))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-26 10:46 • by Alex Muscar (unregistered)
 This is so nice :).

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-26 11:55 • by Alex Muscar (unregistered)
 Common Lisp: Corrected version of the tail recursive variant: (defun rpm7 (m n) (labels ((rec (m n acc) (if (= m 0) acc (rec (ash m -1) (ash n 1) (if (oddp m) (+ acc n) acc))))) (funcall (sigfun m) (rec (abs m) n 0))))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-26 13:25 • by Михаил (unregistered)