The Daily WTF: Curious Perversions in Information Technology

2009-07-26 Reply Admin

A couple of more solutions with Matlab. A solution, which follows the specifications pretty much to the letter:

function z = russianmultiply(x, y)
  A = [x, y];
  while A(end,1) ~= 1
    A(end+1,:) = [floor(A(end,1)/2), A(end,2)*2];
  end
  A(~mod(A(:,1), 2),:) = [];
  z = sum(A(:, 2));

And another solution for matrix input (works as Matlab function times would with positive integers):

function Z = russianpeasantmultiply(X, Y)
  if any(size(X) ~= size(Y))
    error('Matrix dimensions must agree');
  end
  dim = size(X);
  X = reshape(X, 1, prod(size(X)));
  Y = reshape(Y, 1, prod(size(Y)));
  while any(X(end, :) > 1)
    X(end+1, :) = floor(X(end, :)/2);
    Y(end+1, :) = Y(end, :)*2;
  end
  Z = sum(Y.*mod(X,2));
  Z = reshape(Z, dim);

2009-07-26 Reply Admin

Ok, I found a very small improvement to my earlier progs. Function:

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

1 char less, for 49 and 70 respectively...

Not a function:

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

One char less, 34 chars for the algorithm, 61 for the one-liner.

I actually thought / wouldn't return an int and bit shift had to be used, for some reason. Go me.

2009-07-26 Reply Admin

curtmack:

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

Ok, because I'm really bored. There's a bug in the (still awesome) Befunge program by mister curtmack, so I decided to add actual support for writing out the answer while fixing the bug. Unfortunately, it's pretty hard to control so many variables in Befunge, so I used the p and g operators. This works, but has a nasty effect of only counting up to 65536. Bleh. This will print out both the things that would be added and the answer (if it's under 65536, the proper one ;)).

&& 000p     v
v.:p00:\<   \ 
\       |%2:<
v       <@p00"&".<
v < \.:p00+g00:\<g
>      2/\2*\:2%|0
^              <:0
               ^_^

2009-07-26 Reply Admin

#!/usr/bin/ruby

def russian_peasant_mutiplication(left, right)
  total = 0
  if(left % 2 == 1)
    total = right
  end
  while left > 0
    left = left / 2
    right = right * 2
    if(left % 2 == 1)
      total += right
    end
  end
  return total
end

puts russian_peasant_mutiplication(ARGV[0].to_i, ARGV[1].to_i).to_s

2009-07-26 Reply Admin

A little PDP-8 love :)

*200

MAIN, CLA CLL

LOOP, CLA CLL TAD ONE AND FACTA SNA JMP NOPE

CLA CLL TAD FACTB TAD OUT DCA OUT

NOPE, CLL TAD FACTB RAL DCA FACTB

CLL TAD FACTA RAR CLL SNA JMP NOMAS

DCA FACTA JMP LOOP

NOMAS, HLT

ONE, 0001 FACTA, 0010 FACTB, 0010 OUT, 0000

2009-07-26 Reply Admin

Here is Ruby solution that takes two arguments on the command line and prints their product on the standard output. Both arguments have to be non-negative, but they can be zero and it's no problem.

a=ARGV[0].to_i
b=ARGV[1].to_i
product=0;
while(a > 0)
  product += b if a & 1 != 0
  a /= 2;
  b *= 2;
end
puts product

Here is a solution in PIC assembly, which will run on the 8-bit PIC18F14K50 processors that my company uses in our products The language is defined on page 306 of the PIC18F14K50 datasheet. The function peasantMultiply multiplies two 8-bit unsigned integers and stores the 16-bit unsigned result in PRODH:PRODL. The arguments to the function should be placed in pMultA and pMultB. A temporary register pMultBH is used so that we can have a 16-bit unsigned integer pMultBH:pMultB that stores the doubled value of B. The algorithm here is essentially the same as the Ruby code above, except that dividing A by two is done at the same time that we are testing whether it is odd or not.

    EXTERN PRODL
    EXTERN PRODH
    EXTERN STATUS

    UDATA_ACS
    GLOBAL pMultA
    GLOBAL pMultB
pMultA RES 1
pMultB RES 1
pMultBH RES 1

    CODE
	GLOBAL peasantMultiply
peasantMultiply:
    clrf PRODL      ; Set prodcut to zero.
    clrf PRODH      ; Set product to zero.
    clrf pMultBH    ; Set pMultBH to zero so we can use it as the
                    ;   upper byte of a two-byte integer.
    bcf STATUS, 0   ; Set the carry bit to zero.
loop:
    rrcf pMultA     ; Shift pMultA right through the carry bit.
    bnc doneAdding  ; If A was was even before shifting,
                    ;   skip the addition.
    movf pMultB, W  ; Add pMultBH:pMultB to PRODH:PRODL.
    addwf PRODL     ;   ...
    movf pMultBH, W ;   ...
    addwfc PRODH    ;   ...
doneAdding:         ; The carry bit will always be zero here.
    rlcf pMultB     ; Double pMulbBH:pMultB.
    rlcf pMultBH    ;   ...
    movf pMultA     ; Test pMultA.
    bnz loop        ; Do the loop again if pMultA != 0.
done:
    return          ; pMultA is zero, so return.

    END

So that's 15 instructions. I challenge anyone to come up with a smaller solution!

--David Grayson DavidEGrayson.com

2009-07-26 Reply Admin

Python solution that probably exactly matches one in the last 15 pages of submissions, but I couldn't be bothered looking:

def russian_peasant_multiply(a, b):
    total = 0
    while a:
        (a, remainder) = divmod(a, 2)
        if remainder:
            total += b
        b *= 2
    return total

2009-07-27 Reply Admin

Havn't seen any solutions in Labview. Lets see if the pic works:

http://share.ovi.com/media/zeppelin-79.public/zeppelin-79.10204

2009-07-27 Reply Admin

a href="http://share.ovi.com/media/zeppelin-79.public/zeppelin-79.10204">Peasant Multiplication - Share on Ovi

2009-07-27 Reply Admin

I am disturbed by the number of implementations (Alex's included!) that will obviously fail when asked to calculate 11 (or 00). But here's mine:

#!/usr/bin/perl -w

use strict;

die "usage: $0 NUM1 NUM2\n" unless @ARGV==2;
my ($n1,$n2)=@ARGV;

my $result=0;
for(;;) {
    $result+=$n2 if $n1%2;
    last unless $n1>1;
    $n1=int($n1/2); $n2=$n2*2;
}
print "$result\n";

I read some of the comments after writing this, and wished I had considered the (elegant) recursive solution too. I believe my solution works for NUM1>=0 and any NUM2.

2009-07-27 Reply Admin

ah well. just read that article and even tho its late i will still submit the work of 2 minutes :)

def rmul(x, y):
    if x == 1:
        return y
    a = y << 1
    while (x != 1):
        x = x >> 1
        y = y << 1
    return y + a

2009-07-27 Reply Admin

Linq is lazy (just as F#). So you can use .Range to generate an infinite list and stop when left goes 0.

C#4 using bigintegers (so it makes "sense" to generate an infinite list):

static BigInteger Multiply3(BigInteger left, BigInteger right)
{
   return 
      Enumerable.Range(0, int.MaxValue)
      .Select(i => 
         new
            {
               Left = left >> i, 
               Right = right << i,
            })
      .TakeWhile(tuple => !tuple.Left.IsZero)
      .Where(tuple => !tuple.Left.IsEven)
      .Aggregate(
         new BigInteger(0),
         (seed, tuple) => seed + tuple.Right);
}

Dascandy · 2009-07-27 Reply Admin

IEnumerable<int> factors(int x)
{
   while (x > 0) { yield return ((x & 1) != 0); x >>= 1; }
}

int russianmult(int a, int b)
{
    int sum = 0;
    foreach(bool x in factors(a))
    {
        if (x)
            sum += b;
        b <<= 1;
    }
    return sum;
}

A C# solution with yield return.

2009-07-27 Reply Admin

Lunkwill: 68k entries are commendable, I tried to optimize it a bit but bear in mind that I haven't programmed 68k in 15 years.

Untested ofc.

; op1: d0
; op2: d1
; out: d0
; scratch: d2 (has to be zero on entry)

loop:	add.l	d1,d2
skip:	add.l	d1,d1
peasantmult:
	lsr.l	#1,d0
	bcs.s	loop
	bne.s	skip
	move.l	d2,d0
	rts

2009-07-27 Reply Admin

My attempt to at the shortest possible solution in Perl:

($a,$b)=@ARGV;
while($a){$r+=$a&1&&$b;$a>>=1;$b<<=1}
print "$r\n";

It's just too bad that there has to be a verbose initialization step :/

2009-07-27 Reply Admin

I believe this is a new record for number of comments. And it's definitely a new record for the ratio of genuine comments to spam/troll/rubbish comments.

workmad3 · 2009-07-27 Reply Admin

As others seem to be going for shortest, here is my super-short 1-liner in python (which is the same as what I've posted previously, but without the embedded function required to decorate the function and allow full negative multiplication ;))

def m(a,b):
    return 0 if not a else m(a/2,b*2)+(b if a%2 else 0)

This will cause infinite recursion if called with a negative number for a though...

mol1111 · 2009-07-27 Reply Admin

Version in Baltie 3: [image]

Frixus · 2009-07-27 Reply Admin

Written in Java, this function works for any two ints, returning the same value as normal multiplication would. (Though I have to admit, I didn't try all possible combinations to verify this claim.) A trivial command-line interface is provided, which, I'm sad to say, isn't quite as fool-proof as the implementation itself.

class RussionMultiplication
{
	static int multiply(int a, int b)
	{
		int c = 0;
		if (a != 0)
		while (true)
		{
			if ((a & 1) == 1) c += b;
			if (a == 1) break;
			a >>>= 1;
			b <<= 1;
		}
		return c;
	}

	public static void main(String[] args)
	{
		int a = Integer.parseInt(args[0]);
		int b = Integer.parseInt(args[1]);
		System.out.println(args[0] + " x " + args[1] + " = " + multiply(a, b));
	}
}

2009-07-27 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;}

Now do it without semicolons and I'll be impressed..

2009-07-27 Reply Admin

Goujon:
My attempt to at the shortest possible solution in Perl:
($a,$b)=@ARGV;
while($a){$r+=$a&1&&$b;$a>>=1;$b<<=1}
print "$r\n";
It's just too bad that there has to be a verbose initialization step :/

Whoa, how could I miss this? This lets me chop 2 characters off... algorithm, one-liner (though with semicolons...):

$_+=$a&1&&$b,$a/=2,$b*=2while $a
$ perl -E'($a,$b)=@ARGV;$_+=$a&1&&$b,$a/=2,$b*=2while $a;say' 18 23
414
$ perl -E'($a,$b)=@ARGV;$_+=$a&1&&$b,$a/=2,$b*=2while $a;say' 135 975
131625

59 + args for the one-liner and just 32 for the algorithm! Thanks to mister Goujon, who made this one possible :).

And specially for RedAdder, an improved function, non-semicolon version...

Func:

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

47 chars!

And the one liner, no semicolons:

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

68 chars!

Again thanks to Goujon for opening my eyes. I am not worthy :).

mol1111 · 2009-07-27 Reply Admin

Guido van Robot version (not optimal):

define back:
	turnleft
	turnleft

define turnright:
	turnleft
	back

define is_odd:
	while next_to_a_beeper:
		pickbeeper
		if next_to_a_beeper:
			pickbeeper
		else:
			move
			putbeeper
			back
			move
			back
	while any_beepers_in_beeper_bag:
		putbeeper

define add_up:
	while next_to_a_beeper:
		pickbeeper
		turnleft
		move
		turnleft
		move
		pickbeeper
		back
		move
		move
		turnright
		move
		putbeeper
		turnright
		move
		back
	while any_beepers_in_beeper_bag:
		putbeeper
	back
	move
	turnleft

define half:
	while next_to_a_beeper:
		pickbeeper
		if next_to_a_beeper:
			pickbeeper
		back
		move
		putbeeper
		back
		move
	while any_beepers_in_beeper_bag:
		putbeeper

define double:
	while next_to_a_beeper:
		pickbeeper
		move
		turnleft
		move
		pickbeeper
		back
		move
		turnright
		move
		back
	while any_beepers_in_beeper_bag:
		putbeeper

move
while next_to_a_beeper:
	is_odd
	move
	if next_to_a_beeper:
		pickbeeper
		back
		move
		move
		putbeeper
		turnright
		move
		turnright
		move
		turnleft
		add_up
	else:
		back
		move
		back
	half
	if next_to_a_beeper:
		turnleft
		move
		turnleft
		double
		turnleft
		move
		turnleft
turnoff

The world should look like this:

robot 1 1 E 0
beepers 1 1 500
beepers 2 2 12
beepers 2 1 13

12 and 13 are the numbers which will be multiplied. 500 is just big enough buffer of beepers. The result will be put at

position 2 3 (above 12 and 13).

mol1111 · 2009-07-27 Reply Admin

I have also version for karelNB, but that's limited for results <= 8.

mult.kar:

DEFINE Back AS LEFT LEFT END

DEFINE MoveOneSignTwoCells AS PICK STEP STEP PUT Back
STEP STEP Back END

DEFINE MoveAllSignsTwoCells AS WHILE IS SIGN MoveOneSignTwoCells END END

DEFINE IsOdd AS WHILE IS SIGN MoveOneSignTwoCells IF NOT SIGN STEP PUT Back STEP Back ELSE MoveOneSignTwoCells END END STEP STEP Back MoveAllSignsTwoCells END

DEFINE AddUp AS WHILE IS SIGN PICK STEP PUT STEP PUT Back STEP STEP Back END STEP STEP Back MoveAllSignsTwoCells REPEAT 3 TIMES STEP END END

DEFINE Half AS WHILE IS SIGN PICK IF IS SIGN PICK STEP STEP PUT Back STEP STEP Back END END STEP STEP Back MoveAllSignsTwoCells STEP STEP END

DEFINE Double AS WHILE IS SIGN PICK STEP STEP PUT PUT Back STEP STEP Back END STEP STEP Back MoveAllSignsTwoCells STEP
STEP END

STEP WHILE IS SIGN IsOdd STEP IF IS SIGN PICK RIGHT
STEP LEFT STEP RIGHT AddUp LEFT ELSE STEP Back END Half IF IS SIGN RIGHT STEP RIGHT Double LEFT STEP LEFT END END

Town example:

mult.kat:

10 10

10 1

WWWWWWWWWWWW W W W W W W W W W W W W W W W W W 2 W W 3 W WWWWWWWWWWWW

Addendum (2009-07-27 20:07): Image of a successful run: [image]

EnterpriseSolutionsLTD · 2009-07-27 Reply Admin

C# (4.0):

using System;
using System.Collections.Generic;
using System.Linq;

public static class Russian
{
    public static long Multiply(long multiplier, long multiplicand)
    {
        var s = new List<Tuple<long, long>>
        {
            new Tuple<long, long>(multiplier, multiplicand)
        };

        while (s.Last().Item1 != 1)
        {
            s.Add(new Tuple<long, long>(
                s.Last().Item1 / 2, s.Last().Item2 * 2));
        }

        return s.AsParallel().Sum(
            q => q.Item1 % 2 == 0 ? 0 : q.Item2);
    }
}

Addendum (2009-07-27 21:37): Or:

public static class Russian
{
    public static long Multiply(long multiplier, long multiplicand)
    {
        var s = new List<Tuple<long, long>> { Tuple.Create(multiplier, multiplicand) };

        while (s.Last().Item1 != 1)
        {
            s.Add(Tuple.Create(s.Last().Item1 / 2, s.Last().Item2 * 2));
        }

        return s.AsParallel().Sum(q => q.Item1 % 2 == 0 ? 0 : q.Item2);
    }
}

2009-07-28 Reply Admin

But no Ada`?

2009-07-28 Reply Admin

Here's my version using vba - so at least loads of you can run it. I've sped it up by checking which no. is largest so it doesn't loop for ages.

'Function to do multiplication like a russian peasant Private Function MultiplyLikePeasant(ByVal n1 As Long, ByVal n2 As Long) As Long

Dim nTotal As Long
Dim nTmp As Long
nTmp = n1

'Check the order so we minimise the no. of iterations
If nTmp > n2 Then
    n1 = n2
    n2 = nTmp
End If

Do
    If n1 Mod 2 <> 0 Then
        nTotal = nTotal + n2
    End If
    
    n1 = n1 \ 2
    n2 = n2 * 2

Loop While n1 > 1

MultiplyLikePeasant = nTotal + n2

End Function

Private Sub CommandButton1_Click() MsgBox MultiplyLikePeasant(18, 317) End Sub

2009-07-28 Reply Admin

btw it was indented when i previewed it...

2009-07-28 Reply Admin

Surround your code pastes with code tags. See http://en.wikipedia.org/wiki/BBCode.

2009-07-28 Reply Admin

Using VbScript ... the "Incredible Machine" sorta way

Dim bDebug
bDebug = True

Dim intFirstNumber, intSecondNumber, intTempNumber1, intTempNumber2
intFirstNumber = 18
intSecondNumber = 23

NumberVerification intFirstNumber
NumberVerification intSecondNumber

debug "working with whole numbers only"
intFirstNumber = Abs(Int(intFirstNumber))
intSecondNumber = Abs(Int(intSecondNumber))

debug intFirstNumber
debug intSecondNumber

Dim arrFirstNumber(), arrSecondNumber(), i, intFinalAnswer
ReDim arrFirstNumber(0)
ReDim arrSecondNumber(0)

arrFirstNumber(0) = intFirstNumber
arrSecondNumber(0) = intSecondNumber
debug "array 0 = intFirstNumber " & arrFirstNumber(0)
i = 0
intTempNumber1 = arrFirstNumber(0)
intTempNumber2 = arrSecondNumber(0)

Do While Int(intTempNumber1) <> 0
	DivideNumber arrFirstNumber(i)
	MultiplyNumber arrSecondNumber(i)
	i = i + 1
	ReDim Preserve arrFirstNumber(i)
	ReDim Preserve arrSecondNumber(i)
	arrFirstNumber(i) = intTempNumber1
	arrSecondNumber(i) = intTempNumber2
Loop

ReDim Preserve arrFirstNumber(Ubound(arrFirstNumber) - 1)
ReDim Preserve arrSecondNumber(Ubound(arrSecondNumber) - 1)

For i = 0 to Ubound(arrFirstNumber)
	debug "arrFirstNumber(" & i & ") " & arrFirstNumber(i) & " | arrSecondNumber(" & i & ") " & arrSecondNumber(i)
	If arrFirstNumber(i) Mod 2 <> 0 Then
		intFinalAnswer = intFinalAnswer + arrSecondNumber(i)
	End If
Next

If Len(intFinalAnswer) < 1 Then
	intFinalAnswer = 0
End If

debug "The result of " & intFirstNumber & " times " & intSecondNumber & " is " & intFinalAnswer

Function DivideNumber(Number)
	intTempNumber1 = Int(Number / 2)
End Function

Function MultiplyNumber(Number)
	intTempNumber2 = Number * 2
End Function

Function NumberVerification(intNumbertoCheck)
	If Not isNumeric(intNumbertoCheck) Then
		debug intNumbertoCheck & " is not a number, exiting script"
		WScript.Quit
	Else
		debug intNumbertoCheck & " is a number, continuing"
	End If
End Function

Function Debug(strMessage)
	If bDebug Then
		WScript.Echo strMessage
	End If
End Function

2009-07-28 Reply Admin

Here's my version:

int russian_multiply(int a, int b) { return a*b; }

On most hardware multipliers, this will be done with the peasant multiplication algorithm anyway :)

CorgiDude · 2009-07-28 Reply Admin

My version is C. The difference between mine and most of the others is:

Error checking
Proper formatting -- conforms to the style standards of my corporate environment!
You can print the columns if you define PRINT_COLUMNS during compilation
Tested with Very Large Numbers.

Only bug is that 1*1 (and -neg) doesn't work. This is all noted in the function comment.

Note that I only hacked this for like an hour, when there was a lull in Real Work, and I didn't get much sleep last night, so there might be something I missed.

Code follows.

/************************************************************************
 * main.c - Main file for Russian Peasant Program			*
 * Russian Peasant Program for Daily WTF				*
 * Copyright (c) 2009 Wilcox Technologies.  All rights reserved.	*
 *									*
 * License: public domain						*
 ************************************************************************/

#include <stdio.h>		// printf, fprintf
#include <stdint.h>		// [u]int[32|64]_t
#include <stdlib.h>		// atoi, exit

/* error codes */
#define	ERR_NOT_ENOUGH_PARAMS	0x01

/*
 *	int64_t russianMul(uint32_t a, uint32_t b)
 *	Mulplies two numbers using the Russian Peasant algorithm.
 *	
 *	Input:
 *		a: the number to multiply
 *		b: the other number to multiply
 *	Output:
 *		The resulting product.
 *	Notes:
 *		Does not work correctly with negative numbers.
 *		This is a by-product of using bit-shifting for fast numeric processing.
 *		Doesn't work with 1*1 because of the bit-shifting also.
 */
int64_t russianMul(uint32_t a, uint32_t b)
{
	int64_t result = 0;
	
#ifdef PRINT_COLUMNS
	printf("%08d\t%08d\n", a, b);
#endif
	do
	{
		do
		{
			a >>= 1;
			b <<= 1;
#ifdef PRINT_COLUMNS
			printf("%08d\t%08d\n", a, b);
#endif
		} while(((a % 2) == 0) && (a > 1));

		result += b;
	} while (a > 1);
	
	return result;
};

/*
 *	int main(int argc, const char *argv[])
 *	The entry-point for Russian Peasant Program
 *	
 *	Input:
 *		argc: The number of arguments supplied in argv
 *		argv: The arguments, in string format
 *	Expected Parameter Format:
 *		Two string representations of numbers in argv[1] and [2]
 *	Output:
 *		The result of the multiplication of said numbers using the Russian Peasant algorithm.
 *	Notes:
 *		None in this version.
 */
int main (int argc, const char *argv[])
{
	uint32_t a, b;
	
	if(argc < 2)
	{
		fprintf(stderr, "Not enough parameters given.\n\nUsage: RussianPeasant number1 number2\nOther parameters are silently ignored.\n");
		exit(ERR_NOT_ENOUGH_PARAMS);
	};
    
	a = atoi(argv[1]);
	b = atoi(argv[2]);
	
	printf("The product of %d and %d is %qi\n", a, b, russianMul(a, b));
	
	return 0;
};

mol1111 · 2009-07-28 Reply Admin

Much shorter version:

DEFINE Back AS 
    LEFT 
    LEFT 
END 

DEFINE IsOddAndHalf AS 
    IF IS SIGN 
        PICK 
        IF NOT SIGN 
            STEP 
            PUT 
            Back
            STEP
            Back
        ELSE
            PICK 
            IsOddAndHalf
            PUT 
        END 
    END
END 

DEFINE AddUp AS
    IF IS SIGN 
        PICK 
        STEP 
        PUT 
        Back
        STEP 
        Back
        AddUp
        PUT 
    END 
END 

DEFINE Double AS 
    IF IS SIGN 
        PICK 
        Double
        PUT
        PUT 
    END 
END

DEFINE MoveToSecond AS 
    LEFT
    STEP 
    LEFT 
    STEP 
END 

STEP
WHILE IS SIGN 
    IsOddAndHalf
    STEP 
    IF IS SIGN 
        PICK 
        MoveToSecond
        RIGHT 
        AddUp
        Back
        STEP 
        Back
    ELSE 
        Back
        STEP
        RIGHT 
    END 
    IF IS SIGN 
        STEP 
        Double
        Back
        STEP 
        LEFT
    END 
END

2009-07-28 Reply Admin

I know, I know, boring old Java. I did it in C first, but didn't want to embarrass myself too badly.

import java.math.*;

public class RussianProduct {

    public static BigInteger multiply(BigInteger a, BigInteger b) {
        BigInteger sign = (a.xor(b).compareTo(BigInteger.ZERO) < 0)?BigInteger.ONE.negate():BigInteger.ONE;
        BigInteger p = BigInteger.ZERO;

        if(a.equals(BigInteger.ZERO) || b.equals(BigInteger.ZERO))
            return(BigInteger.ZERO);

        a = a.abs();
        b = b.abs();

        if(a.equals(BigInteger.ONE))
            return(b.multiply(sign));
        if(b.equals(BigInteger.ONE))
            return(a.multiply(sign));

        for(;;) {
            if(!(a.mod(new BigInteger("2"))).equals(BigInteger.ZERO))
                p =  (p.add(b));

            a = a.shiftRight(1);

            if(a.equals(BigInteger.ZERO)) {
                return(p.multiply(sign));
            }

            b = b.shiftLeft(1);
        }
    }

    static void printUsage() {
        System.err.println("RussianProduct java.math.BigInteger java.math.BigInteger");
    }

    public static void main(String [] args) {
        BigInteger product = null;

        if(args.length < 2) {
            printUsage();
            System.exit(-1);
        }

        try {
            product = multiply(new BigInteger(args[0]), new BigInteger(args[1]));
            System.out.println("Product(" + args[0] + ", " + args[1] + "): " + product);
        }
        catch(NumberFormatException nfe) {
            printUsage();
        }

    }
}

2009-07-28 Reply Admin

peasant = sum . map snd . filter (odd . fst) . fix (\f xs@((a,b):_) -> if a == 1 then xs else f $ (a div 2,b * 2) : xs) . (:[])

2009-07-29 Reply Admin

This almost 100% matches the * operator. I did get some differences when dealing with int.MaxValue and int.MinValue multiplications.

// C#

public int MultiplyLoop(int x, int y) { int result = 0; int sign = x ^ y; x = (x ^ (x >> 31)) - (x >> 31); y = (y ^ (y >> 31)) - (y >> 31);

while (x > 0)
{
    if ((x & 0x1) == 1)
    {
        result += y;
    }
    
    x >>= 1;
    y <<= 1;
}

return (sign >= 0) ? result : -result;

}

2009-07-29 Reply Admin

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

Updated version below, Now supports zero and negative values:

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

2009-07-29 Reply Admin

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

Ignore my previous post.

Updated version with zero and negative value support:

public static int Multiply(int x, int y) { return (x % 2 * y) + (Math.Abs(x) > 1 ? Multiply(x / 2, y * 2) : 0);
}

2009-07-29 Reply Admin

C

int rpmul(int a, int b) { int c = 0; for (; a >= 1; (a % 2) ? c += b : 0, a /= 2, b *= 2); return c; }

2009-07-29 Reply Admin

I found this one after the one about Josephus's circle. This one seemed much easier. Here it is in C#:

public static int peasantRiddle(int left, int right) { int leftVal = 0; int rightVal = 0; int result = 0; List<int> leftSide = new List<int>(); List<int> rightSide = new List<int>();

        leftSide.Add(left);
        rightSide.Add(right);

        leftVal = left / 2;
        rightVal = right * 2;

        while(leftVal >= 1)
        {
            leftSide.Add(leftVal);
            rightSide.Add(rightVal);
            rightVal = rightVal * 2;
            leftVal = leftVal / 2;
        }

        for(int i =0; i < leftSide.Count ; i++)
        {
            if (leftSide[i] % 2 != 0)
            {
                result += rightSide[i];
            }                
        }

        return result;
    }

Christian · 2009-07-29 Reply Admin

I know its a bit late, but I'd like to add a Powershell version.

function CustomMultiply ($mult1, $mult2)
{
    @(for (;$mult1 -gt 0; $mult1,$mult2=[Int]($mult1/2),($mult2*2)) {,($mult1, $mult2)}) |
        foreach{$a=($_[0] % 2) * $_[1]
            ,($_ + $a)} |
        foreach -begin {$total = 0} -process {$total += $_[2]} -end {$total}
}

2009-07-29 Reply Admin

Nick Pope:
After my earlier attempt with bc, I decided to try something more difficult: dc. Seems to work with negative numbers nicely too.
Using dc (GNU bc 1.06.95) 1.3.95:
Code (peasant.dc):
sbsa0[la2~rsalbd2*sb*+0la!=r]dsrxp

I thought it was more fun to include the running status with this

r[l=]npr[r=]npsbsa0[la2~[+ ]nd48+an[ x ]nlbn10anr[l=]npsalbd2*[r=]npsb*+0la!=r]dsrx[sum=]np

Example:

$ dc -e  39 -e 83 peasant.dc
l=39
r=83
+ 1 x 83
l=19
r=166
+ 1 x 166
l=9
r=332
+ 1 x 332
l=4
r=664
+ 0 x 664
l=2
r=1328
+ 0 x 1328
l=1
r=2656
+ 1 x 2656
l=0
r=5312
sum=3237

2009-07-30 Reply Admin

An Error Occured (again)...

but... I'm pretty sure we can reach 750 comments on this article if the damn thing lets me post...

2009-07-30 Reply Admin

Try this...

(Common Lisp)

(defun rm(x y)
  (apply #'+ (loop for a = x then (floor a 2)
                   for b = y then (* b 2)
                   when (oddp a) collect b
                   until (zerop a))))

2009-07-30 Reply Admin

Try this...

(Common Lisp)

(rm -18 23)

2009-07-31 Reply Admin

Here it is in Whitespace:

(hahahahahahahahahahhaahaha!)

2009-07-31 Reply Admin

Congrats on reaching 750 comments everyone, this is a new record!

2009-07-31 Reply Admin

reol:
But no Ada`?

Since you asked so nicely:

with Ada.Command_Line;
with Ada.Text_IO;
procedure Russian_Peasant_Multiplication is
L, R : Integer;
Result : Integer := 0;
begin
L := Integer'Value(Ada.Command_Line(1));
R := Integer'Value(Ada.Command_Line(2));
while L /= 0 loop
Result := Result + (L rem 2)R;
L := L/2;
R := R2;
end loop;
Ada.Text_IO.Put_Line(Integer'Image(Result));
end Russian_Peasant_Multiplication;

Works for negative numbers, 11, 00, etc... No validation of input, though...

2009-07-31 Reply Admin

Mine is late because I've only just discovered thedailywtf, so I naturally don't deserve a sticker, but hopefully the other 6502-heads will enjoy this:

; Unsigned 8x8 multiply
;
; In:	Multiplicand in mpand
;	Multiplier in A
;
; Out:	16 bit product in A:prodl
;	mpand, other regs and memory unchanged
;
; 64 bytes
; 95-111 cycles
;
; Uses the Russian Peasant algorithm (repeatedly halving
; the multiplier, doubling the multiplicand, and adding the
; multiplicand to the partial product if the multiplier is
; odd).
;
; Bit shifting is minimized by having the partial product
; share a 17 bit word (carry:A:prodl before each shift
; and A:prodl:carry after) with the multiplier.
;
; The partial product initially occupies the leftmost eight
; bits, the multiplier the rightmost eight; the unused bit
; between them is zeroed. Each right-shift allocates one
; more bit to the partial product while simultaneously
; narrowing and halving the multiplier.
;
; The partial product's shifting alignment *implicitly*
; doubles the multiplicand, allowing a single instruction
; to add its 8 most significant bits to those of the partial
; product. 
;
; After eight shifts, the leftmost 16 bits are occupied by
; the partial (now final) product and the multiplier has
; disappeared altogether.
;
; As a final optimization, the multiplier is held in bit-
; inverted form so that the carry flag will already be zero
; whenever an addition is necessary (the 6502 has no pure
; add instruction, only an add with carry).

mpand	equ $06		;Anywhere on page zero will do
prodl	equ $07		;Anywhere on page zero will do

mul8u:
	eor #$FF	;Bit-invert multiplier
	lsr		; and align it in rightmost
	sta prodl	; eight bits of A:prodl:carry
	lda #0		;Initialize partial product
	bcs mul8u7	;If multiplier bit 0 was set,
	adc mpand	; add mpand to partial product
mul8u7:
	ror		;Widen and realign partial product
	ror prodl	; and narrow and halve multiplier
	bcs mul8u6	;If multiplier bit 1 was set,
	adc mpand	; add mpand*2 to partial product
mul8u6:
	ror		;Widen and realign partial product
	ror prodl	; and narrow and halve multiplier
	bcs mul8u5	;If multiplier bit 2 was set,
	adc mpand	; add mpand*4 to partial product
mul8u5:
	ror		;Widen and realign partial product
	ror prodl	; and narrow and halve multiplier
	bcs mul8u4	;If multiplier bit 3 was set,
	adc mpand	; add mpand*8 to partial product
mul8u4:
	ror		;Widen and realign partial product
	ror prodl	; and narrow and halve multiplier
	bcs mul8u3	;If multiplier bit 4 was set,
	adc mpand	; add mpand*16 to partial product
mul8u3:
	ror		;Widen and realign partial product
	ror prodl	; and narrow and halve multiplier
	bcs mul8u2	;If multiplier bit 5 was set,
	adc mpand	; add mpand*32 to partial product
mul8u2:
	ror		;Widen and realign partial product
	ror prodl	; and narrow and halve multiplier
	bcs mul8u1	;If multiplier bit 6 was set,
	adc mpand	; add mpand*64 to partial product
mul8u1:
	ror		;Widen and realign partial product
	ror prodl	; and narrow and halve multiplier
	bcs mul8u0	;If multiplier bit 7 was set,
	adc mpand	; add mpand*128 to partial product
mul8u0:
	ror		;Widen and realign product and
	ror prodl	; discard last bit of multiplier
	rts

2009-07-31 Reply Admin

Anonymous:
Here it is in Whitespace:
(hahahahahahahahahahhaahaha!)

Granted, it's whitespace, and it runs... But pushing 0s to the stack is not what this Praxis is about... It's about multiplying to numbers using a specific algorithm...

Here's one that actually works: (I hope the forum software doesn't screw it up. It looks good in Preview)

--start(do not include this line:)
   		
   	 
    	
	
			
		     
		 
   	     	
    	
			
	  	    	 
   		
    	
			   	 
	 		   	 
				  
   		
				   		     	
    	
			   	 
	 	 		    	 
   	 
			   	 
	  
		 
 
 	     	

   	    	 
   		
				
 	

--end (do not include this line)

--

2009-07-31 Reply Admin

egilhh:

reol:
But no Ada`?

Since you asked so nicely:

with Ada.Command_Line;
with Ada.Text_IO;
procedure Russian_Peasant_Multiplication is
L, R : Integer;
Result : Integer := 0;
begin
L := Integer'Value(Ada.Command_Line(1));
R := Integer'Value(Ada.Command_Line(2));
while L /= 0 loop
Result := Result + (L rem 2)R;
L := L/2;
R := R2;
end loop;
Ada.Text_IO.Put_Line(Integer'Image(Result));
end Russian_Peasant_Multiplication;

Works for negative numbers, 11, 00, etc... No validation of input, though...

Oops... Should be

   L := Integer'Value(Ada.Command_Line.Argument(1));
   R := Integer'Value(Ada.Command_Line.Argument(2));

Russian Peasant Multiplication

Serves me right for not copy/paste-ing

Leave a comment on “Russian Peasant Multiplication”