• AdamK (unregistered)

    Nice one for a golf challenge.

  • Chris Hunt (unregistered)

    Recursive approach using ORACLE PL/SQL:

    CREATE OR REPLACE FUNCTION russian_mult (pleft IN NUMBER,
                                             pright IN NUMBER)
    RETURN NUMBER IS
       newleft NUMBER;
    BEGIN
       -- Sanity checking: pleft has to be an integer
       IF pleft != TRUNC(pleft) THEN
          RAISE VALUE_ERROR;
       END IF;
    
       newleft := TRUNC(pleft/2);
    
       -- tests for 0 and negative numbers added for completeness
       IF pleft < 0 THEN
          RETURN - russian_mult(-pleft,pright);
       ELSIF pleft = 0 THEN
          RETURN 0;
       -- the main bit starts here!
       ELSIF pleft = 1 THEN
          RETURN pright;
       ELSIF pleft/2 = newleft THEN  -- even number
          RETURN russian_mult(newleft,pright*2);
       ELSE -- odd number
          RETURN russian_mult(newleft,pright*2) + pright;
       END IF;      
    END;
    /
    SQL> SELECT russian_mult(18,23) FROM dual
    
    RUSSIAN_MULT(18,23)
    -------------------
                    414
    
  • Azeroth (unregistered)

    You and your prmature optimizations! I made my code follow the instructions (in Pascal implementation of SCAR)

    program PhilBewig;
    
    type
      TNumberLine = record
        LeftColumn: Integer;
        RightColumn: Integer;
        CrossedOut: Boolean;
      end;
    
      TNumberLineSheet = array of TNumberLine;
    
    function MultiplyNumbers(a, b: Integer): Integer;
    var
      Sheet: TNumberLineSheet;
      i: Integer;
    begin
      //They start by writing the two numbers to be multiplied at the head of two columns
      i:= 0;
      SetArrayLength(Sheet, i + 1);
      Sheet[i].CrossedOut:= False;
      Sheet[i].LeftColumn:= a;
      Sheet[i].RightColumn:= b;
    
      //Then they repeatedly .. until the number in the left column is one
      while(Sheet[i].LeftColumn > 1)do
      begin
        //writing the two new numbers immediately below their predecessors
        i:= i + 1;
        SetArrayLength(Sheet, i + 1);
        Sheet[i].CrossedOut:= False;
        //divide the number in the left column by two (dropping any remainder)
        Sheet[i].LeftColumn:= Sheet[i - 1].LeftColumn div 2;
        //double the number in the right column
        Sheet[i].RightColumn:= Sheet[i - 1].RightColumn * 2;
      end;
      
      //Then they cross out all rows where the number in the left column is even
      for i:= 0 to GetArrayLength(Sheet) - 1 do
      begin
        if(Sheet[i].LeftColumn mod 2 = 0)then
          Sheet[i].CrossedOut:= True;
      end;
      
      //and add the remaining numbers in the right column, which is the desired product
      Result:= 0;
      for i:= 0 to GetArrayLength(Sheet) - 1 do
      begin
        if(not Sheet[i].CrossedOut)then
          Result:= Result + Sheet[i].RightColumn;
      end;
    end;
    
    begin
      Writeln(IntToStr(MultiplyNumbers(18, 23)));
    end.
    
  • freako (unregistered)

    What, no Haskell? Oh you sorry bunch of infidels...

    mlt :: Int -> Int -> Int mlt 1 y = y mlt x y = (if x mod 2 == 0 then 0 else y) + mlt (x div 2) (y * 2)

  • Dave Ingram (unregistered)

    Haskell:

    peasant :: Int -> Int -> Int
    peasant x y = sum (map (\(_, z) -> z) (filter (\(x, _) -> mod x 2 == 1) (peasantnums x y)))
      where peasantnums 1 b = [ (1, b) ]
            peasantnums a b = (a, b) : peasantnums (div a 2) (b*2)
  • Bonce (unregistered)

    A few people have missed a bug in their code when the first value equals 1.

  • Russian Peasant (unregistered)

    Bah. Looks like me hearing of this method for the first time. In Soviet Russia we just multiply it by electronic calculators. Or by abacus. Or by slide rule. Whatever appropriate.

  • RayS (cs)

    Quick and dirty (just how I like it!) and hopefully stays true to the manual working process, not being naughty and skipping a few steps. When run in a suitable VBA host (e.g. Excel) will even show the working table.

    Public Function RussianMultiply(x As Long, y As Long) As Long
        Dim vals() As Long
        ReDim vals(1 To Round(Sqr(x), 0) + 1, 1 To 2) As Long
        Dim i As Long, j As Long, c As Long, Msg As String
        i = 1
        Do Until x = 0
            vals(i, 1) = x
            vals(i, 2) = y
            i = i + 1
            x = x \ 2
            y = y * 2
        Loop
        For j = 1 To i - 1
            If vals(j, 1) / 2 = vals(j, 1) \ 2 Then
                Msg = " X"
            Else
                c = c + vals(j, 2)
                Msg = vals(j, 2)
            End If
            Debug.Print vals(j, 1) & vbTab & vals(j, 2) & vbTab & Msg
        Next
        Debug.Print vbCrLf & "=" & vbTab & c
        RussianMultiply = c
    End Function

    Sample output:

    >RussianMultiply 18,23
    18  23   X
    9   46  46
    4   92   X
    2   184  X
    1   368 368
    
    =   414

    Addendum (2009-07-22 09:26): Oops, posted the +ve numbers only version. Replace Sqr(x) with Sqr(Abs(x))), add a new long s, where s = Sgn(x) * Sgn(y), and amend the output as required

  • Damien (unregistered)

    C# (I normally do VB, but wanted simple iterator support):

    	static void Main(string[] args)
    	{
    		Int32 total = 0;
    		foreach (NumPair p in GetColumns(Int32.Parse(args[0]), Int32.Parse(args[1])))
    		{
    			if (p.First % 2 == 1)
    			{
    				total = total + p.Second;
    			}
    		}
    		Console.WriteLine(total);
    		Console.ReadLine();
    	}
    
    	private struct NumPair
    	{
    		public Int32 First;
    		public Int32 Second;
    	}
    
    	private static IEnumerable<NumPair> GetColumns(Int32 Num1, Int32 Num2)
    	{
    		NumPair current = new NumPair();
    		current.First = Num1;
    		current.Second = Num2;
    		while (current.First > 0)
    		{
    			yield return current;
    			current.Second = current.Second * 2;
    			current.First = Convert.ToInt32(Math.Floor(current.First / 2.0));
    		}
    		yield break;
    	}
    
  • Drew (unregistered)

    Java. Untested and recursive.

    public void int multiply(int x, int y) { if(x == 1) { return y; } else if(x%2 == 1) {
    return y + multiply(x/2, y2); } else { return multiply(x/2, y2); } }

  • Me (unregistered)
    Comment held for moderation.
  • Dave Ingram (unregistered) in reply to freako

    You got there a couple of minutes before me... and more concisely. In my defence, it has been about 5 years since I last wrote any Haskell... but I share your sentiment ;)

  • Anon (unregistered)

    TRWTF is the animated gif

  • lemon (unregistered)

    int russianPeasantMultiply(int a, int b) { // Russian peasant just optimized his code return a * b; }

  • epv (unregistered)
    Comment held for moderation.
  • KimmoS (unregistered)

    simple non-WTF C++ template version:

    template <typename T> T russian_multiply(T paula, T bean) { T brillant = 0; for(;;) { if( paula & 1 ) brillant += bean; paula /= 2; if( paula == 0 ) return brillant; bean *= 2; } }

    #include <iostream>

    int main() { long a, b; std::cin >> a >> b; std::cout << a << "*" << b << "=" << russian_multiply(a,b) << std::endl; }

  • KnoNoth (unregistered)

    //Not really important part :) #define and ,int #define lets int #define be = #define is = #define jack_is_alive (jack>1){ #define jack_is_not_even (jack%2) #define plus + #define divided / #define multiplied * #define begin_action { #define end_action }

    //The code itself lets multiple(lets jack and john) begin_action lets bill be 0; while jack_is_alive if jack_is_not_even bill is bill plus john; jack is jack divided 2; john is john multiplied 2; end_action return bill plus john; end_action

    //You can call function like that multiple(int num1, int num2). It's written in C of course

  • Jeff Kemp (unregistered)

    I've just learned Python so I just had to contribute... this version doesn't actually use the * or / operators, which I think defeats the purpose somewhat. Works with all integers, positive or negative.

    def rusky_mult (left, right):
        """multiply
        In Russia, peasants multiply You!
        """
        if left < 0 and right < 0:
            left, right = -left, -right
        # left must be positive
        elif left < 0:
            left, right = right, left
        product = 0
        while left >= 1:
            if left & 1:
                product = product + right
            left = left >> 1
            right = right << 1
        return product
  • freako (unregistered) in reply to Dave Ingram
    Dave Ingram:
    You got there a couple of minutes before me... and more concisely. In my defence, it has been about 5 years since I last wrote any Haskell... but I share your sentiment ;)

    Ah, but yours is truer to the spirit of the algorithm provided. Mind, I'm a mere dabbler in the high mysteries of Haskell.

  • Stefan (unregistered)

    Lua

    function russian(a, b)
    	local s = 0;	
    	if a < 0 then s = s + 1; end
    	if b < 0 then s = s + 1; end	
    	a, b = math.abs(a), math.abs(b);	
    	if b > a then a, b = b, a; end	
    	if s == 1 then b = -b; end
    	local r = 0;		
    	while(a > 0) do
    		if (a % 2) > 0 then r = r + b; end
    		a, b = math.floor(a / 2), b * 2;
    	end		
    	return r;
    end
    
  • arnemart (unregistered)

    New and improved recursive ruby version:

    class Fixnum
      def * num
        self == 1 ? num : (self/2) * (num+num) + (self%2 == 1 ? num : 0)
      end
    end
    
    puts 7 * 7
    

    <3 operator overloading

  • Dan (unregistered) in reply to Dan

    C# again, but without that stinky Math.Abs():

    public int PeasantMul(int i, int j) { int accum = 0;

    while (i != 0) { accum += ((i >> 31) | 1) * ((0 - (i & 1)) & j); i /= 2; j *= 2; }

    return accum; }

  • db2 (cs)

    In UserRPL, as I've got my HP 48 handy, and I'm in the mood for the unconventional approach.

    << 0 3 ROLLD WHILE OVER 0 > REPEAT IF OVER 2 MOD THEN ROT OVER + 3 ROLLD END 2 * SWAP 2 / FLOOR SWAP END DROP2 >>

  • Clark S (unregistered) in reply to The Wolf
    The Wolf:
    And in PHP:
    <?php
    <pre>function russian($x, $y) {
    	$left = array();
    	$right = array();
    	
    	while ($x > 1) {
    		$left[] = $x;
    		$right[] = $y;
    		
    		$x = floor($x / 2);
    		$y *= 2;
    	}
    	
    	$left[] = $x;
    	$right[] = $y;
    	$result = 0;
    	
    	foreach ($left as $index => $x) if ($x % 2) {
    		$result += $right[$index];
    	}
    	
    	return $result;
    }
    
    echo russian(41238, 193625);
    

    ?>

    I'll see that and raise you:
    <?php
    function russkiply($a, $b) {
    $product = 0;
    while ($a >= 1) {
    if ($a % 2)
    $product += $b;
    $a = floor((float)$a /= 2);
    $b *= 2;
    }
    return $product;
    }

  • arnemart (unregistered) in reply to KimmoS
    KimmoS:
    simple non-WTF C++ template version

    Oxymoron!

  • malach (unregistered)

    In Delphi:

    function RussianPeasantMultiply(a,b: Integer); begin result := 0; while a>0 do begin if (a AND 1) = 1 then result := result + b; a := a div 2; b := b * 2; end; end;

  • newlisp.org (unregistered)

    in newLISP:

    (define (rmul x y , s)
      (until (= x 1)
        (unless (zero? (% x 2))
          (inc s y))
        (setq x (>> x) y (<< y)))
      (+ y s)
    )
    
  • Dave Ingram (unregistered)

    Since I got beaten to the punch with the Haskell version, here's one for vimscript:

    :fun Peasant(n1, n2)
    :  if a:n1 == 1
    :    retu a:n2
    :  elsei a:n1 % 2 == 1
    :    retu a:n2 + Peasant(float2nr(a:n1/2), a:n2*2)
    :  el
    :    retu Peasant(float2nr(a:n1/2), a:n2*2)
    :  en
    :endf

    To use: save to ~/peasant.vim, :source ~/peasant.vim, then

    i<C-R>=Peasant(42,71)<CR>
    will insert the result of 42 × 71. Maybe if I have some time later, I'll make it print out the workings too ;)

  • Ryan (unregistered)
    Comment held for moderation.
  • pjt33 (cs) in reply to Herman
    Herman:
    As this is the exact implementation of the multiply function on binary computing hardware, a simple
    int Mult(int a, int b)
    {
      return a * b;
    }

    should do for most platforms :)

    That's what I was going to say, so since you beat me to it here's a more long-winded implementation in SML:

    fun mult_inner(x, y, accum) = if (x = 0) then accum else if (x mod 2 = 1) then mult_inner(x div 2, y * 2, accum + y) else mult_inner(x div 2, y * 2, accum); fun mult(x, y) = mult_inner(x, y, 0);

    I think this is the first recursive implementation in the comments to be truly tail-recursive (and hence use a fixed amount of memory with a non-braindead compiler).

  • Whatever (unregistered) in reply to Drew
    Java. Untested and recursive.

    Every good WTF starts with these words.

  • Bob (unregistered)

    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.

  • Felix Ungman (unregistered)

    C#, with yield return, of course!

    static class Program
    {
    	public static bool IsOdd(this int value) { return (value % 2) != 0; }
    
    	public static IEnumerable<KeyValuePair<int, int>> RussianPeasantSequence(int a, int b)
    	{
    		while (a > 0)
    		{
    			yield return new KeyValuePair<int, int>(a, b);
    			a /= 2;
    			b *= 2;
    		}
    	}
    
    	[STAThread]
    	static void Main()
    	{
    		System.Diagnostics.Debug.WriteLine(
    			RussianPeasantSequence(18, 23)
    			.Where(x => x.Key.IsOdd())
    			.Select(x => x.Value)
    			.Sum());
    	}
    }
    
  • baka0815 (unregistered)

    Well, here is a version in Pascal.

    function RussianMultiply(Left, Right: Integer): Integer;
    begin
      if (Left = 1) then
      begin
        Result := Right;
        Exit;
      end;
    
      Result := 0;
      while Left <> 1 do
      begin
        Left := Left div 2;
        Right := Right * 2;
    
        if ((Left mod 2) <> 0) then Inc(Result, Right);
      end;
    end;

    Anyone noticed this only works if the left number is even?!

    1823 works fine (414), bit 2318 would be 396.

  • phihag (cs)

    code golf: Python 3, 1 statement, 1 line, 70 characters:

    m=lambda a,b:sum(b<
    
  • Sebastian Paaske Tørholm (unregistered)

    Oh hey, I did this in my first algorithms class lecture a while back.

    Haskell:

    import Data.Bits (shiftL, shiftR)
    
    x :: Integer -> Integer -> Integer
    1 `x` b             = b
    a `x` b | a > b     = b `x` a
            | otherwise = (if a `mod` 2 == 0 then 0 else b) +
                          ((a `shiftR` 1) `x` (b `shiftL` 1))
  • MP (unregistered)

    LISP

    ((defun russianpeasant ("They start by writing the two numbers to be multiplied at the head of two columns.) (Then they repeatedly divide the number in the left column by (two ) (dropping any remainder) and ((double) the number in the right column), writing the (two new numbers) immediately below their predecessors, until the number in the left column is one.) ((Then they) (cross out all rows) where the number in the left column is even), and (((add the remaining numbers) in the right column), which is the desired product)). (For instance, the product eighteen times twenty-three is found like this.")))))

  • Clark S (unregistered) in reply to Clark S
    Clark S:
    I'll see that and raise you:
    <?php
    function russkiply($a, $b) {
        $product = 0;
    	while ($a >= 1) {
            if ($a % 2)
                $product += $b;
            $a = floor((float)$a /= 2);
            $b *= 2;
        }
        return $product;
    }
    Actually, I just realized that my function doesn't take into account negatives. In order to be functionally complete I must do this:
    <?php
    function russkiply($a, $b) {
        $product = 0;
        if ($a < 0) {
            $a = -$a;
            $b = -$b;
        }
        while ($a >= 1) {
            if ($a % 2)
                $product += $b;
            $a = floor((float)$a /= 2);
            $b *= 2;
        }
        return $product;
    }
    The new check at the beginning will reverse the signs if the first part is less than 0; That way, if just $a is negative, it switches $b to the negative, and if both are negative, they both switch to positive.

    CAPTCHA: appellatio -- sounds like a dirty fruit fetish

  • whileloopsareugly (unregistered)

    int mul(unsigned a, unsigned b) { for (int s=0; a; a>>=1, b<<=1) s+=a&0x1?b:0; return s; }

  • Jeff Kemp (unregistered) in reply to Bob
    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.

  • Tempura (unregistered)

    Simple and readable recursive python-function:

    In [23]: def russia_peasants(x, y):
       ....:     x, y = float(x), float(y)
       ....:     if x <= 1:
       ....:         return 0
       ....:     elif (x%2) == 1:
       ....:         return (x*y) + russia_peasants(x/2, y*2)
       ....:     else:
       ....:         return russia_peasants(x/2, y*2)
    
    In [24]: russia_peasants(18, 23)
    Out[24]: 414.0
    
  • TerraNova (unregistered)
    #define F(name, op)\
    	int name(int num) {\
    		int i, j = 0;\
    		for (i = 0; i < 32; ++i) {\
    			op;\
    		}\
    		return j;\
    	}
    
    #define _BUFFER_SIZE 16
    long b[_BUFFER_SIZE]; // long to avoid integer overflow
    
    F(explode, j = 1; i[b] = num & j << i; i[b] >>= i)
    F(implode, i[b] *= num << i)
    F(deplode, j+= i[b])
    
    #include <stdio.h>
    
    void main(int argc, char *argv[]) {
    	if (argc != 3) return 1; // TODO: Display help text
    	
    	int i;
    
    	printf("%d\n", (explode(atoi(argv[1])), implode(atoi(argv[2])), deplode(0)));
    }
    

    "Features":

    • Uses the , operator
    • buffer overflow (which passes valgrind!)
    • The ever-popular TODO - commenting on the one piece of verification code
    • Macros
    • arrays-as-pointer - need i say more?
    • Does not implement the actual algorithm, just something deceptively similar to what the requirements talk about
    • Violates the language standard for no good reason
  • baka0815 (unregistered)

    Ok, screw that about the left number needing to be even. Just forgot to use that one, too.

    Well, guess it goes with my name. ;)

    function RussianMultiply(Left, Right: Integer): Integer;
    begin
      if (Left = 1) then
      begin
        Result := Right;
        Exit;
      end;
    
      Result := 0;
    
      // Check if the first one is odd and add it  
      if ((Left mod 2) <> 0) then Inc(Result, Right);
    
      while Left <> 1 do
      begin
    
        Left := Left div 2;
        Right := Right * 2;
        if ((Left mod 2) <> 0) then Inc(Result, Right);
      end;
    end;
  • HypocriteWorld (cs) in reply to Dave Ingram

    Better Haskell version: (this one pretty much follows the algorithm given part by part).

    peasant :: Integer -> Integer -> Integer
    peasant = curry (sum . map snd . filter (odd . fst) . unfoldr gen)
      where gen (0, _) = Nothing
            gen (x, y) = ((x, y), (x `div` 2, y * 2))
    

    Sometimes the unfoldr function feels silly.

    And to satisfy your craze for testing:

    import Test.QuickCheck
    prop_peasant x y = (x > 0 && y > 0) ==> peasant x y == x * y
    
  • Arjan (unregistered)

    Recursive Java version. Also works with negative and zero.

    public class Russian {
    public static long multiply(long a,long b){long r=multiply(a>0?a:-a,b>0?b:-b,0);return a<0^b<0?-r:r;}
    private static long multiply(long a,long b,long r){if(a%2==1)r+=b; return a<=1?r:multiply(a>>1,b<<1,r);}
    }
    
  • Stalin (unregistered)
    def inSovietRussiaIntegerMultipliesYou(
        a: "foul capitalist pig",
        b: "patriotic worker comrade"
        ) -> "glorious empowerment of the proletariat for the motherland":
        assert isinstance(a, int) and a > -1 and\
               isinstance(b, int) and b > -1
        al = [a]
        bl = [b]
        while 1 not in al:
            al.append(al[-1]//2)
            bl.append(bl[-1]*2)
        return sum(b for a, b in zip(al, bl) if a%2)

    Only works under Python 3.x

  • leppie (unregistered)

    #!r6rs ;Scheme (for Phil :)

    (define (russian* x y) (cond [(zero? x) 0] [else (let-values (((d m) (div-and-mod x 2))) (+ (if (zero? m) 0 y) (russian* d (bitwise-arithmetic-shift-left y 1))))]))

  • Zishan (unregistered)
    function ruM (input) {
     var left=0,right=0,remainder=0,sum=0,num;
     input = input.replace(/\s+/g, '').replace(/x/g,'*');
      if (input.indexOf('*')) num = input.split('*');
      if (num) for (var i=1; i<num.length; i++) {
       left = (i==1 ? parseInt(num[i-1], 10) : sum);
    	right = parseInt(num[i], 10);
       while (left>1) {
          if (left % 2 != 0) {
             remainder += right;
             left -= 1;
          }	
          left /= 2;
          right *= 2;
       }
    	sum = right + remainder;
    	remainder = 0;
      }
     return sum;
    }
    
    String input:
    ruM("18 x 23 x 23 x 23");
    
  • douglas (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
    
    You're doing it wrong. The correct peasant algorithm here is:
    45   x  76	76
    22	152	0
    11	304	304
    5	608	608
    2	1216	0
    1	2432	2432
    ======================
    		3420
    

    Note the first line in particular.

  • Steven de B (cs)

    Perl, with some nice recursion...

    Code:
    sub mul($$) { my($a,$b)=@_; return $a?(($a&1?$b:0)+mul(int($a/2),$b*2)):0; }
    Probably already mentioned before in some variations, but I just want to have such a cool WTF-sticker :-)

Leave a comment on “Russian Peasant Multiplication”

Log In or post as a guest

Replying to comment #:

« Return to Article