• Anonymous (unregistered)

    I've never seen a comments page fill up so quickly (at least, not with legitimate and well thought out comments). This has been a rousing success!

  • John Evans, [email protected] (unregistered)

    This is PHP, although it probably works as Perl too.

    	$a = 18;
	$b = 23;

	for ($t = 0; $a > 0; $a >>= 1, $b <<= 1)
		$t += (($a % 2) * $b);

	echo "total: $t\n";
  • Albrecht from Germany (unregistered)

    This one ist Tcl/Tk http://www.tcl.tk

    proc russ {a b} { set erg 0 if {$a < 0} { set a [expr {-1 * $a}] set b [expr {-1 * $b}] } for {} {$a} {} { if {$a&1} { incr erg $b puts [format %5d%5d%5d $a $b $erg] } else { puts [format %5d%5d $a $b ] } set a [expr {$a >> 1}] set b [expr {$b << 1}] } puts "==========[format %5d $erg] =======" return $erg } russ 18 23

  • Jim Halfpenny (unregistered)

    Here's the 'schoolbook' perl version to demonstrate recusive fuctions. No fancy operators, indentation where appropriate and variable names which provide no description of that they do. And of course no comments.

    It's kind of beautiful.

    print axb($ARGV[0],$ARGV[1]) . "\n"; sub axb { my $a = shift; my $b = shift; my $total = 0; if ($a == 1) { return $b; } else { if ($a % 2) { $total += $b; } $ah = int($a / 2); $bh = $b * 2; return $total + axb($ah,$bh); } }

  • leppie (unregistered)

    People still using * directly.

    That's cheating yourself!

    Try harder!

  • Albrecht from Germany (unregistered) in reply to Albrecht from Germany 
    # This one ist Tcl/Tk http://www.tcl.tk
# now with indentation
proc russ {a b} {
    set erg 0
    if {$a < 0} {
	set a [expr {-1 * $a}]
	set b [expr {-1 * $b}]
    }
    for {} {$a} {} {
	if {$a&1} {
	    incr erg $b
	    puts [format %5d%5d%5d $a $b $erg]
	} else {
	    puts [format %5d%5d $a $b ]
	}
	set a [expr {$a >> 1}]
	set b [expr {$b << 1}]
    }
    puts "==========[format %5d $erg] ======="
    return $erg
}
russ 18 23
  • Bob Montgomery (unregistered) in reply to Bosshog
    Bosshog:
    	;  6502 Assembler (4-bit operands only)
	;  $0001 should contain operand 1 (not preserved)
	;  $0002 should contain operand 2 (not preserved)

    LDA #0		
LDX #0		

    

    loop:	
CPX $02		
BEQ done	
CLC		
LSR $02	 	
BCC skip 	
CLC		
ADC $01  	
skip:
ASL $01  	
JMP loop	
    

    done:
STA $00

    You beat me to the punch, but there is some unnecessary code in there (you don't need to clear the carry before a LSR). And trashing X is unnecessary since you can test for zero just as fast with LDA $02. Or with some crazy jujitsu to save a byte... Here's my version, handles 8-bit operands:

    ;--$00 holds operand 1
;--$01 (low byte) and $02 (high byte) hold operand 2
;--$03 (low byte) and $04 (high byte) hold product
	cld
Loop
	lsr $00
	bcc NoAdd
	clc
	lda $03
	adc $01
	sta $03
	lda $04
	adc $02
	sta $04
	.byte $2C
NoAdd
	beq Done
	asl $01
	rol $02
	bcc Loop	;this assumes that operand 2 is 8-bit
Done
  • Jared Youtsey (unregistered) 
    	public static double Multiply(long left, long right)
	{
		AddRecord(left, right);
		Recurse(left, right);
		var result = 0D;
		foreach (var row in table)
		{
			result += row.Value;
		}

		return result;
	}

	public static void Recurse(long left, long right)
	{
		var newLeft = (long)(left / 2);
		var newRight = right * 2;
		AddRecord(newLeft, newRight);
		if (newLeft != 1)
		{
			Recurse(newLeft, newRight);
		}
	}

	private static void AddRecord(long newLeft, long newRight)
	{
		long remainder;
		var ignored = Math.DivRem(newLeft, 2L, out remainder);
		if (remainder != 0)
		{
			table.Add(newLeft, newRight);
			Console.WriteLine("left = " + newLeft + "\tright = " + newRight);
		}
	}
  • acsi (unregistered)

    Spreadsheet...

    First number goes in A2 A3 through A41 have "=TRUNC(A2/2)", "=TRUNC(A3/2)", etc (enter in A3, drag lower-right corner to expand to full range, in Excel at least the formulas in the additional cells will be adjusted to keep the relative positions of the referenced cells the same).

    Second number goes in B2 B3 through B41 have "B22", "B32", etc.

    C2 through C41 have "=IF(MOD(A2, 2) = 1, B2, 0)", "=IF(MOD(A3, 2) = 1, B3, 0)", etc.

    D2 has "=SUM(C2:C41)", and is the result.

    A1 through D1 have headers "First Number", "Second Number", "Cross out where A is even", and "Result".

    This function can be called by using the MSOffice interop libraries to open the spreadsheet, populate A2 and B2, and read D2 (there might be another step in between to tell it to run the actual calculation, I forget).

  • (cs)

    Just my own little recursive Java solution:

    	private int multiply(int n, int m, int val) {
		if(n <= 1)
			return val;
		return multiply(n/2,m*2,((n/2)%2!=0 ? val+=m*2 : val) );
	}
	
And of course, the ternary one liner:

	private int multiplyOneLiner(int n, int m, int val) {
		return (n <= 1 ? val : multiply(n/2,m*2,((n/2)%2!=0 ? val+=m*2 : val) ));
	}
  • Osno (unregistered)

    MSIL:

    .method private hidebysig static int64 Multiply(int64 f, int64 s) cil managed { .maxstack 3 start: ldarg.0 dup ldc.i4.0 beq.s done ldc.i4.1 and ldarg.1 mul next: ldarg.0 ldc.i4.1 shr ldarg.1 ldc.i4.1 shl call int64 RussianMult.Program::Multiply(int64, int64) add done: ret }

  • Lunkwill (unregistered)

    As we haven't had any m68k yet:

    ; op1: d0
; op2: d1
; out: d0
; scratch: d2
peasantmult:
	clr.l	d2
.loop:	tst.l	d0
	beq.s	.exit
	lsr.l	d0
	bcc.s	l
	add.l	d1,d2
	asl.l	d1
	bra.s	.loop
.exit:	move.l	d2,d0
	rts

    20 bytes in binary :)

  • Jared Youtsey (unregistered) in reply to Jared Youtsey

    After looking at some of the other solutions I realize that I don't do this kind of programming and why. This kind of boolific bitshifty goodness is brain melting. But it was fun. But boy am I shamed by the cleverness of many of the other solutions.

  • HonoredMule (unregistered) in reply to The Wolf

    This revision of The Wolf's PHP solution handles negative numbers and displays the columns in a table with unused rows crossed out.

    <?php

function visual_russian($x, $y) {
	$left = array();
	$right = array();
	$str = "<table>Operand:
    $x    Operator:
    $y    ";
	
	$sign = 1;
	if($x < 0) {
		$sign *= -1;
		$x = abs($x);
	}
	if($y < 0) {
		$sign *= -1;
		$y = abs($y);
	}

	while ($x >= 1) {
		$left[] = $x;
		$right[] = $y;
		if($x % 2)
			$str .= "$x$y";
		else
			$str .= "$x$y";
		$x = floor($x / 2);
		$y *= 2;
	}
	
	$result = 0;
	foreach ($left as $index => $x) if ($x % 2)
		$result += $right[$index];
	$result = $sign * $result;
	$str .= "Answer:$result";
	return $str;
}

echo visual_russian(156657, -159643248);

?>
  • Alex Muscar (unregistered)

    Common Lisp:

    No multiplication.

    (defun rpm (m n)
  (do ((t1  m (ash t1 -1))
         (t2  n (ash t2 1))
         (r 0))
       ((= t1 0)  r)
    (when (= (logand t1 1) 1)
      (incf r t2))))

    The parens might be unbalanced since I'm writing this from my phone.

  • David C. (unregistered)

    33 characters in C#:

    (a,b)=>a==1?b:m(a/2,b2)+b(a&1);

    Implementing this lambda expression in code is left as an exercise for the reader (hint: assign it to a delegate named 'm')

  • HonoredMule (unregistered)

    Reading many of these ingenious, esoteric, or even simple and straight-forward implementations in various languages makes me very happy that I don't often have to use languages other than PHP.

  • Jörg (unregistered)

    A slightly more sophisticated python version:

    def peasant_mul(a,b):
    def numbers(a=a, b=b):
         if a < 0:
            a, b =  -a, -b
        while a:
            if a & 1:
                yield b
            a >>= 1
            b <<= 1
    return sum(numbers())

    why is code double-spaced or is that my firefox?

  • Josh Bohde (unregistered) in reply to halber_mensch
    halber_mensch:
    Extrapolated from discussion with Josh Bohde:

    m=lambda a,b:b*(a&1)+m(a>>1,b<<1) if abs(a)>1 else a*b

    55 chars... not as short but handles all integers.

    Just because I think using * isn't in the spirit of this.

    m=lambda a,b:[0,b][a&1]+m(a>>1,b<<1)if a else 0
n=lambda a,b:(lambda n,t:[n,~n+1][t])((m(abs(a),abs(b))),(a<0)^(b<0))

    n will handle negatives. 118 characters, including newline.

  • HonoredMule (unregistered)

    One last tweak: forgot to switch the floor($x / 2) for a bit shift.

    <?php

function visual_russian($x, $y) {
	$left = array();
	$right = array();
	$str = "<table>Operand:
    $x    Operator:
    $y    ";
	
	$sign = 1;
	if($x < 0) {
		$sign *= -1;
		$x = abs($x);
	}
	if($y < 0) {
		$sign *= -1;
		$y = abs($y);
	}

	while ($x >= 1) {
		$left[] = $x;
		$right[] = $y;
		if($x % 2)
			$str .= "$x$y";
		else
			$str .= "$x$y";
		$x = $x >> 1; //floor($x / 2);
		$y *= 2;
	}
	
	$result = 0;
	foreach ($left as $index => $x) if ($x % 2)
		$result += $right[$index];
	$result = $sign * $result;
	$str .= "Answer:$result";
	return $str;
}

echo visual_russian(156657, -159643248);

?>
  • (cs) in reply to Dave van der Brugge
    Dave van der Brugge:
    So many nice solutions, yet nobody has offered a solution using XSLT yet.

    So here is mine. The xsl and xml code can be seen here: http://damastabrain.mine.nu/RPA/highlight.php For a better highlight function (at least Firefox), view the xsl itself: http://damastabrain.mine.nu/RPA/russianPeasantAlgorithm.xsl And ofcourse to show the outcome: http://damastabrain.mine.nu/RPA/russianPeasantAlgorithm.xml

    Note: it Does work with negative numbers, on either one of the two or both sides. (Integer only)

    Hadnt registered yet... Also it now works with 0 on any side.

  • (cs)

    Obligatory solution from a Haskell neophyte:

     rpMultiply a b =
   ( sum . map snd . filter ( odd . fst ) ) ( zip ( takeWhile ( >= 1 ) a' ) b' )
   where
     a' = a : ( map ( `div` 2 ) a' )
     b' = b : ( map ( (*)   2 ) b' )
  • martinp (unregistered)

    Did this in Python, and it made me remember why I like it so much.

    def rp_multiply(m, n):
    sum = 0
    while m >= 1:
        if m % 2 != 0:
            sum += n
        n *= 2
        m /= 2;
    return sum
  • hornet (unregistered)

    long rmultiply(long a, long b) { return (a==1)?b:((a&1)?b:0)+rmultiply(a>>1,b<<1); }

  • Cindi Knox (unregistered)

    mIRC

    alias productRussianPeasant {
  ;multiplies two integers using Russian Peasant method
  ;parms: multiplier, multiplicand
  ;returns: product
  var %lMultiplier
  var %lMultiplicand
  var %lProduct

  ;use minimum iterations - smaller parm goes in multiplier:
  if ($1 < $2) {
    %lMultiplier = $1
    %lMultiplicand = $2
  }

  else {
    %lMultiplier = $2
    %lMultiplicand = $1
  }

  ;clear product accumulator:
  %lProduct = 0


  while (%lMultiplier > 0) {
    if ($calc(%lMultiplier % 2) > 0) {
      ;multiplicans counts toward product if multiplier is odd:
      %lProduct = $calc(%lProduct + %lMultiplicand)
    }
    %lMultiplier = $int($calc(%lMultiplier / 2))
    %lMultiplicand = %lMultiplicand * 2
  }

  return %lProduct
}
  • Bored (unregistered) 
    int rmul(auto a, auto b) {
   auto sum=0,target=a*b;
   while(sum!=target) {
      sum += a&1?b:0, a>>=1, b<<=1;
   }
   return sum;
}

    I like it since it does the builtin multiply anyway, and then the calculation. NB: infinite loops may happen with -ve numbers.

  • (cs)

    My implementation is in C (or C++).

    typedef unsigned long ulong;
ulong russian_peasant_mult(ulong x, ulong y)
{
    ulong result = 0;
    if(x == 0 || y == 0)
        return 0;
    if(x % 2 != 0)
        result += y;
    while(x != 1)
    {
        y *= 2;
        if((x /= 2) % 2 != 0)
            result += y;
    }
    return result;
}

    If you accuse me of initially using std::list and std::pair I'll deny it! Deny!

  • Tim Pierce (unregistered)
    There is no language restriction, though anything on the esoteric language list will probably be ignored.

    Including Perl? :-)

  • (cs)

    Quick Solution in Delphi. Accompanying form has a StdCtrls Memo to display columns named Memo1. Two edit boxes allow input of multiplicands (edit1 := Leftside, edit2 := Rightside). ClearValues simply clears the edit boxes and resets all totals. lblResult is a label displaying the result. This routine will not handle negative numbers.

    procedure TForm1.ComputeRpProduct; var vTotal : Integer;

    {SUB} procedure AddLineToMemo; begin if (Leftside mod 2) <> 0 then begin Memo1.Lines.Add(inttostr(Leftside) + ' ' + inttostr(RightSide)); vTotal := vTotal + Rightside; end else begin Memo1.Lines.Add(inttostr(Leftside) + ' ' + inttostr(RightSide) + ' ---'); end; end; {/SUB}

    begin if (Leftside <> 0) and (Rightside <> 0) then begin

    vTotal := 0;

AddLineToMemo;

while Leftside <> 1 do
begin

  Leftside := Leftside div 2;
  Rightside := Rightside * 2;

  AddLineToMemo;

end;

lblResult.Caption := IntToStr(vTotal);

    end else begin ShowMessage('Please enter numeric nonzero values to compute.'); ClearValues; Edit1.setfocus; end;

    end;

  • mucki.at (unregistered)

    I didn't read all the comments but this is also called "Shift and Add" in information processing, and this is typically how computers actually implement multiply. Thus, I propose this "hardware accelerated" version of the algorithm:

    return a*b;

    (see http://en.wikipedia.org/wiki/Multiplication_algorithm#shift_and_add for more info)

  • (cs)

    I missed a lot previously...enough to make me register so I can erase evidence of future blunders. This PHP handles negative numbers, outputs an HTML table with the unused rows crossed out, and is derived from the code posted by The Wolf on page one of the comments:

    <?php

function visual_russian($x, $y) {
	$str = "<table>Operand:
    $x    Operator:
    $y    ";
	$result = 0;
	
	$sign = 1;
	if($x < 0) {
		$sign *= -1;
		$x = abs($x);
	}
	if($y < 0) {
		$sign *= -1;
		$y = abs($y);
	}

	while ($x > 1) {
		$x = $x >> 1;
		$y *= 2; // Bit-shifting $y causes overflow, but multiplication does not.
		if($x % 2) {
			$str .= "$x$y";
		} else {
			$str .= "$x$y";
			$result += $y;
		}
	}
	$str .= "Answer:$result";
	return $str;
}

echo visual_russian(156657, -159643248);

?>
  • David Young (unregistered)

    int russian_peasant(int n1, int n2) { int product = 0, sign = 1;

    if(n1 < 0) {
	sign = -1;
}

for(; n1 != 0; n1 /= 2, n2 *= 2) {
	if(n1 & 1) {
		product += n2;
	}
}

return product * sign;

    }

  • wombat (unregistered)

    Recursive Common Table Expression in MS SQL Server:

    WITH russian AS ( SELECT 45 a, 76 b UNION ALL SELECT a / 2, b + b FROM russian WHERE a > 1) SELECT ISNULL(SUM(b), 0) AS product FROM russian WHERE a & 1 = 1

  • (cs)

    C++ using for loop

    for(int a=3,b=5,c=0;a>0;c+=(a&1?b:0),a>>=1,b<<=1,std::cout<<c<<std::endl);

  • (cs) in reply to xtremezone
    xtremezone:
    My implementation is in C (or C++). 
    typedef unsigned long ulong;
ulong russian_peasant_mult(ulong x, ulong y)
{
    ulong result = 0;
    if(x == 0 || y == 0)
        return 0;
    if(x % 2 != 0)
        result += y;
    while(x != 1)
    {
        y *= 2;
        if((x /= 2) % 2 != 0)
            result += y;
    }
    return result;
}
    If you accuse me of initially using std::list and std::pair I'll deny it! Deny!
    I wrongly assumed it only worked for positive integers so I used unsigned types. :-[ Here's a quick fix. 
    long russian_peasant_mult(long x, long y)
{
    int negative = 0;
    long result = 0;
    if(x == 0 || y == 0)
        return 0;
    if(x < 0 && y > 0)
    {
        x *= -1;
        negative = 1;
    }
    else if(x > 0 && y < 0)
    {
        y *= -1;
        negative = 1;
    }
    if(x % 2 != 0)
        result += y;
    while(x != 1)
    {
        y *= 2;
        if((x /= 2) % 2 != 0)
            result += y;
    }
    if(negative)
        result *= -1;
    return result;
}
  • hornet (unregistered)

    Supporting negative numbers: long multiply(long a, long b) { return (a<0)?-multiply(-a,b):(a==1)?b:((a&1)?b:0)+multiply(a>>1,b<<1); }

  • anonymous (unregistered)

    In JavaScript var s = 7 * 38;

    The binary approach is taken behind the scenes.

  • JJM (unregistered) 
    def multiply(a,b):
    c=0
    while a>1:
        a >>= 1
        b <<= 1
        c += b*(a&1)
    return c
  • Trey Jackson (unregistered)

    common lisp from Emacs:

    (defun mymult (nn mm) (loop for n = nn then (/ n 2) for m = mm then (* m 2) until (< n 1) sum (if (oddp n) m 0)))

  • IcePanther (unregistered)

    Solution in PHP :

    function peasant($a,$b) { $s = 0; while($a > 1) { $b *= 2; $a = floor($a/2); if(($a % 2) != 0) { $s += $b; } }

    return $s;

    }

    Could probably be made more efficient by using bitwise operations instead of base mathematical operators. Well, would obviously be more efficient NOT being written in PHP, too.

  • Tim (unregistered)

    My recursive PHP CLI version. (Inputs must be >0) The output will create the table as shown in the instructions and even cross out the even rows.

    <?php


function multiply($x, $y, $padX, $padY)
{
    $even = ($x % 2 == 0);
    
    if ($even) {
        $pad = '-';
    } else {
        $pad = ' ';
    }

    echo $pad . $pad
       . str_pad($x, $padX, $pad, STR_PAD_LEFT)
       . $pad . 'x' . $pad
       . str_pad($y, $padX + $padY, $pad, STR_PAD_LEFT)
       . $pad . $pad . "\n";
    
    if (abs($x) == 1) {
        return $y;
    }
    
    $add = multiply((int) ($x/2), $y * 2, $padX, $padY);
    
    if (!$even) {
        return $y + $add;
    } else {
        return $add;
    }

}

$x = $argv[1];
$y = $argv[2];
$padX = strlen($x);
$padY = strlen($y);

if ($x <= 0 || $y <= 0) {
    echo 'Usage: ' . $argv[0] . ' x y' . "\n"
       . 'Both x and y must be greater than 0' . "\n";
    exit;
}

$product = multiply ($x, $y, $padX, $padY);

echo str_pad('', $padX + $padX + $padY + 7, '_') . "\n"
   . str_pad($product, $padX + $padX + $padY + 5, ' ', STR_PAD_LEFT) . "\n";

</pre>
  • Osno (unregistered)

    Non-recursive MSIL, more stack-based:

    .method private hidebysig static int64 m(int64 f, int64 s) cil managed { .maxstack 4 ldc.i4.0 conv.i8 start: ldarg.0 ldc.i4.0 beq.s done ldarg.0 ldc.i4.1 and ldarg.1 mul add ldarg.0 ldc.i4.1 shr starg.s 0 ldarg.1 ldc.i4.1 shl starg.s 1 br.s start done: ret }

  • Andrew Nurse (unregistered)

    This was perfectly timed, since I'm learning Haskell. It gave me the perfect opportunity to try out what I've learned so far :). So to add to the already numerous Haskell solutions, here's mine (I noticed it looked similar to others, so I guess I'm getting the hang of this functional programming thing :D):

    russianMult :: (Integral a) => a -> a -> a
russianMult 1 y = y
russianMult x y = if x `mod` 2 == 0 then 
	             multStep 
		  else 
		     multStep + y
    where multStep = russianMult (x `div` 2) (y * 2)

    I'm sure there's more concise ways to do this, but this works :).

  • Igor V. (unregistered)

    Unobfuscated Perl:

    sub russian_peasant_multiply {
    my ($one, $two) = @_;
    my $rus = 0;
    do {
        $rus += $two if ($one & 1);
    } while ($one >>= 1 and $two <<= 1);
    return $rus;
}
  • jeff.woodhull (unregistered)

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

    namespace ConsoleApplication1 { class Program { static void Main(string[] args) { var leftNum = 0; var rightNum = 0;

    		if (args.Length != 2 || (!Int32.TryParse(args[0], out leftNum) || ! Int32.TryParse(args[1], out rightNum)))
		{
			Console.WriteLine("Please enter numbers like ConsoleApplication1.exe 5 10");
			return;
		}

		var answer = (from p in RussianPairs(leftNum, rightNum)
					  where p.Left % 2 != 0
					  select p.Right).Sum();

		Console.WriteLine("The answer to {0} * {1} is {2}", leftNum, rightNum, answer);
		Console.WriteLine("Press <enter> to exit");
		Console.ReadLine();
	}


	static IEnumerable<Pair> RussianPairs(int leftNumber, int rightNumber)
	{
		while (leftNumber >= 1)
		{
			yield return new Pair(leftNumber, rightNumber);
			leftNumber /= 2;
			rightNumber *= 2;
		}
	}

	internal class Pair
	{
		internal Pair(int left, int right)
		{
			Left = left;
			Right = right;
		}

		internal int Left { get; private set; }
		internal int Right { get; private set; }
	}
}

    }

  • Tyler (unregistered) in reply to Bob

    You didn't add the first row in your first example.

  • It'sMe ([email protected]) (unregistered)

    non recusive version in c# with 64bit in because russians love big numbers right?

    private static Int64 RussianPeasantMultiplication(Int64 first, Int64 second)
{
	Int64 rvalue = 0;
	
	while(first > 0)
	{
		if(first % 2 != 0)
		{
			rvalue += second;
		}
		first /= 2;
		second *= 2;
	}
	
	return rvalue;
}
  • Mike5 (unregistered) in reply to Anonymous Coward
    Anonymous Coward:
    Prolog:

    rusmul(0,_,0). rusmul(A,B,X) :- C is A//2, D is B*2, rusmul(C,D,E), X is E+(A mod 2)*B.

    "optimized" with bit-shifting

    russian( 0, _, 0 ).

russian( A, B, C ) :-
    A /\ 1 =:= 1,
    B1 is B << 1,
    A1 is A >> 1,
    russian( A1, B1, C1 ),
    C is C1 + B.

russian( A, B, C ) :-
    B1 is B << 1,
    A1 is A >> 1,
    russian( A1, B1, C ).
  • (cs) in reply to xtremezone
    xtremezone:
    I wrongly assumed it only worked for positive integers so I used unsigned types. :-[ Here's a quick fix. 
    long russian_peasant_mult(long x, long y)
{
    int negative = 0;
    long result = 0;
    if(x == 0 || y == 0)
        return 0;
    if(x < 0 && y > 0)
    {
        x *= -1;
        negative = 1;
    }
    else if(x > 0 && y < 0)
    {
        y *= -1;
        negative = 1;
    }
    if(x % 2 != 0)
        result += y;
    while(x != 1)
    {
        y *= 2;
        if((x /= 2) % 2 != 0)
            result += y;
    }
    if(negative)
        result *= -1;
    return result;
}
    <sigh/> Accounted for one negative number, but not two... Fixed. :P Maybe. 
    long russian_peasant_mult(long x, long y)
{
    int negative = x < 0 && y > 0 || x > 0 && y < 0;
    long result = 0;
    if(x == 0 || y == 0)
        return 0;
    if(x < 0)
        x *= -1;
    if(y < 0)
        y *= -1;
    if(x % 2 != 0)
        result += y;
    while(x != 1)
    {
        y *= 2;
        if((x /= 2) % 2 != 0)
            result += y;
    }
    if(negative)
        result *= -1;
    return result;
}
    Though the negative workarounds do use multiplication which may be a paradox of sorts... >_<

    Addendum (2009-07-22 13:34): I suppose you could replace...

    x *= -1;

    ...with...

    x -= russian_peasant_mult(x, 2);

    :P

    Addendum (2009-07-22 13:36): No, no, wait, no you couldn't... Infinite recursion...

  • Bob (unregistered)

    Scheme:

    (define (peasant* a b)
  (do ([acc '() (if (odd? a)
                    (cons b acc)
                    acc)]
       [a a (quotient a 2)]
       [b b (+ b b)])
      [(= a 1)
       (fold + b acc)]))

    Assumes fold:

    (define (fold p x l)
  (if (null? l)
      x
      (fold p 
            (p (car l) x) 
            (cdr l))))

    Easily done without the list, I thought it was more in keeping, though.

Leave a comment on “Russian Peasant Multiplication”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article