• (cs)

    in C# public int RussianMultiply(int operand1, int operand2) { int res = 0; while (operand1 > 0) { if (operand1 % 2 == 1) res += operand2; operand1 /= 2; operand2 *= 2; } return res; }

  • Dmitri Savichev (unregistered)

    Yet another Scheme solution

    ;;proper R5RS (define (rusmult a b) (cond ;;special cases ((= a 0) 0);; okay, it's dirty, but i'm way to lasy ((= b 0) 0);; to try to come up with something better ((negative? a) (* -1 (rusmult (* -1 a) b))) (else (if (= a 1) ;; real computation (+ (if (odd? a) b 0)) (+ (if (odd? a) b 0) (rusmult (if (even? a) (/ a 2) (/ (- a 1) 2)) (* b 2)))))))

  • (cs)

    Recursive in C# public int RecursiveRussianMultiply(int operand1, int operand2) { return operand1 == 0 ? 0 : RecursiveRussianMultiply(operand1 / 2, operand2 * 2) + (operand1 % 2 == 1 ? operand2 : 0); }

  • Sean Handley (unregistered)

    C# solution (boilerplate not included)

    private static List<Pair> _pairs = new List<Pair>();

private static void RussianPeasant(int a, int b)
{
    _pairs.Add(new Pair(a, b));
    if (a == 1)
    {
        int result = 0;
        foreach (Pair pair in _pairs)
        {
            if (pair.FirstNum % 2 != 0)
            result += pair.SecondNum; //accumulate all second nums, if first num in pair is an odd number
        }
        DisplayMessage("Result: " + result.ToString());
    }
    else
    {
        //tail recursive call
        RussianPeasant(a / 2, b * 2); //half first number (ignoring remainder), double second number
    }
}
  • lyml (unregistered)

    Scheme

    (define (mult a b) (cond ((= b 1) a) ((= (remainder b 2) 1) (+ b (mult (* 2 a) (quotient b 2)))) (else (mult (* 2 a) (/ b 2)))))

    not tested CAPTHA: vereor

  • Osno (unregistered)

    Recursive C# in one line :)

    private static long m(long f, long s) { return ((f&1)==1?s:0)+(f>0?m(f>>1,s<<1):0); }

    Ok, it's just like the perl sample. Here, how it should be read:

    private static long m(long f, long s) { return ((f&1)==1?s:0)+(f>0?m(f>>1,s<<1):0);
    }

    And for the whole "I can do it in a few chars" thing, from the return to the colon it's only 43 characters.

  • Someone (unregistered)

    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.
  • Dmitri Savichev (unregistered) in reply to Dmitri Savichev

    ugh, i meant it that way

    ;;proper R5RS
(define (rusmult a b)
  (cond ;;special cases
    ((= a 0) 0);; okay, it's dirty, but i'm way to lasy
    ((= b 0) 0);; to try to come up with something better
    ((negative? a) (* -1 (rusmult (* -1 a) b)))
    (else (if (= a 1) ;; real computation
              (+ (if (odd? a) b 0))
              (+ (if (odd? a) b 0)
                 (rusmult (if (even? a) (/ a 2) (/ (- a 1) 2)) (* b 2)))))))
  • (cs)

    This is going to get lost in the mix, but here's my take.

    Note: I'm betting that most of the naive implementations people have done don't function correctly when multiplying negative numbers. This one does.

    using System;
using System.Data;
using System.Diagnostics;

using o = System.Console;

// to compile on any modern Windows machine:
// 
// PATH=%PATH%;C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727
// csc rusmult.cs

class X {

  public static void Main(string[] args) {
     try {
      if (args.Length != 2) {
        o.WriteLine("Usage: {0} n1 n2", Environment.GetCommandLineArgs()[0]);
        return;
      }
      
      // doing this makes negative numbers work
      uint n1 = (uint)Convert.ToInt32(args[0]);
      uint n2 = (uint)Convert.ToInt32(args[1]);

      // ensure n1 < n2 to minimize steps
      if (n1 > n2) { n1 ^= n2; n2 ^= n1; n1 ^= n2; }
      
      int dig1 = (n1==0) ? 1 : (int) Math.Ceiling(Math.Log10(n1));
      int dig2 = (n2==0) ? 1 : (int) Math.Ceiling(Math.Log10(n2));
      int dig3 = dig1 + dig2;
      
      string fmt1 = string.Format("{{0,{0}}} x {{1,{1}}} ", dig1, dig3);
      string fmt2 = string.Format(" | + {{0,{0}}}", dig3);
      string fmt3 = string.Format("{{0,{0}}} x {{1,{1}}}  =    {{2}}", dig1, dig3);
      
      uint accum = 0;
      while (n1 > 0) {
        o.Write(fmt1, n1, n2);
        if ( (n1 & 1) != 0) { 
          o.Write(fmt2, n2);
          accum += n2; 
        }  else {
          o.Write(" | strike");
        }
        o.WriteLine();
        n1 >>= 1;
        n2 <<= 1;
      }
      o.WriteLine(new string('-', dig1 + 3 + dig3 + 5 + dig3));
      o.WriteLine(fmt3, args[0], args[1], (int)accum); 
      
     } catch (Exception ex) {
       o.WriteLine("Error: {0}", ex);
     }
  }
}
  • Slinky (unregistered) 
    Function PeasantMultiply(x As Integer, y As Integer) As Integer
  Dim product As Integer = 0

  While x >= 1
    If x Mod 2 == 1 Then
      product += y;
    End If
  
    x /= 2
    y *= 2
  End If

  Return product
End Function
  • _flt (unregistered)

    Some considerations for speed optimisation:

    • Division, multiplication and modulo are quite complex and will take longer than standard bit operations on most CPUs.
    • Have the smaller value be decremented will save cycles
    unsigned int rmul( unsigned int a, unsigned int b )
{
  if ( a > b ) rmul( b, a );
  
  unsigned int acc = (a & 1) ? b : 0;

  for ( ; a >>= 1 ; b <<= 1 ) {
    if ( a & 1 ) acc += b;
  }
  return acc;
}
  • Remy (unregistered)

    Here's mine, in Python. It works for all integers.

    def russian(a, b):
	if a < 0:
		a, b = -a, -b
	c = 0
	while 1:
		if a & 1:
			c += b
		a >>= 1
		b <<= 1
		if a <= 0:
			break
	return c
  • Mestafais (unregistered)

    Mine on javascript function peasentDevide(a, b){r=0;while(a!=0){if (a%2==1)r+=b;a=Math.floor(a/2);b=b*2;}return r;}

  • Rief (unregistered)

    Wrote in D language :P but the mult function should work also in C++, I think...well, with unsigned int instead of uint :P:

    import std.stdio; import std.string;

    int mult(uint fst, uint snd) { uint result;

    for(uint i=0; fst >= 1; fst/=2, snd*=2, i+=1)
	if(fst % 2)
	{
		result += snd; 
		fst -= 1;
	}

return result;

    }

    void main(string[] args) { if(args.length != 3) { writefln("Usage: %s <num> <num>", args[0]); return 0; } if(!args[1].isNumeric()) { writefln("First argument isn't a number"); return 0; } if(!args[2].isNumeric()) { writefln("Second argument isn't a number"); return 0; }

    writefln(mult(atoi(args[1]),atoi(args[2])));

return 0;

    }

    To run put it in a file and use the gdc compiler....

  • Billy (unregistered)

    In Python (Works with 0 and negative numbers!)

    def p_mult(num1, num2) : if num1 == 0 or num2 == 0 : return 0 sign = bool(num1 < 0) ^ bool(num2 < 0) num1 = abs(num1) num2 = abs(num2) dat = [[num1, num2]] while num1 != 1 : num1 /= 2 num2 *= 2 dat.append([num1, num2]) total = 0 for n in dat : if n[0] % 2 == 1 : total += n[1] if sign : return total * -1 else : return total

    http://www.codeskilled.com

  • Harleqin (unregistered)

    Common Lisp:

    (defun russkiply (a b &optional (sum 0))
  "returns the product of a and b,
   achieved by peasant multiplication."
  (cond ((or (zerop a) (zerop b)) 0)
        ((minusp a) (- (russkiply (- a) b)))
        ((minusp b) (- (russkiply a (- b))))
        ((= a 1) (+ b sum))
        (t (russkiply (floor (/ a 2))
                      (* b 2)
                      (+ sum (* b (logand a 1)))))))

    C:

    int russkiply (int a, int b)
  { if (a == 0 || b == 0) { return 0; };
    if (a < 0) { return - russkiply (- a, b); };
    if (b < 0) { return - russkiply (a, - b); };
    int p = 0;
    for (;
         p += (a & 1) * b, a != 1;
         a /= 2, b *= 2) {};
    return p; };
  • Will (unregistered)

    My solution in LUA:

    function f(x, y)
  return (x % 2 == 1 and y or 0) + (x > 0 and f(math.floor(x / 2), y * 2) or 0)
end
  • Anonymous (unregistered) in reply to SR
    SR:
    Anonymous:
    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.
    If you fancy a return to normal we could have a slanging match about earnt/earned ;o)
    I dropped that in there to test the waters (FYI it is proper English) but amazingly enough, nobody took the bait. Everyone's just happy to work on the coding problem. I'm aghast at just how civil developers can be when they've got something to develop!
  • bluebearr (unregistered)

    Windows XP batch file:

    @echo off
set _a=18
set _b=23
call :mult %_a% %_b% _result
echo %_a% x %_b% = %_result%
goto :EOF


:mult
::   Multiply two numbers
::   Parameters:
::    %1 - first number
::    %2 - second number
::    %3 - variable to return result in
  setlocal
  set _a=%1
  set _b=%2
  set _res=0
  :calc
    set _eventest=0
    for /L %%i in (0,2,8) do if %_a:~-1%==%%i set _eventest=1
    if %_eventest%==0 set /a _res+=_b
    if %_a% LEQ 1 goto endcalc
    set /a _a/=2
    set /a _b*=2
    goto calc
  :endcalc
  endlocal & set %3=%_res%
goto :EOF
  • (cs) in reply to Nick Pope
    Nick Pope:
    WarheadsSE:
    Did you check the output? ;)

    Aye, I did. And still seems to work fine... Are you having a problem with it?

    Forgive, i missed the automagic vivification of c to existance and 0

  • Josh Bohde (unregistered)

    Python 2.6

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

    51 characters

  • baka0815 (unregistered)

    Since everyone is bragging about shifting instead of multiply/divide, here is a Pascal version with shifting:

    function RussianMultiply(Left, Right: Integer): Integer;
begin
  if (Left = 1) then
  begin
    Result := Right;
    Exit;
  end;

  Result := 0;
  
  if ((Left mod 2) <> 0) then Inc(Result, Right);
  while Left <> 1 do
  begin

    Left := Left shr 1;
    Right := Right shl 1;
    if ((Left mod 2) <> 0) then Inc(Result, Right);
  end;
end;

    You could strip the

      if (Left = 1) then
  begin
    Result := Right;
    Exit;
  end;

    part, but it would be slower I guess.

  • Osno (unregistered)

    Shorter: return f>0?m(f>>1,s<<1)+(f&1)*s:0;

    Just realized that ( (a&1) == 1? s : 0 ) === ( (a&1)*s )

    34 chars without the function header.

  • Ian McLaird (unregistered) in reply to Alex Ciarlillo
    Alex Ciarlillo:
    recursive scala soln. 
      def do_mult(left : Int, right : Int) : Int = {
    if (left == 1) right
    else if (left%2 == 0) do_mult(left/2, right*2)
    else do_mult(left/2, right*2) + right
  }

    And, for even more fun, with a custom operator

    object praxis2 {
    implicit def RussianIntInt(i: Int):RussianInt = new RussianInt(i)
    implicit def IntRussianInt(i: RussianInt):Int = i.a

    class RussianInt(val a: Int) {
        def ***(b: RussianInt): RussianInt = {
            if (a < 2) if (a == 1) b else 0
            else if (a % 2 == 1) b + ((a / 2) *** (b * 2))
            else ((a / 2) *** (b * 2))
        }
    }

    def main(args: Array[String]) {
        val a = args(0).toInt
        val b = args(1).toInt
        val res: Int = a *** b
        println(res)
    }
}
  • Wulf0r (unregistered)

    Python:

    def russianMultiply(lst):
    """ param is a list with one entry of tupel containing the ints to multiply """
    # take head of list
    arg = lst[-1]
    # check if recursion is complete
    if arg[0] == 1:
        # pythons X-trem X-pressivnes -> filter all unevens and add them
        return reduce( lambda x,y: x+y, [x[1] for x in lst if x[0] % 2 != 0])

    lst.append( (arg[0] / 2, arg[1] * 2) )
return russianMultiply( lst)

    

    print russianMultiply( list([(18,23)]))
  • Xthlc (unregistered) in reply to Xthlc

    Final version of my ruby function, slightly altered with some cribbage from halber_mensch to handle all integers.

    def russian(a, b)
   return a*b if (-1..1).include? a
   (a & 0x1) * b + russian(a>>1, b<<1)
end
  • baka0815 (unregistered)

    Last one I submit, I promise! :)

    • shifting instead of multiply/divide
    • bit-and instead of modulo
    function RussianMultiply(Left, Right: Integer): Integer;
begin
  Result := 0;
  
  if ((Left and 1) = 1) then Inc(Result, Right);
  while Left <> 1 do
  begin
    Left  := Left shr 1;
    Right := Right shl 1;
    if ((Left and 1) = 1) then Inc(Result, Right);
  end;
end;
  • Steve the Cynic (unregistered) in reply to Captain Obvious
    Captain Obvious:
    I haven't done APL in a LONG time... 
         Z <- A RUSSIAN B
[1]  Z <- 0
[2] TOP:
[3]  Z <- Z + A * 0 = 2 | B
[4]  A <- |_ A (divide) 2
[5]  B <- B x 2
[6]  -> (A>0) / TOP

    Or

         RET <- A RUSSIAN B
[1] X <- 2 * (highminus)1 + (iota) (upside down L) 2 (star-in-circle) A + 1
[2] Y <- X x B
[3] Z <- 2 | |_ A / X
[4] RET <- +/ Y x Z

    X gets a list of powers of two starting with 1

    Y gets a list of B times powers of two

    Z gets a list of (A/power of two) mod 2 (0 or 1)

    RET gets the sum of the list of Y and Z elements multiplied together.

    4 lines, no loops, no recursion, and only one Greek letter!

    NOT TESTED. Written using a memory of APL not exercised in 25 years.

  • - (unregistered) 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 :)

    Well that one wins Best Abuse Of The Rules.:) I've only seen one C preprocessor nasty so far.... any more takers?

  • Ken B (unregistered) in reply to kastein
    kastein:
    Also, I'm disappointed... no MUMPS? no MS-DOS batch?
    You just didn't wait long enough. :-)

    Here is my MS-Windows Batch file:

    @echo off
rem Multiply.bat
rem Multiplication the "Russian Peasant" way.
rem To be called with two parameters -- the numbers to multiply.
rem For example:  multiply 18 23
rem
rem Note:  No sanity check is provided to verify two numbers are passed.
    

    set /a Multiplier=%1
set /a Multiplicand=%2
set /a Product=0
    

    :loop
    

    set /a OddOrEven=%Multiplicand% / 2
set /a OddOrEven=%OddOrEven% * 2
if not %OddOrEven%==%Multiplicand% set /a Product=%Product% + %Multiplier%
    

    set /a Multiplicand=%Multiplicand% / 2
set /a Multiplier=%Multiplier% * 2
    

    if not %Multiplicand%==0 goto loop
    

    echo %1 times %2 equals %Product%
    Now, how does one get code to single-space?

  • Lupe (unregistered) in reply to SR

    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)".

  • aBase (unregistered)

    The problem says two numbers, not two integers, so here's the first draft of a PHP solution that will handle decimal fractions (and also negative numbers):

    function potemkin_multiply($two_numbers)
{
$frac_len = array(0, 0);
foreach ($two_numbers as $num) {
if ($num == 0) {
return 0;
}
$num = rtrim($num, '.');
if ($len = strrchr($num, '.')) {
$frac_len[] = strlen(strrchr($num, '.')) - 1;
}
}
$power = max($frac_len);
$neg = false;
foreach ($two_numbers as & $num) {
if ($num < 0) {
$neg = !$neg;
}
$num = abs($num * pow(10, $power));
}
$total = 0;
while ($two_numbers[0] > 1) {
if ($two_numbers[0] % 2) {
$total += $two_numbers[1];
}
$two_numbers[0] = floor($two_numbers[0] / 2);
$two_numbers[1] *= 2;
}
$total = ($total + $two_numbers[1]) / pow(10, $power * 2);
if ($neg) {
$total *= -1;
}
return $total;
}
    Test code:
    $nums = array(0, -1, 1, 18, -23, 154., -229.5, 49.0, 389.99,
67.99999, -592.8729, .678, 0.00678);
for ($i = 0; $i < 50; $i++) {
$pair = array($nums[array_rand($nums)], $nums[array_rand($nums)]);
$russian = potemkin_multiply($pair);
$orthodox = $pair[0] * $pair[1];
echo $pair[0] . ' * ' . $pair[1] . ' = ' . $russian . '';
if ((string) $russian != (string) $orthodox) {
echo ' (' . $orthodox . ')';
}
echo '
    ';
}

  • Qwertyuiopas (unregistered)

    I know everybody wants it :)

    Hopefully none of it was removed.

    Also, everything after the first . is disabled debugging code. Remove the [-] to see what is left of the memory.

    ,>>,[->+>+<<]<<[[-[>+<-]>[>+>>>+<<<<-[[<+>-]>[-]<]]<]>>[>>[-]<<[-]]+>[->>>>>++>++<<<<<<]>>]>>>>[-]<<<<<<<[<<<<<]>>>>>[>>[->>>>>+<<<<<]>>>]>>.[-][<<<<<<<[<<<<<]>>>.>.>[.>.>.>.>.>].>.>.]

  • Markus Persson (unregistered)

    48 characters in javascript:

    function m(a,b){return a>1?a%2b+m(a>>1,b2):b;}

  • (cs) in reply to Jay
    Jay:
    public static int multiply(int first, int second){ if(first == 1){ return second; }

    int result = 0;

    if(first%2 != 0){ result += second; } result += multiply(first/2, second * 2); return result; }

    Didn't test it, but I think this will infinite loop if the first number is 0;

  • Ken B (unregistered) in reply to Steve the Cynic
    Steve the Cynic:
    Captain Obvious:
    I haven't done APL in a LONG time... 
    ...snip...

    Or

    ...snip...

    ...snip...

    NOT TESTED. Written using a memory of APL not exercised in 25 years.

    Noted. (Also, I am not familiar with using standard ASCII characters for APL, as I had a "real" APL character set to work with.) However, where's your single-line solution, as any "good" APL programmer knows is the target.
  • (cs)

    Efficient C solution:

    int russianMult( int a, int b ){

    return a*b;

    }

  • (cs)

    All of these solutions are soooooo slooooooooow. Try this one out. Just call the function you need! Ex: for 5 x 18, call "F5x18();". Note: Doesn't yet work for all values, but I'm working on it.

    static int F10x1() { return F5x2(); } static int F10x10() { return F5x20(); } static int F10x2() { return F5x4(); } static int F10x3() { return F5x6(); } static int F10x4() { return F5x8(); } static int F10x5() { return F5x10(); } static int F10x6() { return F5x12(); } static int F10x7() { return F5x14(); } static int F10x8() { return F5x16(); } static int F10x9() { return F5x18(); } static int F11x150() { return F5x300() + 150; } static int F1x1() { return 1; } static int F1x10() { return 10; } static int F1x12() { return 12; } static int F1x1200() { return 1200; } static int F1x14() { return 14; } static int F1x16() { return 16; } static int F1x18() { return 18; } static int F1x2() { return 2; } static int F1x20() { return 20; } static int F1x24() { return 24; } static int F1x28() { return 28; } static int F1x3() { return 3; } static int F1x32() { return 32; } static int F1x36() { return 36; } static int F1x4() { return 4; } static int F1x40() { return 40; } static int F1x48() { return 48; } static int F1x5() { return 5; } static int F1x56() { return 56; } static int F1x6() { return 6; } static int F1x64() { return 64; } static int F1x7() { return 7; } static int F1x72() { return 72; } static int F1x8() { return 8; } static int F1x80() { return 80; } static int F1x9() { return 9; } static int F23x75() { return F11x150() + 75; } static int F2x1() { return F1x2(); } static int F2x10() { return F1x20(); } static int F2x12() { return F1x24(); } static int F2x14() { return F1x28(); } static int F2x16() { return F1x32(); } static int F2x18() { return F1x36(); } static int F2x2() { return F1x4(); } static int F2x20() { return F1x40(); } static int F2x24() { return F1x48(); } static int F2x28() { return F1x56(); } static int F2x3() { return F1x6(); } static int F2x32() { return F1x64(); } static int F2x36() { return F1x72(); } static int F2x4() { return F1x8(); } static int F2x40() { return F1x80(); } static int F2x5() { return F1x10(); } static int F2x6() { return F1x12(); } static int F2x600() { return F1x1200(); } static int F2x7() { return F1x14(); } static int F2x8() { return F1x16(); } static int F2x9() { return F1x18(); } static int F3x1() { return F1x2() + 1; } static int F3x10() { return F1x20() + 10; } static int F3x12() { return F1x24() + 12; } static int F3x14() { return F1x28() + 14; } static int F3x16() { return F1x32() + 16; } static int F3x18() { return F1x36() + 18; } static int F3x2() { return F1x4() + 2; } static int F3x20() { return F1x40() + 20; } static int F3x3() { return F1x6() + 3; } static int F3x4() { return F1x8() + 4; } static int F3x5() { return F1x10() + 5; } static int F3x6() { return F1x12() + 6; } static int F3x7() { return F1x14() + 7; } static int F3x8() { return F1x16() + 8; } static int F3x9() { return F1x18() + 9; } static int F4x1() { return F2x2(); } static int F4x10() { return F2x20(); } static int F4x12() { return F2x24(); } static int F4x14() { return F2x28(); } static int F4x16() { return F2x32(); } static int F4x18() { return F2x36(); } static int F4x2() { return F2x4(); } static int F4x20() { return F2x40(); } static int F4x3() { return F2x6(); } static int F4x4() { return F2x8(); } static int F4x5() { return F2x10(); } static int F4x6() { return F2x12(); } static int F4x7() { return F2x14(); } static int F4x8() { return F2x16(); } static int F4x9() { return F2x18(); } static int F5x1() { return F2x2() + 1; } static int F5x10() { return F2x20() + 10; } static int F5x12() { return F2x24() + 12; } static int F5x14() { return F2x28() + 14; } static int F5x16() { return F2x32() + 16; } static int F5x18() { return F2x36() + 18; } static int F5x2() { return F2x4() + 2; } static int F5x20() { return F2x40() + 20; } static int F5x3() { return F2x6() + 3; } static int F5x300() { return F2x600() + 300; } static int F5x4() { return F2x8() + 4; } static int F5x5() { return F2x10() + 5; } static int F5x6() { return F2x12() + 6; } static int F5x7() { return F2x14() + 7; } static int F5x8() { return F2x16() + 8; } static int F5x9() { return F2x18() + 9; } static int F6x1() { return F3x2(); } static int F6x10() { return F3x20(); } static int F6x2() { return F3x4(); } static int F6x3() { return F3x6(); } static int F6x4() { return F3x8(); } static int F6x5() { return F3x10(); } static int F6x6() { return F3x12(); } static int F6x7() { return F3x14(); } static int F6x8() { return F3x16(); } static int F6x9() { return F3x18(); } static int F7x1() { return F3x2() + 1; } static int F7x10() { return F3x20() + 10; } static int F7x2() { return F3x4() + 2; } static int F7x3() { return F3x6() + 3; } static int F7x4() { return F3x8() + 4; } static int F7x5() { return F3x10() + 5; } static int F7x6() { return F3x12() + 6; } static int F7x7() { return F3x14() + 7; } static int F7x8() { return F3x16() + 8; } static int F7x9() { return F3x18() + 9; } static int F8x1() { return F4x2(); } static int F8x10() { return F4x20(); } static int F8x2() { return F4x4(); } static int F8x3() { return F4x6(); } static int F8x4() { return F4x8(); } static int F8x5() { return F4x10(); } static int F8x6() { return F4x12(); } static int F8x7() { return F4x14(); } static int F8x8() { return F4x16(); } static int F8x9() { return F4x18(); } static int F9x1() { return F4x2() + 1; } static int F9x10() { return F4x20() + 10; } static int F9x2() { return F4x4() + 2; } static int F9x3() { return F4x6() + 3; } static int F9x4() { return F4x8() + 4; } static int F9x5() { return F4x10() + 5; } static int F9x6() { return F4x12() + 6; } static int F9x7() { return F4x14() + 7; } static int F9x8() { return F4x16() + 8; } static int F9x9() { return F4x18() + 9; }
  • (cs)

    While I haven't checked if it already exists, here a non-recursive Ruby solution overwriting the default operator.

    I couldn't test it, so it'll probably not work.

    But it has comments, works with negative numbers, and doesn't interfere with non-integral multiplication.

    class Bignum
  # Save the old multiplication
  alias old_mult *
end

class Fixnum
  # Save the old multiplication
  alias old_mult *
end

class Integer
  def *(b)
    # Only perform RPM on two integers
    if b.is_a? Integer
      # Copy first operand so that it can be modified in place *
      a = self
      # If any of the two is 0, result is 0
      return 0 if a == 0 or b == 0
      # Get the sign of the result **
      sgn = ((a <=> 0) + (b <=> 0)).abs - 1
      # Get the absolute values
      a, b = a.abs, b.abs
      # Initialize the result
      result = 0
      # > 0 because we want to do a last addition when a is 1
      while a > 0
        # Add b to result if a is odd
        result += b if a % 2 == 1
        a << -1 # Right shift a by one
        b << 1  # Left shift b by one
      end
      # Return the result (also: get the sign right)
      sgn * result
    else
      # Use old multiplication if no Integer supplied
      old_mult(b)
    end
  end
end

=begin
* Not sure if this is neccessary, but as I said, I wasn't able to test it.
** You got it? No? Okay, explanation:
a<0^b>0 => (a<=>0)=-1^(b<=>0)=1 => sgn=(-1+1).abs-1=-1
a<0^b<0 => (a<=>0)=-1^(b<=>0)=-1 => sgn(-1-1).abs-1=1
a>0^b>0 => (a<=>0)=1^(b<=>0)=1 => sgn=(1+1).abs-1=1
a>0^b<0 => (a<=>0)=1^(b<=>0)=-1 => sgn(1-1).abs-1=-1
(a<=>0)=0 or (b<=>0)=0 cannot occur, because of the line above that.
=end

    Addendum (2009-07-22 11:36): Okay, so this is one of the least clever solutions... but it is commented like no other. Does this get me a sticker?

    Addendum (2009-07-22 13:32): Damn! I'm stupid. Of course, sgn*result is incorrect. Take this instead:

          (sgn == -1) ? 0 - result : result

Addendum (2009-07-22 13:34):
    (gotta close those tags.)
  • Ken B (unregistered) in reply to Zor
    Zor:
    All of these solutions are soooooo slooooooooow. Try this one out. Just call the function you need! Ex: for 5 x 18, call "F5x18();". Note: Doesn't yet work for all values, but I'm working on it.
    static int F10x1() { return F5x2(); } static int F10x10() { return F5x20(); } ...snip... static int F9x8() { return F4x16() + 8; } static int F9x9() { return F4x18() + 9; }
    The problem is when you don't know the two parameters until runtime. In that case, you'll need something like this: 
    switch( x*y )
    {
    case 1: return F1x1();
    case 2: return F1x2();
    case 3: return F1x3();
    case 4: return F2x2();
    }
    As in your code, it won't handle all cases, but you can finish this "enhancement" as you finish your original code.
  • Steve the Cynic (unregistered) in reply to Ken B
    Ken B:
    Noted. (Also, I am not familiar with using standard ASCII characters for APL, as I had a "real" APL character set to work with.) However, where's your single-line solution, as any "good" APL programmer knows is the target.

    Exercise for the reader, as always.

    Or if you insist:

         RET <- A RUSSIAN B
[1] RET <- +/ X x B x 2 | |_ X <- 2 * (highminus)1 + (iota) (upside down L) 2 (star-in-circle) A + 1
  • (cs) 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.
    Except that C doesn't define bit shift on negative integers. How do you like this signature: 
    int peasant_multiply(int x, int y, int *result);
    Maybe we could set errno, in the grand tradition of sqrt().

    Or how about this:

    unsigned int peasant_multiply(unsigned int x, unsigned int y);
    Using multiply and divide expands our domain from N × N to Z × Z. If that's not worth the minor performance penalty, you're doing much more interesting work than I am.
  • WraithShade (unregistered)

    Since I read this as "Multiply exactly like russian peasants would" then I did it the old-fashioned C# way.

    public static int RussianPeasantMultiplication(int CurrentLeftValue, int CurrentRightValue)
{
    List<int> LeftColumn = new List<int>();
    List<int> RightColumn = new List<int>();
    int FinalValue = 0;

    LeftColumn.Add(CurrentLeftValue);
    RightColumn.Add(CurrentRightValue);

    while (true)
    {
        CurrentLeftValue = LeftColumn[LeftColumn.Count - 1];
        CurrentRightValue = RightColumn[RightColumn.Count - 1];

        CurrentLeftValue /= 2;
        CurrentRightValue *= 2;

        LeftColumn.Add(CurrentLeftValue);
        RightColumn.Add(CurrentRightValue);

        if (CurrentLeftValue <= 1) break;
    }

    for (int i = 0; i < LeftColumn.Count; i++)
    {
        if (LeftColumn[i] % 2 != 0)
            FinalValue += RightColumn[i];
    }

    return FinalValue;
}
  • CF Guru (unregistered)

    Dammit...Someone beat me the the CF solution...

    Where are the COBOL developers? Don't make me bust out my college COBOL!!!

  • porty (unregistered) in reply to Zor

    Zor, this is very useful. Perhaps something like this would make it easier for the user?

    #define multiply(X, Y) F##X##x##Y ()

  • (cs) in reply to threecheese

    Did that already...

    But...

    sub t{$[0]?t($[0]>>1,$[1]<<1)+($[0]&1)*$_[1]:0}

    52 char is about as far down as I can get it, and does not handle (-) due to Perl using C shifts, which dont operate properly on (-)..

  • Kman (unregistered) in reply to shub

    inline bool shift(unsigned int& result, unsigned int a, unsigned int b) { return result += a & 1 ? b : 0; }

    unsigned int RM(unsigned int a, unsigned int b) { unsigned int result = 0; while (a != 1 && shift(result, a>>=1, b<<=1)) { } return result; }

  • HonestJoe (unregistered)

    public class NotCheating {

    public static int multiply(int i, int j) {
	// using russian multiplication
	return multiplyRussian(i, j);
}

private static int multiplyRussian(int i, int j) {

	/*
	 * This method is so secret, you should not even know
	 * it is here!
	 * Please stop reading immediately!
	 * No kidding!
	 * Stop now, before it is to late!
	 * Trust me, this is a really neat implementation of the
	 * russian peasants algorithm, but for your own sake,
	 * STOP NOW!
	 */


	return i*j;

}

    }

  • baka0815 (unregistered)

    Well, what's a promis if you don't break it? :)

    • using bit shifting
    • using and instead of mod
    • working with zeros
    • not working with negatives - but why should a peasant multiply negative values?
    function RussianMultiply(Left, Right: Integer): Integer;
begin
  Result := 0;

  Inc(Result, Right * (Left and 1));
  while Left > 1 do
  begin
    Left  := Left shr 1;
    Right := Right shl 1;
    Inc(Result, Right * (Left and 1));
  end;
end;
  • ponky (unregistered)

    C++ version

    
void russian(int x, int y)
{
	if (x == 0) throw 0;
	try { russian(x>>1, y<<1); }
	catch (int a) { throw a + y * (x & 1); }
}

int multiply(int x, int y)
{
	try { russian(x, y); }
	catch (int a) { return a; }
}

Leave a comment on “Russian Peasant Multiplication”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article