• Romeo (unregistered) in reply to Bob

    You've just forget to sum the first line...

    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.

  • Bob (unregistered) in reply to Jeff Kemp
    Jeff Kemp:
    Bob:
    Peasants get:[code] 45 x 76 22 152 0 11 304 304 5 608 608 2 1216 0 1 2432 2432 ====================== 3344

    You forgot to add the initial 76: 45 is odd.

    I will blame this on poor specifications.

  • djjeavons (unregistered) 
        Private Function Multiply(ByVal number As Integer, ByVal multiplyBy As Integer)

        Dim lastNumber As Integer = number
        Dim remainder As Integer = 0
        Dim additionNumbers As Integer = 0
        Dim lastMultiplyByValue As Integer = multiplyBy

        System.Math.DivRem(System.Math.DivRem(lastNumber, 2, remainder), 2, remainder)
        If remainder = 0 Then additionNumbers += lastMultiplyByValue

        Do Until lastNumber = 1

            lastMultiplyByValue *= 2
            System.Math.DivRem(System.Math.DivRem(lastNumber, 2, remainder), 2, remainder)
            lastNumber = System.Math.Floor(lastNumber / 2)

            If Not remainder = 0 Then
                additionNumbers += lastMultiplyByValue
            End If

        Loop

        Return additionNumbers

    End Function
  • csulli13 (unregistered)

    SQL function using columns

    CREATE FUNCTION RussianMultiply (@Num1 int, @Num2 int) RETURNS int AS BEGIN

    CREATE TABLE #Columns(C1 int, C2 int)

    WHILE @Num1 >= 1 BEGIN

    INSERT INTO #Columns VALUES(@Num1, @Num2)

SET @Num1 = @Num1/2
SET @Num2 = @Num2 * 2

    END

    DELETE FROM #Columns WHERE C1 % 2 = 0

    RETURN SUM(C2) FROM #Columns

    END

  • Maxim (unregistered)

    Haskell, point-free style:

    russian = curry $ sum . map snd . filter (odd.fst) . takeWhile ((>0).fst) . iterate ((div2) *** (*2))

  • (cs)

    Nice idea. F# solution, without much thoughts put into it (in other words: Nicer solutions probably exist) and assuming #light:

    let russianMultiplication (x:int) (y:int) =
    let rec russianMultiplicationRec x y l =
        match x with
            | 0 -> [(1, 0)]
            | 1 -> ((1, y) :: l)
            | _ -> russianMultiplicationRec (x/2) (y*2) ((x, y) :: l)

    russianMultiplicationRec x y []
    |> List.fold (fun acc (x, y) -> 
        if x % 2 = 1 then acc + y
        else acc
    ) 0
  • (cs) in reply to SR

    I think we did one worse.

    Database error A database query syntax error has occurred. This may indicate a bug in the software. The last attempted database query was: 
    (SQL query hidden)

    from within function "MediaWikiBagOStuff::_doquery". MySQL returned error "1194: Table 'mw_objectcache' is marked as crashed and should be repaired (localhost)".

  • Osno (unregistered)

    All the people looping on 1 instead of 0 fail. All the people using multiplication and division instead of shifting (except in languages where there is no shifting) also fail.

  • SR (unregistered)

    ColdFusion:

    <cffunction name="multiply" returntype="numeric"> <cfargument name="x" required="Yes" type="numeric"> <cfargument name="y" required="Yes" type="numeric"> <cfargument name="total" required="no" type="numeric">

    &lt;cfif NOT IsDefined("arguments.total")&gt;
  &lt;cfif arguments.x MOD 2 NEQ 0&gt;
	&lt;cfset arguments.total = arguments.y&gt;
  &lt;cfelse&gt;
	&lt;cfset arguments.total = 0&gt;
  &lt;/cfif&gt;
&lt;/cfif&gt;

&lt;cfset newX = Int(arguments.x / 2)&gt;
&lt;cfset newY = arguments.y * 2&gt;

&lt;cfif newX MOD 2 NEQ 0&gt;
  &lt;cfset arguments.total = arguments.total + newY&gt;
&lt;/cfif&gt;
&lt;cfif arguments.x GT 1&gt;
  &lt;cfset arguments.total = multiply(newX, newY, arguments.total)&gt;
&lt;/cfif&gt;
&lt;cfreturn arguments.total&gt;

    </cffunction>

    Glad I use Java these days.

  • GM (unregistered)

    Another C# one: private int Multiply(int a, int b) { int result = 0, aBy2, bBy2;

            if (a == 1) return b;

        aBy2 = a ;
        bBy2 = b ;
        do
        {
            aBy2 = aBy2 / 2;
            bBy2 = bBy2 * 2;
            if (aBy2 % 2 == 1)
            {
                result += bBy2;
            }
        } while (aBy2 != 1);
                
        return result;
    }
  • Damien (unregistered)

    For those "handling negatives and zero" - the correct behaviour for these, given the literal description of the algorithm, is to loop forever, because the left hand column will never equal 1. (Not that my previous solution gets this right either)

  • SR (unregistered)

    2nd attempt:

    <cffunction name="multiply" returntype="numeric"> <cfargument name="x" required="Yes" type="numeric"> <cfargument name="y" required="Yes" type="numeric"> <cfargument name="total" required="no" type="numeric"> 
    <cfif NOT IsDefined("arguments.total")>
  <cfif arguments.x MOD 2 NEQ 0>
	<cfset arguments.total = arguments.y>
  <cfelse>
	<cfset arguments.total = 0>
  </cfif>
</cfif>

<cfset newX = Int(arguments.x / 2)>
<cfset newY = arguments.y * 2>

<cfif newX MOD 2 NEQ 0>
  <cfset arguments.total = arguments.total + newY>
</cfif>
<cfif arguments.x GT 1>
  <cfset arguments.total = multiply(newX, newY, arguments.total)>
</cfif>
<cfreturn arguments.total>
    </cffunction>
  • Soops (unregistered) in reply to Bob

    Clue:

    3420 - 3344 = 76

  • Jason Knight (unregistered)

    Javascript version:

    function calculate() {
    var num1 = 28;
    var num2 = 13; 
    var tot = 0;
    if ((num1 % 2) != 0) { tot = num2 }
    while (num1 > 1) {
        num1 = Math.floor(num1 / 2);
        num2 *= 2;
        if ((num1 % 2) != 0) { tot += num2 }
    }
    alert(tot);
}
  • cwink (unregistered)

    public static int Multiply( int op1, int op2 ) { return Mult( Math.Abs(op1), op2*op1/Math.Abs(op1) ); }

    private static int Mult( int op1, int op2 ) { if( op1 == 1 ) return op2; else return (op1 & 1)*op2 + Mult( op1 >> 1, op2 << 1 ); }

  • dee (unregistered)

    Iterative Scheme:

    (define (peasant left right)
  (define (peasant-i left right sum)
    (if (= left 0)
        (apply + sum)
        (peasant-i (floor (/ left 2))
                   (+ right right)
                   (if (= (modulo left 2) 1)
                       (append sum (list right))
                       sum))))
  (if (< left 0)
      (peasant-i (- left) (- right) '())
      (peasant-i left right '())))

    Works with negative numbers and zeroes. I tried to follow the manual process as closely as possible :)

  • Jim (unregistered) in reply to phihag
    phihag:
    code golf: Python 3, 1 statement, 1 line, 70 characters: 
    m=lambda a,b:sum(b<

    Python 3, 64 characters

    m=lambda a,b:sum(b<
  • Bob (unregistered) in reply to Bob
    Bob:
    Jeff Kemp:
    Bob:
    Peasants get:[code] 45 x 76 22 152 0 11 304 304 5 608 608 2 1216 0 1 2432 2432 ====================== 3344

    You forgot to add the initial 76: 45 is odd.

    I will blame this on poor specifications.

    I will add that many solutions here are making the same error.

  • Philipp (unregistered)

    public class SmallTest { public static void main(String [] args) { try { int m1 = Math.abs(Integer.parseInt(args[0])); int m2 = Math.abs(Integer.parseInt(args[1])); if (m1 > m2) {int temp = m1; m1 = m2; m2 = temp;} int result = 0; while (m1 >= 1) { if ((m1 & 1) > 0) result += m2; m1 >>= 1; m2 <<= 1; } System.err.println(args[0] + " * " + args[1] + " == " + result); } catch (Exception e) { System.err.println("Whoops: " + e.getMessage()); } } }

    There you go. Even works for negative numbers ;) -- and it heavily optimizes... :)

  • Daniel (unregistered)

    Recursion is always the right answer!!

    function peasantMath($a,$b) { return (($a>>1)%2 == 0 ? 0 : $b<<1) + ($a>>1 == 1 ? 0 : peasantMath($a>>1, $b<<1)); }

    Also, TRWTF is that the link to esoteric languages is throwing database errors.

  • cwink (unregistered) 
      public static int Multiply( int op1, int op2 )
  {
     if( op1 == 0 || op2 == 0 )
        return 0;
     else
        return Mult( Math.Abs(op1), op2*op1/Math.Abs(op1) );
  }

  private static int Mult( int op1, int op2 )
  {
     if( op1 == 1 )
        return op2;
     else
        return (op1 & 1)*op2 + Mult( op1 >> 1, op2 << 1 );

    }

  • Anonymous (unregistered)

    Oh wow, this is unbelievable. No trolls, no grammar nazis, no flame-bait, no spammers - just everyone chipping in on an interesting coding challenge. I think this is probably the most civilised comments page I've ever seen on TDWTF. Well done everyone, you've all earnt a cookie.

  • Bob (unregistered) 
    (define (halve x) (quotient x 2))
(define (double x) (+ x x))
(define (mul x y)
  (let iter ((x (abs x)) 
             (y (if (negative? x) 
                    (- y)
                    y))
             (acc 0))
    (cond
     ((zero? x) acc)
     ((even? x) (iter (halve x) (double y) acc))
     (else (iter (- x 1) y (+ acc y))))))
  • Jeff Kemp (unregistered) in reply to Bob
    Bob:
    Bob:
    Jeff Kemp:
    ...

    You forgot to add the initial 76: 45 is odd.

    I will blame this on poor specifications.

    I will add that many solutions here are making the same error.

    and only those who said their solution is "untested" have half an excuse... :)

  • Daniel (unregistered)

    Adjusted to handle negatives, and to handle an initial odd left operand, as pointed out above. This is PHP by the way, though it's not doing anything special.

    function peasantMath($a,$b) {
    if ( $a < 0 ) {
        $a *= -1;
        $b *= -1;
    }
    return (($a)%2 == 0 ? 0 : $b) + ($a == 1 ? 0 : peasantMath($a>>1, $b<<1));
}

    CAPTCHA: nulla. mmmm, nulla wafers.

  • Éibhear (unregistered) in reply to newlisp.org

    Using emacs lisp (and the dreaded recursion):

    (defun russian-peasant-multiply (factor1 factor2) (cond ((eq factor1 1) factor2 ) ((eq (mod factor1 2) 0) (russian-peasant-multiply (/ factor1 2) (* factor2 2)) ) (t (+ factor2 (russian-peasant-multiply (/ factor1 2) (* factor2 2)))) ) )

  • Stalker (unregistered)

    Another assembly version, this time x64 using nasm

    SECTION	.text
GLOBAL	RussianMul
RussianMul:

[BITS 64]
	xor	rax, rax
.start:
	bt	rcx, 0
	jnc	.even
	add	rax, rdx
.even:
	shr	rcx, 1
	shl	rdx, 1
	test	rcx, rcx
	jnz	.start

	ret
  • YES WE CAN! (unregistered)

    doesn't use any * or /, supports negative numbers:

    #define NEGATE(x) (~(x) + 1)

    int russian_multiplication(int a, int b) { short think_positive = 1; int result=0;

    if (a < 0) {
	a=NEGATE(a);
	think_positive=NEGATE(think_positive);
}

if (b < 0) {
	b=NEGATE(b);
	think_positive=NEGATE(think_positive);
}

// do it the russian way:
while (a > 0) {
	if (a & 1) {
		result+=b;
	}
	a >>= 1;
	b <<= 1;
}

// think positive!
if (think_positive == -1)
	result = NEGATE(result);
return result;

    }

  • Stefan (unregistered) in reply to Osno
    Osno:
    All the people looping on 1 instead of 0 fail. All the people using multiplication and division instead of shifting (except in languages where there is no shifting) also fail.

    java.math.abs(int x)

    public static int abs(int a) 
    Returns the absolute value of an int value. If the argument is not negative, the argument is returned. If the argument is negative, the negation of the argument is returned.

<b>Note that if the argument is equal to the value of Integer.MIN_VALUE, the most negative representable int value, the result is that same value, which is negative.</b>

Parameters:
    a - the argument whose absolute value is to be determined 
Returns:
    the absolute value of the argument.
See Also:
    Integer.MIN_VALUE

    if you use shifting operators, russion(Integer.MIN_VALUE, ...) will always end in an infinity loop if your loop condition depends on a value != 0

  • little3lue (unregistered)

    Damn: someone beat me to a C++ metaprogramming solution. This is easier to read:

    template <long a, long b> struct RusMult { enum { value = ((a&1) ? b : 0 ) + RusMult<(a>>1),(b<<1)>::value }; };

    template <long b> struct RusMult<0,b> { enum { value = 0 }; };

    // Usage: result = RusMult< a, b >::value;

  • Eutactic (unregistered)

    Python 3.x Why else would they support unicode? Translation is probably hilariously wrong.

    #Русский крестьянин умножения модуль

    def Умножение(X,Y): пар = []

    def Населять(X,Y):
    пар = []
    while X > 0:
        пар.append([X,Y])
        X = X//2
        Y = Y*2
    return Суммавсех(Ликвидировать(пар))

def Ликвидировать(пар):
    пар = [Элемент for Элемент in пар if Элемент[0] %2 != 0]
    return пар

def Суммавсех(пар):
    Сумма = 0
    for Элемент in пар:
        Сумма += Элемент[1]
    return Сумма

пар = Населять(X, Y)
return пар

    print(Умножение(18, 23))

    414

  • RECURSIVEMAN (unregistered)

    RECURSIVE MAN SAYS:

    def _mult(a,b): if a == 1: return [(a,b)] return [(a,b)]+_mult(a/2,b*2) def mult(a,b): return sum(b for (a,b) in _mult(a,b) if a%2==1)

    I was trying to stick exactly to the algorithm. The intermediate list of numbers that you'd write down on paper is first produced by _mult. The list comprehension then crosses out which ones are unnecessary, and adds the rest.

  • rob tracey (unregistered)

    python:

    def rus(a,b): c = 0 while a > 0: a = a/2 b = b*2 if a % 2 != 0: c += b print 'total = ',c

  • (cs) 
    def russian_peasant(n1, n2):
    remainder = 0
    if n1 > n2: n1, n2 = n2, n1
    while n1 != 1:
        if n1 % 2:
            remainder += n2 
        n1 >>= 1
        n2 <<= 1

    return n2 + remainder
  • Philipp (unregistered)

    Small improvement; now it really works with negative numbers...

    public class SmallTest { public static void main(String [] args) { try { boolean n = args[0].trim().startsWith("-") ^ args[1].trim().startsWith("-"); int m1 = Math.abs(Integer.parseInt(args[0])); int m2 = Math.abs(Integer.parseInt(args[1])); if (m1 > m2) {int temp = m1; m1 = m2; m2 = temp;} int result = 0; while (m1 >= 1) { if ((m1 & 1) > 0) result += m2; m1 >>= 1; m2 <<= 1; } System.out.println(args[0] + " * " + args[1] + " == " + ((n && result != 0) ? "-" : "") + result); } catch (Exception e) { System.err.println("Whoops: " + e.getMessage()); } } }

  • JaguarOne (unregistered)

    Not very esoteric.... LOLCODE

    HAI CAN HAS STDIO?

    HOW DUZ I MULTIPLY_STALIN YR SOVIETA AN YR SOVIETB
	I HAS A PROFIT
	PROFIT R TROOF
	I HAS A THROWFUD
	THROWFUD R 0
		
	IM IN YR USSR_LOOP WILE PROFIT AN SOVIETA BIGGR 0
		IZ MOD OF SOVIETA AN 2 NOT 0?
		YARLY
			THROWFUD R SUM THROWFUD N SOVIETB
		
		KTHX
		
		SOVIETA R QUOSHUNT SOVIETA AN 2
		SOVIETB R PRODUKT SOCIETB AN 2
	IM OUTTA YR USSR_LOOP
IF U SAY SO

    KTHXBYE

    (captcha vulputate? sounds nasty!)

  • Andrew Brehm (unregistered)

    "It is said that Russian peasants multiply using a most curious method"

    Is that why there are so many of them?

  • Fabio Lima (unregistered)

    Minimalist C#

    static int RussianMultiply(int a, int b) { int r=0; for (int i=a/2;i!=1;i--,a=a/2,b=b*2,r=r+(a%2)*b){} return r; }

  • povman (unregistered)

    Here's my very realistic solution, in C:

    /* Oh god, who wrote this? - geoff */
int RussianMultiply(int a, int b)
{
   return a * b; /* TODO: Implement russian peasant multiplication */
}
  • GWO (unregistered)

    unsigned long long mult(unsigned long a, unsigned b) { unsigned long long acc = 0; while(a != 0) acc += (a%2)b,a/=2,b=2; return acc; }

  • drBeat (unregistered) in reply to ath

    This never terminates if x == 0.

    My try:

    def russian_multiply(a, b):
    product = 0
    while a:
        if a & 1:
            product += b
        a >>= 1
        b <<= 1
    return product
  • exo (unregistered)

    a very horribly ruby one-liner:

    def mul(a, b) (t=[[a, b]]).inject(0){|acc,(a, b)|a<=0?acc:acc+(t<<[a>>1,b<<1])[-2][1]*(a%2==1?1:0)} end

  • (cs) in reply to Paula
    Paula:
    public class Paula extends WTF { public static string Paulabean = "brillant!"; }

    Best solution by far

  • Benjamin Bridges (unregistered)

    Don't see anyone doing this for the adding portion: sum += b * (a & 1);

    Save an if statement.

  • avl (unregistered)

    uint32 rpMultiply(uint32 a, uint32 b) { uint32 res = 0;

    if (b < a) { // change for shorten time a = a ^ b; b = a ^ b; a = a ^ b; }

    do { if (a & 1) { res += b; a >>= 1; b <<= 1; } while (a); } return res; }

  • (cs) in reply to Dascandy
    Dascandy:
    X86: 
    ; assumption: eax contains arg1, ebx contains arg2
mov edx, eax
next:
shr ebx, 1
cmovc ecx, edx
cmovnc ecx, 0
jz end
lea eax, [eax*2 + ecx]
jmp next

    end:
ret

    ARM:

    	mov r2, r0
next    test r1, 1
	mov r1, #0, r1 shr 1
	addc r0, r0, r2
	movz pc, lr
	add r0, r0, r0
	b next

    Both approximated. Appreciate comments.

    awesome! more assembly required...

    In IA64 assembly:

    .text
.align 32
.global russian_multiply
.proc russian_multiply
russian_multiply::
	alloc	r14=ar.pfs,2,0,0,0
	mov	r2=pr
	movl	r8=0;;
startloop:
	tbit.nz	p6=r32,1
	cmp.e	p7=1,r32;;
(p6)	add	r8=r8,r33;;
(p7)	br.cond	endloop;;
	shr	r32=r32, 1
	shl	r33=r33, 1;;
	br.cond	startloop;;
endloop:
	mov	pr=r2
	mov	ar.pfs=r14;;
	br.ret.sptk	b0;;
.endp russian_multiply

    Usable in C as: int russian_multiply(int num1, int num2);

    Addendum (2009-07-22 10:26): cmp.eq not cmp.e. brainfart...

  • ross (unregistered)

    Python. Recursive, works with positive integers.

    def mul(a,b): if a != 1: if a % 2 == 1: return b + mul(a >> 1, b << 1) else: return mul(a >> 1, b << 1) else: return b

  • FatherStorm (unregistered) 
    <?php
		$x=rand(1,65535);
		$y=rand(1,65535);
		$ans=$x*$y;
		while($x>=1){
			if($x % 2==1 ){
				$z+=$y;
			}
			$x=intval($x/2);
			$y=$y*2;
		}
		echo"$ans == $z";;
?>
  • Phil (unregistered) in reply to Bob
    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.

    You're doing it wrong. In the first example you forgot to add the 76 on the first row.

  • threecheese (unregistered) in reply to Me
    Me:
    I was concerned my entry was too long and too legible. So I've shaved 11 bytes off it :)

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

    if you wanted illegible, you should assume no strict (drop the 'my $t') and use indexes of @ instead of assigning $a and $b to it...

Leave a comment on “Russian Peasant Multiplication”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article