classic spaghetti code

StarLite · 2009-07-23 Reply Admin

My take using Progress V9 (will probably work in most older versions as well) Code:

function multiply returns integer (input ip_int1 as integer, input ip_int2 as integer):
define variable v_result as integer no-undo.

if ip_int1 = 1 then
return ip_int2.

if ip_int1 mod 2 <> 0 then
v_result = v_result + ip_int2.

v_result = v_result + multiply(integer(truncate(ip_int1 / 2, 0)), (ip_int2 * 2)).
return v_result.
end.

message "Russian Peasant Notation: " multiply(18, 23) view-as alert-box info buttons ok.

2009-07-23 Reply Admin

static int m(int x,int y){return x==1?y:x%2==0?m(x/=2,y*=2):y+m(x/=2,y*=2);}

2009-07-23 Reply Admin

Not sure if anyone posted this solution yet. Here's mine:

private int Multiply(int x, int y) { return x == 1 ? y : Multiply(x / 2, y * 2) + x % 2 * y; }

2009-07-23 Reply Admin

Mike5:

Anonymous Coward:
Prolog...
"optimized" with bit-shifting ...

To get the real prolog feeling:

%% russian(?A,?B,?P).
%% multiplies A and B the russian way, 
%% all parameters are optional
russian(A,B,P) :- nonvar(A), var(B), !, russian(B,A,P).
russian(A,B,P) :- var(A), (nonvar(B),!;length(_,P),between(0,P,B)), 
                  row(A,B,P,0,P).
russian(A,B,P) :- nonvar(A), row(A,B,P,0,P), !.

row(_,_,P,F,_) :- nonvar(P), P < 1<<(F-1), !, fail.
row(0,_,_,_,0).
row(A,B,P,F,R) :-
    row(Ax,B<<1,P,F+1,Rx),
    double(Ax,A,Odd),
    R is Rx+B*Odd.
    
double(0,1,1) :- !.
double(X,X2,Odd) :- (Odd=0;Odd=1), X2 is X*2+Odd.

may need some optimization though...

2009-07-23 Reply Admin

Mike5:

Anonymous Coward:
Prolog...
"optimized" with bit-shifting ...

To get the real prolog feeling:

%% russian(?A,?B,?P).
%% multiplies A and B the russian way, 
%% all parameters are optional
russian(A,B,P) :- nonvar(A), var(B), !, russian(B,A,P).
russian(A,B,P) :- var(A), (nonvar(B),!;length(_,P),between(0,P,B)), 
                  row(A,B,P,0,P).
russian(A,B,P) :- nonvar(A), row(A,B,P,0,P), !.

row(_,_,P,F,_) :- nonvar(P), P < 1<<(F-1), !, fail.
row(0,_,_,_,0).
row(A,B,P,F,R) :-
    row(Ax,B<<1,P,F+1,Rx),
    double(Ax,A,Odd),
    R is Rx+B*Odd.
    
double(0,1,1) :- !.
double(X,X2,Odd) :- (Odd=0;Odd=1), X2 is X*2+Odd.

may need some optimization though...

bugmonkey · 2009-07-23 Reply Admin

PHP and Perl, and gives the same output for both:

#
#<?php echo "\x8";ob_start();
$rm='return int($a/2)==1?$b*2:(int($a/2)%2==1?$b*2+rm(int($a/2),$b*2):rm(int($a/2),$b*2));';
#?><?php function int($a){return floor($a);}$a=$argv[1];$b=$argv[2];eval('function rm($a, $b){'.$rm.'}');?>
$a=$ARGV[0];$b=$ARGV[1];eval("sub rm{\$a=shift;\$b=shift;$rm}");#<?php ob_end_clean();
print rm($a,$b);</pre>

2009-07-23 Reply Admin

Came up with a more condensed PHP function after another 45 minutes or so:

function multiply($x, $y) { return $x % 2 * $y + ($x > 1 ? multiply(floor($x / 2), $y * 2) : 0); }

LatecomerX:
I've been a TDWTF reader for the past few months, and I'm dedicating my first comment to this interesting question here:
In PHP:
<? function multiply($x, $y, $o = 0) { return $x > 1 ? multiply(floor($x / 2), $y * 2, $o + $x % 2 * $y) : $o + $y; } echo multiply(18, 23); ?>
Also available at: http://phpieceofcake.com/?83344437

Methuselah · 2009-07-23 Reply Admin

Here's some Lua code:

function russian(a, b)
	if a==1 then
		return b
	else
		if a%2==1 then
			return b+russian(math.floor(a/2), b*2)
		else
			return russian(math.floor(a/2), b*2)
		end
	end
end

Code only: 189 bytes Code with BBCode coloring: 1190 bytes

2009-07-23 Reply Admin

Someone:

An ABAP solution that compiles:

REPORT MULTIP.
DATA: product TYPE i,
left_num TYPE f VALUE 18,
right_num TYPE f VALUE 23,
half_left TYPE f,
half_left_floor TYPE f.
WHILE left_num > 0.
"check for even number and add to product (there must be a better way...)
half_left = left_num / 2.
half_left_floor = FLOOR( left_num / 2 ).
IF half_left <> half_left_floor.
product = product + right_num.
ENDIF.
"move to next set
left_num = FLOOR( left_num / 2 ).
right_num = right_num * 2.
ENDWHILE.
WRITE product.

Yes there is a better way, the MOD operator. Also, when creating a whole report for it, why not include a nice, verbose, selection screen?

SELECTION-SCREEN BEGIN OF BLOCK 1 WITH FRAME TITLE 'Input'.
PARAMETER p_num1 TYPE I DEFAULT 18 OBLIGATORY.
PARAMETER p_num2 TYPE I DEFAULT 23 OBLIGATORY.
SELECTION-SCREEN END OF BLOCK 1.

2009-07-23 Reply Admin

#! -- Encoding: Latin-1 --

import threading import Queue

classic spaghetti code

def rupmul1(a,aa):
aaa = lambda:(a % 2) and aa
aaaa = aaa() while a > 1: a, aa = a/2, aa*2 aaaa += aaa() return aaaa

functional programming

rupmul2 = lambda a,b: sum(map( lambda b:a&b[0] and b[1],zip(map( lambda a:pow(2,a),range(31)),map( lambda a:b*pow(2,a),range(31)))))

multicore power using threads + functional programming = TOTAL WIN!

def rupmul3(a,b,=Queue.Queue()):
return sum(map(lambda _:.get(),map(lambda :[threading.Thread(target=lambda : __.put((a&1<<) and b<<),args=(,)).start(),][-1],range(32))))

def selftest():
import random

for k in range(60):
    a = random.randrange(1,10000)
    b = random.randrange(1,10000)
    
    n = a*b
    assert rupmul1(a,b) == rupmul2(a,b) == rupmul3(a,b) == a*b

if name == "main": selftest()

2009-07-23 Reply Admin

ParkinT:
Wow! I had not time to submit a solution. Everyone was too busy Russian to provide an answer!

OH DEAR!!! LOL!

2009-07-23 Reply Admin

That ARM code is both wrong and far too long. This is perhaps slightly less wrong:

    mov    r2,#0
loop:
    movs   r1,r1,lsr #1
    addcs  r2,r2,r0
    mov    r0,r0,lsl #1
    bne    loop

2009-07-23 Reply Admin

Me:
Bah to all your bloaty solutions. Perlmongers do it in one line :P
sub m(){my($a,$b)=@_;my $t;while($a){$t+=$b if ($a&1);$a>>=1;$b<<=1;}return $t;}

Apologies if this has been pointed out already but you can shorten that slightly.

sub m{my($a,$b)=@_;my $t;while($a){$t+=$b*($a&1);$a>>=1;$b*=2}$t}

2009-07-23 Reply Admin

Tail recursive in IL (based on 278641, not sure if C# can compile a tail recursivity, I'll have to check later). The first param is the acumulator and should be initialized to 0 (or wrapped in another method):

.method private hidebysig static int64 Russian(int64 a, int64 f, int64 s) cil managed { .maxstack 4 ldarg.0 dup ldarg.1 brfalse.s done ldarg.1 ldc.i4.1 and ldarg.2 mul add ldarg.1 ldc.i4.1 shr ldarg.2 ldc.i4.1 shl tail. call int64 RussianMult.Program::Russian(int64, int64, int64) done: ret }

2009-07-23 Reply Admin

BTW, I think I've never seen a post in this site with 12 pages of comments.

khahem · 2009-07-23 Reply Admin

C++ with a 'simple' iterator.

#include <numeric>
struct gen {
    int a, b;
    gen(int a=0, int b=0) : a(a), b(b) { }
    gen operator*() { return *this; }
    void operator++() { a /= 2; b *= 2; }
    bool operator!=(gen b) { return a != b.a; }
    gen operator+(gen r) {
        if (r.a % 2)
            return gen(0, b + r.b);
        return gen(0, b);
    }
};

int mul(int a, int b) {
    return std::accumulate(gen(a, b), gen(), gen()).b;
}

2009-07-23 Reply Admin

Python, nominate for shortest one :) 49 characters. And, with python, numbers multiply peasants.

m=lambda a,b:sum(b<<i for i in range(a)if a&1<<i)

2009-07-23 Reply Admin

Java:

public static long multiply(int a, int b) {
    if (a < 0) {
        a = -a;
        b = -b;
    }
    int result = 0;
    while (a > 0) {
        int tz = Integer.numberOfTrailingZeros(a);
        result += b << tz;
        a = a >> ++tz << tz;
    }
    return result;
}

2009-07-23 Reply Admin

This nearly works; I'll leave the rest to the in-house coders.

    public static int multiply(int x, int y) {
        StringBuffer sb = new StringBuffer();
        sb.append("" + x);
        sb.append(" x "); // prettify output
        sb.append(y + "");

        while (doIt(sb));

        System.err.println(sb.toString());

        String str = sb.toString();
        StringTokenizer st = new StringTokenizer(sb.toString(), "\n ");
        int o = 0;
        while (st.hasMoreTokens()) {
            if (Integer.parseInt(st.nextToken()) % 2 == 0) {
                //do nothing
            } else {
                o += Integer.parseInt(st.nextToken());
            }
        }

        return o;
    }

    public static boolean doIt(StringBuffer sb) {
        int line = sb.lastIndexOf("\n");
        line++; //need this for some reason!!!!!1!

        //if(line<0){
        //      line++;
        //}

        int split = sb.indexOf(" ", line);
        String x = sb.substring(line, split);
        String y = sb.substring(split);

        sb.append("\n");
        sb.append(Integer.parseInt(x) / 2);
        sb.append(" ");
        sb.append(Integer.parseInt(y.trim()) * 2);

        if (x.equalsIgnoreCase("1")) {
            return false;
        }

        return true;
    }
    
//    public static int multiply(int x, int y) {
//        int out = 0;
//        while (x != 1) {
//            if (x % 2 != 0) {
//                out += y;
//            }
//            x = x >> 1;
//            y = y << 1;
//        }
//        return out + y;
//    }

2009-07-23 Reply Admin

Wow, the number of unreadable and unmaintainable examples outweight the readable and maintainable ones by about 50:1! That's the real WTF...

2009-07-23 Reply Admin

my crappy C version that doesn't work for negative numbers ;) ----------------------- <snip> --------------------------

#include <stdio.h>

main( argc, argv)
int argc;
char *argv[3];
{
	int n1 = 0;
	int n2 = 0;
	int n3 = 0;
	
	n1 = atoi(argv[1]);
	n2 = atoi(argv[2]);
	/* Implement Russian Peasant Multiplication algorithm */
	if ( argc != 3 )
	{
	   printf("USAGE: rpm n n\nrpm multiplies two numbers via the Russian peasant method\n");
	   return(1);
	}
	
	/* if either parameter is zero, the answer is zero */
	if ( n1 == 0 || n2 == 0 )
	{
	   printf("Result of %d * %d via Russian peasant method is: 0.\n", n1, n2);
	   return(0);		
	}
	
	if ( n1 == 1 || n2 == 1 )
	{
	   printf("Result of %d * %d via Russian peasant method is: %d.\n", n1, n2, n1*n2);
	   return(0);		
	}
	
	if ( (n1 % 2) != 0 )
	{
	      n3 = n2;
	}
	      
	while ( n1 >= 1 )
	{
		n1 = n1 / 2;
		n2 = n2 * 2;
		if ( (n1 % 2) != 0 )
		{
			  n3 = n3 + n2;  
		} 
  }				
	
	printf("Result of %d * %d via Russian peasant method is: %d.\n", atoi(argv[1]), atoi(argv[2]), n3);
	
	return(0);
}

----------------------- <snip> ---------------------

2009-07-23 Reply Admin

The C# compiler does tail call optimisation only on x64 afaik.

2009-07-23 Reply Admin

Smalltalk

Note that this overwrites the System's definition of * and everything still works.

* aNumber

	self isZero ifTrue: [^0].
	self < 0
		ifTrue: [^(self negated * aNumber) negated]
		ifFalse:  [^ ((self bitShift: -1) * (aNumber + aNumber)) + ((self bitAnd: 1) = 1 ifTrue: [aNumber] ifFalse: [0])]

EJCorcoran · 2009-07-23 Reply Admin

Another SQL (T-SQL) Answer: DECLARE @X INT, @Y INT, @Z INT SELECT @X=18,@Y=23,@Z=0 WHILE @X!=1 BEGIN IF (@X%2)!=0 SET @Z=@Z+@Y SET @X=@X/2 SET @Y=@Y*2 END SET @Z=@Z+@Y SELECT @Z

2009-07-23 Reply Admin

577 comments later and still no recursive VB.Net solution, so here's my second try; it handles negatives as well and doesn't use multiplication:

Function Russiply2(ByVal a As Long, ByVal b As Long) As Long

  Return If(a < 0, Russiply2(-a, -b), If(a > 1, If((a And 1) = 1, b, 0) + Russiply2(a >> 1, b << 1), If(a = 1, b, 0)))

End Function

2009-07-23 Reply Admin

Just checked on an x64. At least by default, it doesn't do tail recursion. Also, when compiled in Release the output is really really close to my solution. The only real difference is that it branches on non-equal instead of false.

WarheadsSE · 2009-07-23 Reply Admin

joeyadams:
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?

I believe the problem is that we've made this poor russian peasant thirsty, after warping his brain with such compressed algorithms in as many languages we could come up with. PDP-8, nice touch, but its still ASM! CP/M shell anyone???

WarheadsSE · 2009-07-23 Reply Admin

Lom:
Python, nominate for shortest one :) 49 characters. And, with python, numbers multiply peasants.
m=lambda a,b:sum(b<<i for i in range(a)if a&1<<i)

There is a 44 character python, and a 40 characther bc, although you still have several characters to go to catch perl :)

WarheadsSE · 2009-07-23 Reply Admin

rjp:
Me:
Bah to all your bloaty solutions. Perlmongers do it in one line :P
sub m(){my($a,$b)=@_;my $t;while($a){$t+=$b if ($a&1);$a>>=1;$b<<=1;}return $t;}

Apologies if this has been pointed out already but you can shorten that slightly.

sub m{my($a,$b)=@_;my $t;while($a){$t+=$b*($a&1);$a>>=1;$b*=2}$t}

It has, but then its perl.. TIMTOW! stub..! oww.

2009-07-23 Reply Admin

Only works with positive integers.

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

    <!-- get initial values out of xml -->
    <xsl:template match="/">
        <xsl:variable name="number1">
            <xsl:value-of select="*/number[1]"/>
        </xsl:variable>

        <xsl:variable name="number2">
            <xsl:value-of select="*/number[2]"/>
        </xsl:variable>

        <!--call the loop for the first time-->
        <xsl:call-template name="loop">
            <xsl:with-param name="a" select="$number1"/>
            <xsl:with-param name="b" select="$number2"/>
            <xsl:with-param name="r" select="0"/>
        </xsl:call-template>
    </xsl:template>

    <!-- the loop to recurse over-->
    <xsl:template name="loop">
        <xsl:param name="a"/>
        <xsl:param name="b"/>
        <xsl:param name="r"/>
        <xsl:choose>
            <xsl:when test="$a = 1">
                <!-- we have finished print the result -->
                <xsl:value-of select="$b + $r"/>
            </xsl:when>
            <xsl:otherwise>
                <!--call the template again. each time divide "a" by 2 multiple "b" by 2, and sum "b" to the remainder if "a" is odd -->
                <xsl:call-template name="loop">
                    <xsl:with-param name="a" select="round(($a div 2) - 0.5)"/>
                    <xsl:with-param name="b" select="$b * 2"/>
                    <xsl:with-param name="r" select="($a mod 2) * $b + $r"/>
                </xsl:call-template>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:template>

</xsl:stylesheet>

2009-07-23 Reply Admin

Another version, now in Rebol.

multru: func [a b /local res] [
	res: copy []
	append res [res: 0]
	append res compose [(either a < 0 [[-res]] [[res]])]
        res: back tail res
	until [
		insert res compose/deep [either odd? (a) [add res (b)] [res]]
		insert res to-set-word 'res
		set [a b] compose [(round/down divide a 2) (multiply b 2)]
		zero? a
	]
	do head res
]

It generates rebol code composed from additions and checks for oddity and then executes it. For 23 and 18 generated code looks like:

[res: 0 res: either odd? 1 [add res 288] [res] res: either odd? 2 [add res 144] [res] res: either odd? 5 [add res 72] [
res] res: either odd? 11 [add res 36] [res] res: either odd? 23 [add res 18] [res] res]

2009-07-23 Reply Admin

Ok, I couldn't resist. Here's an (amended!) brainfuck interpreter in Java, running the brainfuck code from Qwertyuiopas:

public class BrainfuckJavaRussianMultiplication {
  private static final String input = 
    ">>>>>,>>,[->+>+<<]<<[[-[>+<-]>[>+>>>+<<<<-[[<+>-]>[-]<]]<]>>[>>[-]" +
    "<<[-]]+>[->>>>>++>++<<<<<<]>>]>>>>[-]<<<<<<<[<<<<<]>>>>>[>>[->>>>>" +
    "+<<<<<]>>>]>>%";
	
  BrainfuckJavaRussionMultiplication(String code) {
    int ptr = 0;
    int [] cell = new int[10000];
		
    for (int i = 0; i < 10000; i++) {
      cell[i] = 0;			
    }
		
    char [] chars = code.toCharArray();
    for (int i = 0, n = chars.length; i < n; i++) {
      char c = chars[i];
      if (c == '>') {
        ptr++;
      } else if (c == '<') {
        ptr--;
      } else if (c == '+') {
        cell[ptr]++;
      } else if (c == '-') {
        cell[ptr]--;
      } else if (c == '.') {
        System.out.print((char) cell[ptr]);
      } else if (c == '%') {
        System.out.print((int) cell[ptr]);
      } else if (c == ',') {
        Scanner in = new Scanner(System.in);
        try {
          cell[ptr] = Integer.parseInt(in.nextLine());
        } catch (Exception e) {
	  cell[ptr] = 0;
        }
      } else if (c == '[') {
	if (cell[ptr] == 0) {
	  int counter = 0;
	  int position = i + 1;
	  while (chars[position] != ']' || counter != 0) {
	    if (chars[position] == '[') {
	      counter++;
	    }
	    if (chars[position] == ']') {
	      counter--;
	    }
	    position++;
	  }
	  i = position;
       }
     } else if (c == ']') {
       int counter = 0;
       int position = i - 1;
       while (chars[position] != '[' || counter != 0) {
         if (chars[position] == ']') {
	   counter++;
	 }
	 if (chars[position] == '[') {
	   counter--;
	 }
	 position--;
       }
       i = position - 1;				
     }
   }
  }
	
  public static void main(String [] args) {
    new BrainfuckJavaRussianMultiplication(input);
  }
}

As you can see, you may enter integers (instead of characters whose ASCII code is interpreted), also we are dealing with Brainfuck++ here, since it has the % command ;)

2009-07-23 Reply Admin

Haskell (with quickCheck to test it) :

import Test.QuickCheck

pm 0 y = 0 
pm 1 y = y 
pm x y 
  | x < 0     = - pm (-x) y 
  | even x    = next
  | otherwise = y + next 
 where next = pm (x `div` 2) (y*2) 

prop_PMOK x y = pm x y == x*y
   where types = (x::Int,y::Int) 

quickCheck prop_PMOK

the real wtf fool · 2009-07-23 Reply Admin

#!/usr/bin/python

from sys import argv

if len(argv) < 3:
	print "input values missing"
	print "usage: "
	print argv[0] + " value1 value2"
	exit()

a = int(argv[1])
b = int(argv[2])
acc = 0
sep = " x "

justWidth = 5

while (a > 0):
  if a & 0x1:
    acc = acc + b
    print "  ",
  else:
    print "--",

  print str(a).rjust(justWidth) + sep + str(b).rjust(justWidth)
  sep = "   "

  a = a >> 1
  b = b << 1

print "   " + "-" * ((justWidth*2)+len(sep))
print "  =" + str(acc).rjust((justWidth*2)+len(sep))

The output:

>pmath.py 18 23
--    18 x    23
       9      46
--     4      92
--     2     184
       1     368
   -------------
  =          414

The lines starting with -- should be considered crossed out

2009-07-23 Reply Admin

soulution as c++ template:

//////////////////////////////
template <int I, int J>
struct Pmul
{
  operator int()	
  {
    return (I%2)?J+Pmul():Pmul();
  }
};
//////////////////////////////
template <int J>
struct Pmul<1, J>
{
  operator int()	
  {
    return J;						
  }
};
//////////////////////////////

i.e.:
int res = Pmul<2311, 1234>();

czetts · 2009-07-23 Reply Admin

Well, I wanted to go back and make this more "clever", but this works just fine (C#):

public static int MultiplyLikeARussianPeasant(int x, int y)
{
    int sum = 0;
    do
    {
        sum += (x%2 == 1) ? y : 0;
        x /= 2;
        y *= 2;
    } while (x >= 1);
    return sum;
}

(I haven't checked the comments for this solution, that would have been cheating!)

2009-07-23 Reply Admin

WarheadsSE:
Lom:
Python, nominate for shortest one :) 49 characters. And, with python, numbers multiply peasants.
m=lambda a,b:sum(b<<i for i in range(a)if a&1<<i)

There is a 44 character python, and a 40 characther bc, although you still have several characters to go to catch perl :)

37 using * and /

m=lambda a,b:a and(a&1)*b+m(a/2,b+b)

41 without

m=lambda a,b:a and[0,b][a&1]+m(a>>1,b+b)

2009-07-23 Reply Admin

Function peasant(factor1, factor2) peasant = 0 If factor1 < 0 Then factor2 = -factor2 While factor1 <> 0 If (factor1 / 2) <> Round(factor1 / 2, 0) Then peasant = peasant + factor2 factor1 = factor1 / 2 - (factor1 Mod 2) / 2 factor2 = 2 * factor2 Wend End Function

2009-07-23 Reply Admin

Bob:
Someone straighten me out here but I think the peasant don't know math for crap.
May be I'm doing it wrong but when I Multiply 45 x 76, I get 3420
Peasants get:
45   x  76	
22	152	0
11	304	304
5	608	608
2	1216	0
1	2432	2432
	3344
Flip the numbers and you get the right answer 76 45 38 90 0 19 180 180 9 360 360 4 720 0 2 1440 0 1 2880 2880
	3420
Peasant math apparently only works if one of the number is even and in the first column.

This must be why they remain peasants.

When you start with the 45 in the left column, you forgot to include the 76 in your sum.

Oh, and by the way:

(define (pm x y)
  (define (pm2 acc x y)
    (cond
      [(= x 0) acc]
      [(= (remainder x 2) 0) (pm2 acc (floor (/ x 2)) (+ y y))]
      [else (pm2 (+ acc y) (floor (/ x 2)) (+ y y))]
    )
  )
  
  (pm2 0 x y)
)

2009-07-23 Reply Admin

In rebol with caching of generated code stuff.

multru: func [a b /local res cached] [	
	if not value? 'cache [
		set/any in system/words 'cache []		
	]	
	select-cache: func [a b /local cached] [select/only cache compose [(a) (b)]]	
	case [
		found? cached: any [select-cache a b select-cache b a] [return do cached]		 
		true [
			append/only cache compose [(a) (b)]			
			res: copy []
			append res [res: 0]	
			append res compose [(either a < 0 [[-res]] [[res]])]
			res: back tail res
			until [		
				insert res compose/deep [either odd? (a) [add res (b)] [res]]
				insert res to-set-word 'res
				set [a b] compose [(round/down divide a 2) (multiply b 2)]
				zero? a
			]			
			append/only cache head res	
		]
	]
	do last cache
]

2009-07-23 Reply Admin

I'm in the process of learning Haskell so here's my haskell solution. Feel free to give feedback so I can improve.

rus 0 _ = 0 rus a b | a < 0 = (-1) * (rus (abs a) b) | b < 0 = (-1) * (rus a (abs b)) | odd a = b + (rus (div a 2) (b2) ) | otherwise = (rus (div a 2) (b2) )

MichaelWH · 2009-07-23 Reply Admin

Erlang, as a module.

-module(peasant).
-export([peasant/2]).

peasant (1,Y) -> Y;
peasant (X,Y) when (X rem 2 == 1) ->
    Y + peasant ((X bsr 1),(Y bsl 1));
peasant (X,Y) ->
    peasant ((X bsr 1),(Y bsl 1)).

2009-07-23 Reply Admin

c++ templates

template <unsigned int a, unsigned int b> struct RM_ { static const unsigned int result = a & 0x1 ? b + RM_<a / 2, b * 2>::result : RM_<a / 2, b * 2>::result; }; template <unsigned int b> struct RM_<1, b> { static const unsigned int result = b; };

unsigned int c = RM_<18, 23>::result;

Evo · 2009-07-23 Reply Admin

The only real solution:

<?php
function ymhoxntb($n1, $n2)
{
  $written = "$n1 x $n2";

  // Create the next line, dividing the left number by two and
  // doubling the right.
  do {
    // Get the last line
    $lines = split("\n", $written);
    $line = $lines[count($lines)-1];
    preg_match("/([0-9]*)\s+[x]?\s*([0-9]*)/", $line, $matches);
    $a1 = intval($matches[1]);
    $a2 = intval($matches[2]);

    // Make the next line
    $a1 = floor($a1/2);
    $a2 *= 2;
    $written .= "\n$a1 $a2";
  }
  while($a1 > 1);
  echo $written."\n\n";

  // Cross out the even numbers on the left side
  $docrossout = TRUE;
  for($i = 0; $i < strlen($written); $i++) {
    if($written[$i] == "\n") {
      $docrossout = FALSE;
      if(intval(substr($written, $i)) % 2 == 0)
        $docrossout = TRUE;
      continue;
    }

    if($docrossout)
      $written[$i] = "-";
  }
  echo $written."\n\n";

  // Add the remaining right columns
  $lines = split("\n", $written);
  $result = "";
  foreach($lines AS $line) {
    if(!preg_match("/([0-9]*)\s+[x]?\s*([0-9]*)/", $line, $matches))
      continue;

    if($result == "")
      $result .= $matches[2];
    else
      $result .= " + ".$matches[2];
  }
  echo $result." = ";
  eval("echo ".$result.";");
  echo "\n";
}
ymhoxntb(18, 23);

Coyne · 2009-07-23 Reply Admin

This is in Java. It was tested and works for negatives.

public static int doRussianMultiply(int a, int b)
{
   if (a < 0) return -doRussianMultiply(-a,b); 
      
   int sum = 0;
   while (a > 1) {
      if ((a & 1) == 1) sum += b;
      a >>= 1;
      b += b;
   }
   if (a == 1) sum += b;
   
   return sum;
}

2009-07-23 Reply Admin

Late to the game, I guess. Replying without viewing comments, wonder if mine is original :)

http://pastebin.com/f50d7e6d5

2009-07-23 Reply Admin

I guess I should post the code, not just a link to it:

/**

Submission for TDWTF Programming Praxis 1: Russian Peasant Multiplication
July 23, 2009 */ #include <stdio.h> #include <stdlib.h>

void usage (void) { printf ("usage: rmult <int> <int>\n") ; exit (-1) ; }

int main (int argc, char **argv) { int a, b, total = 0 ;

if (argc != 3) usage () ;

a = atoi (argv[1]) ; b = atoi (argv[2]) ; if (a <= 0 || b <= 0) usage () ;

printf ("%i * %i = ", a, b) ;

while (1) { if (a % 2) total += b ;

if (a == 1)
  break ;

a /= 2 ;
b *= 2 ;

}

printf ("%i\n", total) ;

return 0 ; }

2009-07-23 Reply Admin

public static double RussianMultiply(int left, int right) { var columns = new Dictionary<int, int> {{left, right}}; var product=0; while (left > 1) columns.Add(left /= 2, right *= 2);

        foreach (var row in columns)
            product += row.Value * (row.Key % 2);

        return product;
    }

2009-07-23 Reply Admin

uint multiplyIntegers( uint a, uint b ) // C#
{
    uint up, down, res = 0;
        	
    if( a > b ) { up = a; down = b; }
    else { up = b; down = a; }
       	
    do
    {
        if( (down & 1) != 0 ) res += up;
        up <<= 1;
        down >>= 1;
    }
    while( down > 0 );

    return res;
}

Evo · 2009-07-23 Reply Admin

Oops... bugfix:

function ymhoxntb($n1, $n2)
{
  $written = "$n1 x $n2";

  // Create the next line, dividing the left number by two and
  // doubling the right.
  do {
    // Get the last line
    $lines = split("\n", $written);
    $line = $lines[count($lines)-1];
    preg_match("/([0-9]*)\s+[x]?\s*([0-9]*)/", $line, $matches);
    $a1 = intval($matches[1]);
    $a2 = intval($matches[2]);

    // Make the next line
    $a1 = floor($a1/2);
    $a2 *= 2;
    $written .= "\n$a1 $a2";
  }
  while($a1 > 1);
  echo $written."\n\n";

  // Cross out the even numbers on the left side
  $docrossout = FALSE;
  for($i = -1; $i < strlen($written); $i++) {
    if($i == -1 || $written[$i] == "\n") {
      $docrossout = FALSE;
      if(intval(substr($written, $i + 1)) % 2 == 0)
        $docrossout = TRUE;
      continue;
    }

    if($docrossout)
      $written[$i] = "-";
  }
  echo $written."\n\n";

  // Add the remaining right columns
  $lines = split("\n", $written);
  $result = "";
  foreach($lines AS $line) {
    if(!preg_match("/([0-9]*)\s+[x]?\s*([0-9]*)/", $line, $matches))
      continue;

    if($result == "")
      $result .= $matches[2];
    else
      $result .= " + ".$matches[2];
  }
  echo $result." = ";
  eval("echo ".$result.";");
  echo "\n";
}
ymhoxntb(18, 23);

Russian Peasant Multiplication

classic spaghetti code

functional programming

multicore power using threads + functional programming = TOTAL WIN!

Peasants get:
45 x 76 22 152 0 11 304 304 5 608 608 2 1216 0 1 2432 2432

Flip the numbers and you get the right answer 76 45 38 90 0 19 180 180 9 360 360 4 720 0 2 1440 0 1 2880 2880

Leave a comment on “Russian Peasant Multiplication”

Russian Peasant Multiplication

classic spaghetti code

functional programming

multicore power using threads + functional programming = TOTAL WIN!

Peasants get:45 x 76 22 152 0 11 304 304 5 608 608 2 1216 0 1 2432 2432

Flip the numbers and you get the right answer 76 45 38 90 0 19 180 180 9 360 360 4 720 0 2 1440 0 1 2880 2880

Leave a comment on “Russian Peasant Multiplication”

Peasants get:
45 x 76 22 152 0 11 304 304 5 608 608 2 1216 0 1 2432 2432