The Daily WTF: Curious Perversions in Information Technology

cofiem · 2009-07-24 Reply Admin

Javascript version:

<!DOCTYPE html> <html> <head> <title> Russian Peasant Multiplication</title> <script> function RussianMultiply(num1, num2){

		var total = 0;
		var easymultiply = num1*num2;
		
		while(num1 > 0){
			var newNum1 = Math.floor(num1/2);
			var newNum2 = num2*2;
			if(Math.floor(newNum1/2) != newNum1/2){
				total += newNum2;
			}
			num1 = newNum1;
			num2 = newNum2;
		}
		document.getElementById('results').innerHTML += "Russian result: "+total+" ("+easymultiply+")<br>";
	}

</script>

2009-07-24 Reply Admin

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

2009-07-24 Reply Admin

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

2009-07-24 Reply Admin

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 <x> <y> BTW shift x right y bits SHIFTLOL <x> <y> 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

2009-07-24 Reply Admin

perl wtf.pl 101 6 606

eval eval '"'.


('`'|                       '-').  ('['^'"').('{'^'[').'(' .'\\'.'$'.('`'|'!').','
 .'\\'                     .'$'.   ('`'|'"').')'.('{'^'[') .'='.('{'^'[').'\\'.'@'
  .('`'       ^'!')       .('{'             ^')')          .('`'
   ^"'")     .("\{"^     '-').              ';'.(          "\`"|
    '-').   ('['^'"')   .('{'               ^'[')          .'\\'.'$'.('['
     ^'/') .';'. ('['^ ',').                ('`'|          '(').('`'|')')
      .('`'|','   ).(('`')|                 '%').          "\(".
       ('\\').     ('$').(                  "\`"|          '!').
        "\)".       '\\'.                   "\{".          '\\'.
'$'.(                       "\["^  '/').'+'.'='.'\\'.'$'.( '`'|'"').'*'."\(".'\\'.
 '$'.(                     "\`"|   '!').'&'.('^'^('`'|'/') ).')'.';'.'\\'.'$'.('`'
  |'!')       .'>'.       "\>".             '='.(          '^'^(
   "\`"|     "\/")).     "\;".              '\\'.          '$'.(
    "\`"|   '"').'*'.   '='.(               '^'^(          '`'|',')).'\\'
     .'}'. ('['^ '+'). ('['^                ')').          ('`'|')').('`'
      |('.')).(   '['^'/').                 ('{'^          '[').
       ('\\').     ('$').(                  "\["^          '/').
        ';'.(       "\!"^                   '+').          ('!'^
'+').                       "\"";  $:='.'^'~';$~='@'|"\("; $^=')'^'[';$/='`'|"\.";
 ($,)=                     "\("^   '}';$\='`'|'!';$:="\)"^ '}';$~='*'|'`';$^="\+"^
  "\_";       ($/)=       "\&"|             "\@";          ($,)=
   "\["&     '~';$\=     "\,"^              "\|";          ($:)=
    "\."^   ('~');$~=   "\@"|               "\(";          $^=')'^'[';$/=
     "\`"| "\."; ($,)= "\("^                "\}";          $\='`'|'!';$:=
      ')'^"\}";   $~=('*')|                 "\`";          ($^)=
       '+'^'_'     ;$/='&'                  |'@';          ($,)=
        "\["&       "\~";                   ($\)=          "\,";

Dascandy · 2009-07-24 Reply Admin

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.

Tachyon · 2009-07-24 Reply Admin

Slightly evil asp.net dynamicly created controls version. Why hasn't anyone done an asp.net version (yet)?

using System; using System.Web.UI; using System.Web.UI.WebControls; using System.Data;

public partial class Default : Page { protected void Page_Load(object sender, EventArgs e) { if (IsPostBack) { TextBox t1 = form1.FindControl("m1") as TextBox; TextBox t2 = form1.FindControl("m2") as TextBox; if ((t1.Text.Length > 0) && (t2.Text.Length > 0)) { int mu1 = int.Parse(t1.Text); int mu2 = int.Parse(t2.Text); DataRow dr = d.Tables[0].NewRow(); dr[0] = mu1; dr[1] = mu2; d.Tables[0].Rows.Add(dr); d.Tables[0].AcceptChanges(); DoRussian(); l1.Text = "Result is : "; int ret = 0; foreach (DataRow dre in d.Tables[0].Rows) { int fi1 = (int)dre[0]; double fi = (double)fi1; double f = fi / 2; if (f != (fi1 / 2)) { ret += (int)dre[1]; } } l1.Text += ret.ToString(); } } g.DataSource = d; g.DataBind(); }

protected override void OnInit(EventArgs e)
{
    base.OnInit(e);
    Panel p2 = new Panel();
    Label m = new Label();
    m.Text = "Enter two numbers: ";
    TextBox m1 = new TextBox();
    m1.ID = "m1";
    m1.MaxLength = 3;
    TextBox m2 = new TextBox();
    m2.ID = "m2";
    m2.MaxLength = 3;
    m1.Text = "4";
    m2.Text = "6";
    Label s = new Label();
    s.Text = " &nbsp; &nbsp; ";
    Label s1 = new Label();
    s1.Text = " &nbsp; &nbsp; ";
    p2.Controls.Add(m);
    p2.Controls.Add(m1);
    p2.Controls.Add(s);
    p2.Controls.Add(m2);
    p2.Controls.Add(s1);
    Button b = new Button();
    b.Text = "Do it!";
    p2.Controls.Add(b);
    d.Tables.Add(new DataTable("Russian"));
    d.Tables[0].Columns.Add("First", typeof(int));
    d.Tables[0].Columns.Add("Second", typeof(int));
    g.CellPadding = 2;
    g.CellSpacing = 2;
    g.BorderWidth = 1;
    Panel p1 = new Panel();
    p1.Controls.Add(l1);
    form1.Controls.Add(p2);
    form1.Controls.Add(g);
    form1.Controls.Add(l1);
}

private GridView g = new GridView();
private DataSet d = new DataSet();
private Label l1 = new Label();

private void DoRussian()
{
    DataRow dr = d.Tables[0].Rows[d.Tables[0].Rows.Count - 1];
    int d1 = (int)dr[0];
    int d2 = (int)dr[1];
    if (d1 > 1)
    {
        int d3 = d1 / 2;
        int d4 = d2 * 2;
        DataRow dn = d.Tables[0].NewRow();
        dn[0] = d3;
        dn[1] = d4;
        d.Tables[0].Rows.Add(dn);
        d.Tables[0].AcceptChanges();
        DoRussian();
    }
}

}

2009-07-24 Reply Admin

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);
    }

2009-07-24 Reply Admin

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.

2009-07-24 Reply Admin

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!"

2009-07-24 Reply Admin

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!"

2009-07-24 Reply Admin

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!"

2009-07-24 Reply Admin

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

curtmack · 2009-07-24 Reply Admin

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";

2009-07-24 Reply Admin

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

2009-07-24 Reply Admin

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]

2009-07-24 Reply Admin

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<loop;i++)method.apply(this,args);
var end=new Date();
return end-start;
}
new function main(){
var params=[990,990];
var loopCount=20000;
var methods=[
straight,
grif,
firg
]
var results=[];
for(var i=0;i<methods.length;i++){
var time=timeMethod(methods[i],params,loopCount);
var result=methods[i].apply(this,params);
results.push(methods[i].toString().match(/function ([^(]*)/)[1]+" took: "+time+"ms to get "+result);
}
alert(results.join('\n'));
}

for extra credit, here's the link to run the above in your browser:

<a rel="nofollow" href="javascript: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;}function straight(x,y){return xy;}function timeMethod(method,args,loop){var start=new Date();for(var i=0;i<loop;i++)method.apply(this,args);return new Date()-start;}var params=[990,990];var methods=[straight,grif,firg];var results=[];for(var i=0;i<methods.length;i++){var time=timeMethod(methods[i],params,20000);results.push(methods[i].toString().match(/function ([^(])/)[1]+" took: "+time+"ms to get "+methods[i].apply(this,params));}results.push('with params x:'+params.join('; y:')+';');alert(results.join('\n'))" target="_blank" title="javascript: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;}function straight(x,y){return xy;}function timeMethod(method,args,loop){var start=new Date();for(var i=0;i<loop;i++)method.apply(this,args);return new Date()-start;}var params=[990,990];var methods=[straight,grif,firg];var results=[];for(var i=0;i<methods.length;i++){var time=timeMethod(methods[i],params,20000);results.push(methods[i].toString().match(/function ([^(])/)[1]+" took: "+time+"ms to get "+methods[i].apply(this,params));}results.push('with params x:'+params.join('; y:')+';');alert(results.join('\n'))">Test Grif and Firg

Cheers, and thanks for the game!

curtmack · 2009-07-24 Reply Admin

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

2009-07-24 Reply Admin

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)

2009-07-24 Reply Admin

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.

2009-07-24 Reply Admin

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).

2009-07-24 Reply Admin

This is exercise 1.18 in Structure and Interpretation of Computer Programs

ikegami · 2009-07-24 Reply Admin

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

2009-07-24 Reply Admin

Features:

excessive use of goto
no bitwise operations
no mul/div/mod operations

#include <stdio.h>

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));
}

mol1111 · 2009-07-24 Reply Admin

Updated version of index. Added entries from yesterday, fixed jnz's entry, resolved most entries without specified language, removed duplicates.

ABAP dv 277800 Someone 277998 278677

APL Captain Obvious 277817 Steve the Cynic 278029 278054

Assembler Dascandy x86, ARM 277793 Bosshog 6502 277804 278103 Stalker x64 277911 kastein IA64 277930 Bob Montgomery 6502 278147 Lunkwill m68k 278154 flax ARM 278263 Kevin Kofler m68k 278381 Gumpy Guss PDP-8 278418 bd_ Rabbit 2000 278438 Chris Walton x86 278499 C x86 278562 Anonymous ARM 278710 Moe 6502 279053 curtmack 6502 279343

BASIC Alex Papadimoulis VBScript 277748 Kees QB/VB ? 277803 Takis VB.Net 277814 278799 RayS VBA 277842 278407 djjeavons VB.Net 277887 Slinky VB? 278001 antelopelovefan VBA 278068 JoLoCo Sinclair 278126 Yorick Sinclair 278372 bluebearr AutoIt 278460 James VBA 278489 Don Knisley VBA 278534 k1 278548 278550 some VBA coder VBA 278862 Nix Nada VBA 279306

bc/dc Nick Pope 277951 278207

brainfuck Qwertyuiopas 278037 Eyrieowl 278241 Philipp 278837 Boombuler 279204

Brilliant Paula 277801

C/C++ Tim 277783 277784 Larry H. 277798 Stefan 277813 Zombywuf templates 277815 Matthew Verleger 277827 darkwraith 277832 KimmoS 277850 KnoNoth 277851 whileloopsareugly 277873 TerraNova 277876 YES WE CAN! 277912 little3lue templates 277914 GWO 277924 277962 277964 277965 avl 277929 ponky 277952 278066 hh10k 277969 buzkie 277984 shub 277985 278055 _flt 278003 Harleqin 278009 Zor 278046 278053 278059 Kman templates 278062 278880 Alex Guzman 278084 Fooba 278100 serg 278113 hornet 278173 278191 Bored 278175 xtremezone 278176 278190 278205 David Young 278185 Haggis 278189 Ronuk Raval 278209 Humanoid Life-form 278238 Alan Woodland templates 278240 Михаил 278267 OmnipotentEntity 278270 MG 278284 Resistance Assembler 278321 Rob Hulswit templates 278329 278331 mxsscott 278342 Rob H 278352 J.I. 278356 Sam 278391 spiderlama 278416 0ffh 278451 jnz 278473 Chris Walton 278499 demo templates 278528 khahem 278731 Mr. Black 278769 n1L templates 278844 markwhi 278906 278908 Lightnix 278994 TP 279023

C# Jay 277786 Dopefish 277788 Brettm 277812 ruckc 277828 Dan 277834 277856 Damien 277843 Felix Ungman 277867 GM 277894 cwink 277899 277905 Fabio Lima 277922 277957 Jonathan 277967 Osno 277972 277997 278021 groknroll 277980 buzkie 277984 campkev 277991 277994 278078 278081 Sean Handley 277995 Oliver Klozoff 278000 WraithShade 278057 Floyd LINQ 278082 Alex Guzman 278084 chriswatson LINQ 278106 Codism LINQ 278139 Jared Youtsey 278149 David C. 278161 278226 jeff.woodhull LINQ 278201 It'sMe 278203 Shiftyness 278236 Humanoid Life-form 278238 aef123 278245 278247 stannius LINQ 278261 blueberry 278286 VirtualBlackFox LINQ 278292 nine 278293 TNProgrammer 278302 Josue Chi 278303 dontera 278324 The Answer + 2 278328 hornet threads 278340 Rob H 278352 Lernin ur codez 278376 PatrickBeebe 278393 278974 Veryth LINQ 278433 brian 278450 Thomas Eyde 278456 Joel 278461 joeyadams 278471 JXO 278474 astander 278544 col obvious 278598 Alex 278628 czetts 278846 HCGL 278911 Jeremy Burns 278922 Paul N 278983 Tachyon ASP.Net 279255 Jason 279280

D Rief 278006 Quxxy 278069

Erlang Mike McNally 278434 278440 MichaelWH 278877 John Stracke 279008

F# darklajid 277890 277941 278137 Patrick Simpson 278127 ajp 278357 279029 cmugford 278486

FORTRAN rst 277978 java.lang.Chris; 278266

Groovy Matt 277949

Haskell freako 277838 Dave Ingram 277839 Sebastian Paaske Tørholm 277870 HypocriteWorld 277878 Maxim 277889 Noah Easterly 278130 semanticprecision 278170 Andrew Nurse 278198 Jonas Kramer 278220 ikorb 278299 valderman 278405 278406 Twey 278439 Joost 278567 jefu 278838 dub 278874 iggy 278935 vog 279045 MichaelWH 279047 dysfunctor 279081 Cale Gibbard 279334

Java Cookie 277785 Jay 277786 Mat Rantell 277802 ruckc 277828 Will 277831 Drew 277844 Arjan 277879 Philipp 277903 277919 Kook 277963 277968 buzkie 277984 Alex Guzman 278084 imhe 278105 278138 Jannik Jochem 278115 Thuktun 278124 idle 278128 klagdon 278131 278242 amischiefr 278152 Greg R 278212 278231 Davi Cavalcanti 278228 DeepThought 278230 bb 278235 cincinnatvs 278237 Humanoid Life-form 278238 aef123 278245 278247 Josue Chi 278303 Fred Dagg 278408 subanark 278537 astander 278544 col obvious 278598 Alex 278628 Rorick 278749 Queex 278761 Coyne 278892

Javascript Z 277796 Zishan 277882 Jason Knight 277898 Mestafais 278005 Markus Persson 278039 jjs105 278136 jonnyq 278208 Phroggy 278221 astonerbum 278248 278264 278343 Scott 278294 Beat by the system 278319 Rob Hulswit 278329 Jeb Walter Strate 278345 Crindigo 278419 Chris 278484 cofiem 279233 Ed 279287 JS ROX! 279340

LISP newlisp.org newLISP 277861 278283 MP 2778711 leppie Scheme 277881 dee Scheme 277900 Bob Scheme 277907 278206 Éibhear Emacs 277910 Dmitri Savichev Scheme 277992 277999 lyml Scheme 277996 Harleqin Common Lisp 278009 Alex Muscar Common Lisp 278090 278096 278160 278514 278516 Trey Jackson Emacs 278194 samanddeanus Scheme 278271 278998 asdfghj Scheme 278311 guille_ 278317 Ted Walther, newLISP fan newLISP 278344 278986 unit3 Common Lisp 278417 noSignal Scheme 278469 iamtim2 newLISP 278491 jvmbsd7 Scheme 278493 Chris Judge 278868

LOLCODE JaguarOne 277920 PopeHappyCat 278099 279245

Lua Stefan 277854 Will 278010 Tiogshi 278368 Methuselah 278675 Kenneth Pullen 279099

Mathematica J 278467 Joel Klein 279356

MSIL Osno 278153 278197 278729 278786 278801

MUMPS MUMPS 278211 Trurl 278246 278255

Other hydrus Clojure 277792 db2 HP 48 277857 Dave Ingram vimscript 277862 pjt33 SML 277864 SR ColdFusion 277896 Will MUSH 277942 Samuel A. Falvo II Forth 277976 Sal Postscript 278093 Cindi Knox mIRC 278174 darkscout Matlab 278298 Roger RPGLE 278337 Tom Medley - www.tommedley.com ML 278350 ikegami circuit diagram 278370 dee COBOL 278403 yowzer ocaml 278428 StarLite Progress V9 278583 Ralf Smalltalk 278794 Rorick Rebol 278810 278873 Whatever Befunge-93 278988 Rusty Nail Verilog 279040 Greg awk 279087 Marlon False 279219 279220 279225 Corpsegrinder AppleScript 279236 279237

Pascal Azeroth 277837 malach Delphi 277860 baka0815 277868 277877 278020 278028 278065 DougB Delphi 278179 Trevor Dubinsky Delphi 278229 mol1111 Turbo Vision 278374

Perl Me 277807 277845 epv 277849 Steven de B 277884 WarheadsSE 277944 278061 Anonymous 277977 tirerim 278119 John Evans 278141 Jim Halfpenny 278143 Igor V. 278199 Darren 278223 Warr regex 278260 278420 qoo3h 278353 Andrew Rodland 278358 H2 278388 Florent 278401 278404 Toby Gray 278538 278540 bugmonkey 278658 rjp 278714 Maurits 279046 Yorick 279222 asd 279246 curtmack 279331

PHP The Wolf 277787 277799 Erin 277797 Clark S 277858 277872 Ryan 277863 Daniel 277904 277909 FatherStorm 277932 aBase 278036 278214 John Evans 278141 HonoredMule 278158 278168 278184 IcePanther 278195 Tim 278196 Paul 278265 LeCoyote 278396 mjomble 278413 mneimeyer 278524 LatecomerX 278617 278673 bugmonkey 278658 Evo 278886 278934 AngeloR. 278960 symcbean 279208

Prolog Anonymous Coward 277938 Mike5 278204 A.T. 278641 278646 279196 Corpsegrinder 279051

Python ath 277789 277806 278244 phihag 277811 277818 277869 Fenris 277823 Jeff Kemp 277852 277940 Tempura 277875 Stalin 277880 Jim 277901 Eutactic 277915 RECURSIVEMAN 277916 rob tracey 277917 krat 277918 drBeat 277925 ross 277931 halber_mensch 277936 277943 277955 277979 278129 Real russian peasant :) 277974 Remy 278004 Billy 278007 Josh Bohde 278017 278080 278092 278104 278166 278854 Wulf0r 278024 Jürgen 278086 koblas 278101 Rob W. 278111 Chad M 278132 Jörg 278163 martinp 278172 JJM 278193 Ronuk Raval 278209 lostlogic 278222 SoaperGEM 278305 ZzzZZZz 278318 Lee Crabtree 278355 sdeek 278359 opussf 278364 KukkerMan 278366 Edinburgh Mike 278375 mwchase 278395 Adrian 278402 Jukka 278412 tdh 278444 Mr.'; Drop Database -- 278459 agrif 278497 Python 278688 Lom 278732 the real wtf fool 278842 workmad3 278975 inky 278996 Scott 279009 kramthegram 279290 279292 279297 raony 279352

Ruby arnemart 277825 277855 Mike Dotterer 277829 exo 277926 Nicholas Laux 277958 277971 Xthlc 277983 278026 derula 278050 Amadan 278071 Northpole 278072 jweir77 278079 Jürgen 278086 Dave Havlicek 278122 Jeremy Weathers 278216 Chewbie 278224 Jimmy Selgen 278367 Redredredredredred 278380 Pony Princess 278967

Scala Alex Ciarlillo 277937 Ian McLaird 278023 Matt 278249 Unlabeled Meat 278332 juancn 278962 Landei 279042 Moritz 279082

Shell mat BASH 277791 bluebearr Batch 278012 278243 Ken B Batch 278032 moltonel BASH 278262 278272 278282 Julian Calaby BASH 278485 The_Assimilator PowerShell 279028 andyesslinger Batch 279049

Spreadsheet acsi 278150 treyb Excel 278300 Joe Excel 279333

SQL SQLDork 277795 KnowOracle Oracle 277816 277822 277824 Chris Hunt Oracle 277836 csulli13 277888 MeesterTurner T-SQL 277959 wombat T-SQL 278186 shane blake T-SQL 278210 Dave Havlicek PL/pgSQL 278322 Bodestone 278341 DFHawthorne Oracle 278409 Paul N T-SQL 278425 278427 Hidayat Oracle 278526 SlyEcho 278535 Boneist Oracle 278555 EJCorcoran T-SQL 278795 dee MySQL 279007 DBA_In_OKC T-SQL 279145

Tcl/Tk Albrecht from Germany 278142 278145

Unspecified SimonY 278120 Michael Clark (mjac.co.uk) 278360 Eric 278371 Wheaties 278426

XSLT Dave van der Brugge 278133 wombat 278808

Addendum (2009-07-24 20:53): BTW If anybody (Alex?) interested, here are sources for the index generator (datafile + python script).

2009-07-25 Reply Admin

;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)))))

2009-07-25 Reply Admin

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 <iostream>

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";
}

2009-07-25 Reply Admin

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

Stalker · 2009-07-25 Reply Admin

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;

2009-07-25 Reply Admin

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. :)

2009-07-25 Reply Admin

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.

:)

2009-07-25 Reply Admin

fun peasantAdder(n,m) = let fun adder(1,m,acc) = m+acc | adder(n,m,acc) = adder(div(n,2),2*m,mod(n,2)*n+acc) in adder(n,m) end

2009-07-25 Reply Admin

No hardware implementations yet?

There's a schematic version and a verilog version way back in the flood of posts :)

mol1111 · 2009-07-25 Reply Admin

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

2009-07-25 Reply Admin

A bit late to this party, but here's my take:

#include <assert.h>

#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;
}

mol1111 · 2009-07-25 Reply Admin

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.

Stalker · 2009-07-25 Reply Admin

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;

2009-07-25 Reply Admin

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)

2009-07-26 Reply Admin

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

2009-07-26 Reply Admin

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

2009-07-26 Reply Admin

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; }

2009-07-26 Reply Admin

@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%

2009-07-26 Reply Admin

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)))

2009-07-26 Reply Admin

This is so nice :).

2009-07-26 Reply Admin

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))))

2009-07-26 Reply Admin

ehrm, forgot.

квас<<=1;

after the пиво>>=1;.

curtmack · 2009-07-26 Reply Admin

I had to cheat a little bit here. I don't know of any way to make this algorithm work in Befunge without very advanced trickery. So, it doesn't actually print the result of the multiplication - it just prints out the values that would be added together if Befunge could actually handle such a thing.

&&v
v <   \.:\<
>2/\2*\:2%|
^        <:
@        ^_

2009-07-26 Reply Admin

Here's mine in perl:

sub k{($a,$b)=@_,$a%2&&($_+=$b),$a&&k($a>>1,$b*2)}

(50 chars)

And the one liner to use that:

$ perl -E'sub k{($a,$b)=@_,$a%2&&($_+=$b),$a&&k($a>>1,$b*2)}k(@ARGV),say' 18 23
414
$ perl -E'sub k{($a,$b)=@_,$a%2&&($_+=$b),$a&&k($a>>1,$b*2)}k(@ARGV),say' 7 7
49

(71 chars + args; also a true one-liner - no semicolons :)) That's making a function, as said in the article. Without using a subroutine, the algorithm by itself:

$a%2&&($_+=$b),$b*=2,$a>>=1while $a

(35 chars! though $a and $b have to be initialised, if

($a,$b)=@ARGV;

is used it becomes 49 chars) And the one liners for that (slightly cheaty because semicolons):

$ perl -E'($a,$b)=@ARGV;$a%2&&($_+=$b),$b*=2,$a>>=1while $a;say' 7 3
21
$ perl -E'($a,$b)=@ARGV;$a%2&&($_+=$b),$b*=2,$a>>=1while $a;say' 135 975
131625

This is 62 chars + args.

Also, the above Befunge program is awesome and I fully endorse it, even if it doesn't fully work ;).

2009-07-26 Reply Admin

I enjoy these tasks, they give me something to do whilst I'm feeling a bit of a blackout on the "programming ideas" but still want to write some code.

My solution isn't as elegant or "efficient" as everyone elses seems to be but it was fun none the less.

public static int doPeasantMaths(int left, int right)
{
	int leftColumn[] = new int[20];
	int rightColumn[] = new int[20];
		
	int product = 0;
	int i = 0;
		
	leftColumn[i] = left;
	rightColumn[i] = right;
		
	if( (leftColumn[i] % 2) != 0 )
	{
		product = product + rightColumn[i];
	}
		
	while(leftColumn[i] != 1)
	{
		if(leftColumn[i] != 1)
		{
			i++;
		}
			
		leftColumn[i] = leftColumn[i-1] / 2;
		rightColumn[i] = rightColumn[i-1] * 2;
			
		if( (leftColumn[i] % 2) != 0 )
		{
			product = product + rightColumn[i];
		}
			
        }
		
	return product;
}

Obviously this code would fail if

a) The number of iterations exceeds 20 steps (as defined by the column sizes) b) The number in the left column is entered as 0

but it works otherwise : '}

2009-07-26 Reply Admin

Just refined my previous code, it was terrible in retrospect, this is a cleaner method!

public static int doPeasantMaths(int left, int right)
{
	int product = 0;
		
	if( (left % 2) != 0 )
	{
		product = product + right;
	}
		
	while(left != 1)
	{
		left = left / 2;
		right = right * 2;
			
		if( (left % 2) != 0 )
		{
			product = product + right;
		}	
	}
		
	return product;
}

Russian Peasant Multiplication

Leave a comment on “Russian Peasant Multiplication”