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]
« PrevPage 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 16Next »

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 05:54 • by Joost (unregistered)
And of course in Haskell:

multiply n m = sum $ map snd $ filter (odd . fst) $ russian n m
where russian 1 m = [(1,m)]
russian n m = (n,m) : russian (n `div` 2) (m * 2)

Progress V9 version of Russian Peasant Multiplication

2009-07-23 06:10 • by StarLite
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 06:15 • by col obvious (unregistered)
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);}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 06:28 • by LatecomerX (unregistered)
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 06:40 • by Alex (unregistered)
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;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 06:45 • by A.T. (unregistered)
278641 in reply to 278204
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...

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 06:51 • by A.T. (unregistered)
278646 in reply to 278204
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...

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 06:54 • by bugmonkey
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);

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 07:08 • by LatecomerX (unregistered)
278673 in reply to 278617
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 07:14 • by Methuselah
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 07:23 • by dv (unregistered)
278677 in reply to 277998
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 07:26 • by Python (unregistered)
#! -*- 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()

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 07:32 • by London Developer (unregistered)
278705 in reply to 277794
ParkinT:
Wow!
I had not time to submit a solution.
Everyone was too busy Russian to provide an answer!


OH DEAR!!! LOL!

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 07:40 • by Anonymous (unregistered)
278710 in reply to 277793
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


Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 07:41 • by rjp (unregistered)
278714 in reply to 277807
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}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 08:00 • by Osno (unregistered)
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
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 08:01 • by Osno (unregistered)
BTW, I think I've never seen a post in this site with 12 pages of comments.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 08:01 • by khahem
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;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 08:02 • by Lom (unregistered)
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)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 08:13 • by Rorick (unregistered)
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;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 08:16 • by Queex (unregistered)
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;
// }

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 08:17 • by ath (unregistered)
Wow, the number of unreadable and unmaintainable examples outweight the readable and maintainable ones by about 50:1!
That's the real WTF...

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 08:18 • by Mr. Black (unregistered)
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> ---------------------

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 08:29 • by Alex Muscar (unregistered)
278786 in reply to 278729
The C# compiler does tail call optimisation only on x64 afaik.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 09:08 • by Ralf (unregistered)
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])]


Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 09:13 • by EJCorcoran
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 09:17 • by Takis (unregistered)
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 09:18 • by Osno (unregistered)
278801 in reply to 278786
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 09:21 • by WarheadsSE
278805 in reply to 278513
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???

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 09:23 • by WarheadsSE
278806 in reply to 278732
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 :)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 09:24 • by WarheadsSE
278807 in reply to 278714
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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 09:25 • by wombat (unregistered)
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>

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 09:27 • by Rorick (unregistered)
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]

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 10:12 • by Philipp (unregistered)
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 ;)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 10:15 • by jefu (unregistered)
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 10:20 • by the real wtf fool

#!/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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 10:24 • by n1L (unregistered)
soulution as c++ template:
//////////////////////////////

template <int I, int J>
struct Pmul
{
operator int()
{
return (I%2)?J+Pmul<I/2,J*2>():Pmul<I/2,J*2>();
}
};
//////////////////////////////
template <int J>
struct Pmul<1, J>
{
operator int()
{
return J;
}
};
//////////////////////////////
i.e.:
int res = Pmul<2311, 1234>();

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 10:27 • by czetts
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!)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 10:43 • by Josh Bohde (unregistered)
278854 in reply to 278806
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)



Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 10:50 • by some VBA coder (unregistered)
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

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 10:55 • by Chris Judge (unregistered)
278868 in reply to 277866
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)
)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 11:01 • by Rorick (unregistered)
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
]

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 11:01 • by dub (unregistered)
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) (b*2) )
| otherwise = (rus (div a 2) (b*2) )

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 11:06 • by MichaelWH
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)).

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 11:09 • by Kman (unregistered)
278880 in reply to 278877
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;

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 11:21 • by Evo
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);

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 11:25 • by Coyne
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;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 11:48 • by markwhi (unregistered)
Late to the game, I guess. Replying without viewing comments, wonder if mine is original :)

http://pastebin.com/f50d7e6d5

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 11:51 • by markwhi (unregistered)
278908 in reply to 278906
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 ;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 11:54 • by HCGL (unregistered)
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;
}
« PrevPage 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 16Next »

Add Comment