Comment On Russian Peasant Multiplication

Ever since the first OMGWTF Programming Contest, I've always wanted to bring back some element of "coding challenges" to the site. Ideally, this would be in the form of a second contest... but considering that contests require a ton of work, and the fact that interns around town have come to learn that interning at Inedo basically mean means shipping mugs, mailing stickers, testing contest entries, and acting as human ottomans, we'll have to go with something a bit scaled back. And that's where Programming Praxis will come in. [expand full text]
« PrevPage 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 | Page 9 | Page 10 | Page 11 | Page 12 | Page 13 | Page 14 | Page 15 | Page 16Next »

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:34 • by antelopelovefan
Here's another VBScript version meant to run as an Excel macro.

It assumes the values to be multipled are in cells A2 and B2 of the first Worksheet and it stores all of the intermediate numbers in the cells below as it calculates.

The final output is put in cell C2


Public Sub CalculateRussianPeasant()
Dim curSheet As Worksheet
Dim curRow: curRow = 2
Dim bDone
Dim i As Integer
Dim total

Set curSheet = Worksheets(1)

Rows("3:65536").Select
Selection.Delete Shift:=xlUp

While Not bDone
curSheet.Cells((curRow + 1), 1).Value = CInt(curSheet.Cells(curRow, 1).Value / 2)
curSheet.Cells((curRow + 1), 2).Value = CInt(curSheet.Cells(curRow, 2).Value * 2)

curRow = curRow + 1

If curSheet.Cells(curRow, 1).Value = 1 Then
bDone = True
End If
Wend

curSheet.Cells(2, 3).Value = 0
For i = 2 To curRow
If curSheet.Cells(i, 1).Value Mod 2 <> 0 Then
curSheet.Cells(2, 3).Value = curSheet.Cells(2, 3).Value + curSheet.Cells(i, 2).Value
ElseIf i > 2 Then
Range("A" & i & ":B" & i).Select
With Selection.Font
.Strikethrough = True
.ColorIndex = 3
End With
End If
Next

Range("C2").Select
End Sub

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:35 • by Quxxy (unregistered)
A version for the D programming language; both as an interative function and a template:

// Regular version.  Can also be used in compile-time code.

long multiply(long a, long b)
{
if( a == 0 || b == 0 ) return 0;
if( a < 0 ) return -multiply(-a, b);
if( b < 0 ) return -multiply(a, -b);

long acc = 0;
do
{
if( a % 2 == 1 )
acc += b;
a /= 2;
b *= 2;
}
while( a >= 1 );
return acc;
}

// Template version
template Multiply(long a, long b)
{
static if( a == 0 || b == 0 )
const Multiply = 0L;

else static if( a < 0 )
const Multiply = Multiply!(-a, b);

else static if( b < 0 )
const Multiply = Multiply!(a, -b);

else static if( a == 1 )
const Multiply = b;

else static if( a % 2 == 1 )
const Multiply = b + Multiply!(a/2, b*2);

else
const Multiply = Multiply!(a/2, b*2);
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:35 • by f3nd3r (unregistered)
278070 in reply to 277787
Wow, you make PHP look good, that is pretty impressive.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:37 • by Amadan (unregistered)
In Ruby,

class Fixnum
def *(b)
a, k = self, 0
a, b = -a, -b if a < 0
while a != 0
k += b if a & 1 == 1
a >>= 1
b <<= 1
end
k
end
end

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:37 • by Northpole (unregistered)
Ruby, one line, non-recursive:
a,b,res=a/2,b*2,(res||0)+(a&1)*b while a>0

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:42 • by campkev
Second attempt at C#, this works with negative numbers:
public int RussianMultiply(int operand1, int operand2)
{
int res = 0;
while (operand1 != 0)
{
if (operand1 % 2 == 1) res += operand2;
else if (operand1 % 2 == -1) res -= operand2;
operand1 /= 2;
operand2 *= 2;
}
return res;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:42 • by jweir77
Different twist on a Ruby solution:


class Fixnum
def rum n
product = 0
self.to_s(2).reverse.split(//).each_with_index do |bit, pos|
product += ( n << pos ) if bit.to_i == 1
end
product
end
end

p 3.rum(2)
p 2.rum(3)
p 18.rum(23)
p 23.rum(18)
p 76.rum(45)
p 45.rum(76)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:43 • by halber_mensch
278080 in reply to 278017
Josh Bohde:
Python 2.6

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


51 characters


I'd argue it's not quite the russian algorithm though, since you've both reversed the operands and you are evaluating a-log2(a) more iterations than would be done in the real algorithm. For example, if I were to feed 5,4 into the russian algorithm, it would make 3 iterations (the left column being 5,2,1). Taking into account that you've swapped the parameters, your algorithm would evaluate 5 iterations (the left column being 5,2,1,0,0), or two more (5 - log2(5)) iterations than you should if you were adhering to the real algorithm, which stops evaluating when reaching 1 in the left column. Your solution also fails for negative values of a.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:43 • by campkev
second attempt at C# recurisive, this works with negative numbers:
public int RecursiveRussianMultiply(int operand1, int operand2)
{
return operand1 == 0 ? 0 : RecursiveRussianMultiply(operand1 / 2, operand2 * 2) + (operand1 % 2 == 1 ? operand2 : 0) + (operand1 % 2 == -1 ? -operand2 : 0);
}

Have a Linqy day!

2009-07-22 11:45 • by Floyd (unregistered)

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

namespace RussianPeasant
{
class RussianPeasant
{
static void Main(string[] args)
{
if (args.Length != 2)
{
Console.Error.WriteLine("Peasants can't multiply " + args.Length + " operands!");
return;
}

int left = 0;
int right = 0;

if ((!int.TryParse(args[0], out left)) || (!int.TryParse(args[1], out right)))
{
Console.Error.WriteLine("Peasants can't multiply non-numeric operands!");
}


int solution = (from pair in GetColumns(left, right)
where pair.First() % 2 != 0
select pair).Sum(p => p.ElementAt(1));

Console.WriteLine(solution);
Console.Read();
}

public static IEnumerable<IEnumerable<int>> GetColumns(int left, int right)
{
yield return new int[] { left, right };

while (left > 0)
{
left = left >> 1;
right = right * 2;

yield return new int[] { left, right };
}
}
}
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:46 • by Alex Guzman (unregistered)
int first = 18;
int second = 23;

int result = 0;

while ((first = first / 2) >= 1)
{
second = second * 2;

if (first % 2 != 0)
result += second;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:47 • by kastein
278085 in reply to 277989
Rootbeer:
Herman:
this is the exact implementation of the multiply function on binary computing hardware


Is this so? I had assumed that most CPUs with MULtiply opcodes used hardware lookup tables, in order to achieve a fast and constant O(1) execution time, but perhaps I am mistaken. It's certainly a less sensible approach with 32- or 64-bit operands than it would have been with 8- or 16-bit operands.

Yeah... it isn't really a good idea. I thought it was more sane until I considered the results...
for 8 bit multiplication we have two 8 bit inputs and a 16 bit output, so the table is 2^16 bits long with 16 bit entries... that's 1M transistors without the decoders/addressing logic. The average 8 bit CPU has a few thousand to a few tens of thousands of transistors. It just gets worse from there - multiplying two 16 bit numbers requires 4G 32-bit entries (128G transistors!) and multiplying two 32 bit numbers requires 1024E transistors... multiplying 64 bit numbers using a lookup table would require more transistors than there are on the planet (by at least a factor of 1 pentillion based on my napkin calculations...)

If you want to know how processors multiply, several methods are listed here: wikibooks: multiply
Booth's Algorithm
some more are listed here, not all easily applicable to microprocessor design: multiplication algorithms

More (basically the peasant's method in hardware!) binary multiplier

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:48 • by Jürgen (unregistered)
Python:


def rpmul(a, b):
return ((a == 1) and b or (a % 2) * b + rpmul(a/2, 2*b))


Ruby:


def rpmul a, b
(a == 1) ? b : (a % 2) * b + rpmul(a/2, 2*b)
end


Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:53 • by Bryan (unregistered)
All we need is a SAS submission and this thread will be complete.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:53 • by Alex Muscar (unregistered)
Common Lisp

Imperative/iterative and functional solutions. Ain't it nice that Lisp's so versatile? :P

(defun rpm (m n)
(do ((t1 m (ash t1 -1))
(t2 n (ash t2 1))
(r 0 (+ r (* (mod t1 2) t2))))
((= t1 0) r)))


(defun rpm-r (m n)
(labels ((rec (acc m n)
(if (= m 0)
acc
(rec (+ acc (* (mod m 2) n)) (ash m -1) (ash n 1)))))
(rec 0 m n)))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:55 • by Josh Bohde (unregistered)
278092 in reply to 278080
halber_mensch:
Josh Bohde:
Python 2.6

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


51 characters


I'd argue it's not quite the russian algorithm though, since you've both reversed the operands and you are evaluating a-log2(a) more iterations than would be done in the real algorithm. For example, if I were to feed 5,4 into the russian algorithm, it would make 3 iterations (the left column being 5,2,1). Taking into account that you've swapped the parameters, your algorithm would evaluate 5 iterations (the left column being 5,2,1,0,0), or two more (5 - log2(5)) iterations than you should if you were adhering to the real algorithm, which stops evaluating when reaching 1 in the left column. Your solution also fails for negative values of a.


Yeah, I was saving some characters (at the cost of a lot of memory).

Here's a recursive version that is 48 characters

m=lambda a,b:[0,b][a&1]+m(a>>1,b<<1)if a else 0

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:56 • by Sal (unregistered)
Postscript:
/rmul{0{2 index 0 eq{exit}if exch dup 1 bitshift 4 1 roll 3 -1 roll dup -1 bitshift 5 1 roll 1 and 1 eq {add}{pop}ifelse}loop exch pop exch pop}def

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:58 • by AdT (unregistered)
278095 in reply to 277892
Osno:
All the people using multiplication and division instead of shifting (except in languages where there is no shifting) also fail.


All the people who don't know what an optimizing compiler is also fail.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:59 • by Alex Muscar (unregistered)
Common Lisp:

Shorter version of the recursive implementation:


(defun rpm-r1 (m n &optional (acc 0))
(if (= m 0)
acc
(rpm-r1 (ash m -1) (ash n 1) (+ acc (* (mod m 2) n)))))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 11:59 • by Murray (unregistered)
public String multiply(int a, int b){
return "Murray is awesome";
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:03 • by PopeHappyCat (unregistered)
278099 in reply to 277920
Damn, you beat me too it. But here you can has lolcode spec 1.2

(Untested)


HAI 1.2
CAN HAS STDIO?

I HAS A X
I HAS A Y
I HAS A MULTIPL
X R NUMBR
Y R NUMBR

VISIBLE "CAN HAS X?:)"
GIMMEH X
VISIBLE "CAN HAS Y?:)"
GIMMEH Y

HOW DUZ I RPM YR X AN YR Y
I HAS A MUTLIPL ITZ 0
I HAS A MODD
I HAS A LOLCAT ITZ MAEK WIN A NUMBR BTW IS DUMMY VARIABLE FOR L00P
IM IN YR RPMLOOP UPPIN YR LOLCAT WILE DIFFRINT X AN 1
X R MAEK QUOSHUNT OF X AN 2 A NUMBR
Y R PRODUKT OF Y AN 2
MODD R MOD X AN 2
BOTH SAEM MODD AN 1, O RLY?
YA RLY, MULTIPL R SUM OF MULTIPL AN Y
NO WAI, BTW NOTHING HAPPENS
OIC
IM OUTTA YR RPMLOOP
FOUND YR MULTIPL
IF U SAY SO

MULTIPL R RPM X Y

VISIBLE "PRODUKT OF " N X N " N " N Y N " IZ " N MULTIPL N ":)"

KTHXBYE

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:03 • by Fooba (unregistered)
C implementation:

int russian(int a, int b) {int c=0,d=a^b;a*=(a<0)?-1:1;for(a<<=1;(a>>=1)!=0;b<<=1)c+=a&0x1?b:0;return((c^d)<0?-c:c);}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:03 • by koblas
Another python version


def mult(a, b) :
v = []
while a != 0 :
v.append((a % 2 != 0, b))
print a%2, a, b
a >>= 1
b <<= 1
print reduce(lambda x, y: x+y, [p[1] for p in v if p[0]])

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:06 • by Bosshog (unregistered)


; 6502 Assembler
; Runs on NES, BBC, C64, Atari 2600 and Apple II :)
; This is the 16-bit version to handle the example 18x23!

; $0002 contains unsigned 8-bit operand 1 (not preserved)
; $0004 contains unsigned 8-bit operand 2 (not preserved)
; $0001:0000 will contain HI:LO bytes of 16-bit answer

LDA #0
STA $00
STA $01
STA $03
LDX #0
loop:
CPX $04
BEQ done
CLC
LSR $04
BCC skip

CLC
LDA $00
ADC $02
STA $00
LDA $01
ADC $03
STA $01
skip:
CLC
ASL $02
ROL $03
JMP loop
done:

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:07 • by halber_mensch
278104 in reply to 278092
Josh Bohde:
halber_mensch:
Josh Bohde:
Python 2.6

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


51 characters


I'd argue it's not quite the russian algorithm though, since you've both reversed the operands and you are evaluating a-log2(a) more iterations than would be done in the real algorithm. For example, if I were to feed 5,4 into the russian algorithm, it would make 3 iterations (the left column being 5,2,1). Taking into account that you've swapped the parameters, your algorithm would evaluate 5 iterations (the left column being 5,2,1,0,0), or two more (5 - log2(5)) iterations than you should if you were adhering to the real algorithm, which stops evaluating when reaching 1 in the left column. Your solution also fails for negative values of a.


Yeah, I was saving some characters (at the cost of a lot of memory).

Here's a recursive version that is 48 characters

m=lambda a,b:[0,b][a&1]+m(a>>1,b<<1)if a else 0

m(-1,2)
....
File "<stdin>", line 1, in <lambda>
File "<stdin>", line 1, in <lambda>
RuntimeError: maximum recursion depth exceeded

=(

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:08 • by Timepass (unregistered)

package com.timepass;

public class RussianMultiply {

private int mulTotal = 0;
RussianMultiply(){
super();
}
private void multiply(int first,int second, boolean isFirstTime){
if(first == 0 || second ==0){
return;
}
if(isFirstTime && first%2!=0){
mulTotal = mulTotal + second;
}
int tempFirst = first/2;
int tempSecond = second*2;
if(tempFirst%2!=0){
mulTotal = mulTotal + tempSecond;
}
if(tempFirst != 1){
multiply(tempFirst,tempSecond,false);
}
}
public void multiply(int first,int second){
multiply(first,second,true);
}

public void clearMulTotal(){
setMulTotal(0);
}

public int getMulTotal() {
return mulTotal;
}
public void setMulTotal(int mulTotal) {
this.mulTotal = mulTotal;
}


/**
* @param args
*/
public static void main(String[] args) {
RussianMultiply rm = new RussianMultiply();

rm.clearMulTotal();
rm.multiply(18, 23);
System.out.println("Multiplication of 18 and 23:" + rm.getMulTotal());

rm.clearMulTotal();
rm.multiply(13, 13);
System.out.println("Multiplication of 13 and 13:" + rm.getMulTotal());



}


}


result:
Multiplication of 18 and 23:414
Multiplication of 13 and 13:169

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:08 • by chriswatson
C# using the delightful LINQ to objects


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

namespace RussianPeasantMultiplication
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Russian Peasant Multiplication");

Console.Write("Number 1: ");
int number1 = Convert.ToInt32(Console.ReadLine());
Console.Write("Number 2: ");
int number2 = Convert.ToInt32(Console.ReadLine());

List<Gimley> steps = new List<Gimley>();
steps.Add(new Gimley(number1, number2));

Console.WriteLine("Mutiply {0} by {1}", number1, number2);

while (steps.Last().Left != 1)
{
Gimley lastStep = steps.Last();

int newLeft = lastStep.Left / 2;
int newRight = lastStep.Right * 2;

steps.Add(new Gimley(newLeft, newRight));

Console.WriteLine("Interim step: {0}, {1}", newLeft, newRight);
}

// discard even lefts and sum remaining rights
decimal answer = (from g in steps
where g.Left % 2 != 0
select g.Right).Sum();

Console.WriteLine("Answer is: {0}", answer);

Console.ReadLine();
}

class Gimley
{
public int Left { get; set; }
public int Right { get; set; }

public Gimley(int left, int right)
{
Left = left;
Right = right;
}
}
}
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:11 • by Jürgen (unregistered)
278109 in reply to 278096
Alex thats nice, and very similiar to my ruby/python versions, except where summarization occurs.

I didn't bother with the 3rd acc parameter because
ruby/python don't do tail-end optimization on recursive calls any way.

That's probably why many diss recursive solutions,
but my profiler tells me theres little difference especially if you compare to solutions using python list comprehensions or ruby's .each iteration.


Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:11 • by Anonymous (unregistered)
278110 in reply to 278099
NO U!

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:12 • by Rob W. (unregistered)
#!/usr/bin/env python
import sys

try:
sys.argv[1]
sys.argv[2]
except IndexError:
numbers = raw_input("Please enter the two integers you wish to multiply separated by a space: ").split(' ')
else:
numbers = sys.argv[1:3]

left = int(numbers[0].strip())
right = int(numbers[1].strip())
product = 0


while left != 0:
if left % 2 != 0:
product += right
left /= 2
right*= 2

print "The product of " + numbers[0].strip() + " x " + numbers[1].strip() + " is " + str(product)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:13 • by serg (unregistered)
Some thoughts...

------------8<-------------------
int mult(int a, int b) {
int result = 0;

while(a) {
if(a & 0x01) {
result += b;
}

a >>= 1;
b <<= 1;
}

return result;
}
------------8<-------------------
int mult2(int a, int b) {
int result = 0;

if(a != 0) {
result = mult2(a >> 1, b << 1);

if(a & 0x01) {
result += b;
}
}

return result;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:13 • by Jannik Jochem (unregistered)
My functional-style java version...


public static int multiply(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == 1)
return b;
else
return multiply(a/2, b*2) + ((a % 2 == 1) ? b : 0);
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:14 • by Osno (unregistered)
278116 in reply to 278095
All the people who don't know what an optimizing compiler is also fail.


So you're basically agreeing with the " a * b " solution? Because defining multiplication by using multiplication is kind of weird (ok, I agree is in the spec, but anyway).

And no, when you're using rounding in vb.net (or the "\" operator) I can assure you that doesn't get optimized. And C# doesn't get optimized, at least not in IL (but maybe at the JIT level).

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:14 • by wolf550e (unregistered)
http://www.phy6.org/outreach/edu/roman.htm

This is not a Russian method but an ancient Roman one.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:17 • by tirerim
#!/usr/bin/perl

use integer;($a,$b)=@ARGV;while($a){$a%2and$r+=$b;$a/=2;$b*=2;}print $r;


I admit that this takes a bit of a shortcut: it checks each pair of numbers as it comes up, and adds the second to the result if necessary at that time, rather than saving them all and waiting for the end.

For anyone who really likes whitespace:

#!/usr/bin/perl
use integer;
($a, $b) = @ARGV;
while ($a) {
$a % 2 and $r += $b;
$a /= 2;
$b *= 2;
}
print $r;

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:17 • by SimonY (unregistered)
let peasant a b =
let rec peasant a b acc =
if a = 1 then b + acc else
match a%2 with
| 0 -> peasant a/2 b*2 acc
| 1 -> peasant a/2 b*2 acc+b
in peasant a b 0

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:18 • by Dave Havlicek (unregistered)
ruby:

class Fixnum


def *(num)
cols = Array.new
cols.push([self, num])
while cols.last[0] != 1 do
cols.push([cols.last[0] / 2, cols.last[1] + cols.last[1]])
end
cols.inject(0) { |sum, n| (n[0] % 2 == 1) ? sum + n[1] : sum }
end
end

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:19 • by Thuktun
Well, that's freakishly easy.

public class RussianPeasantMultiplication {

public static int multiply(int left, int right) {
int sum = 0;
while (left > 0) {
System.out.println("left=" + left + " right=" + right);
if ((left & 1) == 1) { // if odd
sum += right; // collect this row
}
left >>= 1; // divide by two
right <<= 1; // multiply by two
}
return sum;
}

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

left=18 right=23
left=9 right=46
left=4 right=92
left=2 right=184
left=1 right=368
result=414

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:23 • by JoLoCo (unregistered)
Here, for the sake of it, is a Sinclair BASIC version.


10 LET a=18: LET b=23
20 LET tot=0
30 IF a<0 THEN LET a=0-a: LET b=0-b
40 IF (a/2) <> INT (a/2) AND a>0 THEN LET tot=tot+b
50 LET a= INT (a/2)
60 LET b=b*2
70 IF a>0 THEN GO TO 40
80 PRINT tot


Is this the first entry to feature line numbers?

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:23 • by Patrick Simpson (unregistered)
An F# quicky:

let rec RussianPeasantMultiplication a b = 

if a < 0 then -(RussianPeasantMultiplication (-a) b)
else (if a % 2 = 1 then b else 0) + (if a > 1 then RussianPeasantMultiplication (a / 2) (b * 2) else 0)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:24 • by idle (unregistered)
untested Java, quick and dirty...

public static int mult(int x, int y){

Integer x1 = new Integer(x);
int result = 0;

for(int i = 0; i < Integer.toBinaryString(x1).length(); i++){
if(Integer.toBinaryString(x1).endsWith("1"))
result += y * (int)Math.pow(2, i);
x1 = Integer.rotateRight(x1, 1);
}
return result;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:25 • by 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.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:25 • by Noah Easterly (unregistered)
Haskell:


let peasantMultiply a b = f a b 0
where f a b s | a < 0 = f (negate a) (negate b) s
| a == 0 = s
| otherwise =
let (a',r) = a `divMod` 2 in
f a' (2*b) (if r == 1 then s + b else s)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:26 • by klagdon (unregistered)
Accounts for either argument being zero, also throws an exception if trying to multiply a negative number. Tested with given main() method

public static long multiply(long first, long second) {
if(first < 0 || second < 0) {
throw new IllegalArgumentException("May only multiply positive numbers");
} else if(first == 0 || second == 0) {
return 0;
} else if(first == 1) {
return second;
} else if(first % 2 == 1) {
return second + multiply(first / 2, second * 2);
} else {
return multiply(first / 2, second * 2);
}
}

public static void main(String[] args) {
Random r = new Random();
for(int i = 0 ; i < 1000000 ; i++) {
long first = (long)Math.abs(r.nextInt());
long second = (long)Math.abs(r.nextInt());
if((first * second) != multiply(first,second)) {
System.out.println("Failed for " + first + " * " + second + "\t" + (first * second) + "\t" + multiply(first,second));
}
}
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:26 • by Chad M (unregistered)

def russian_mult(l, r):
"""Use Russian-peasant multiplication method. They don't understand zero
or negative numbers very well, according to the description. We fix that
with simple rules. If left side has negative sign, change sign of result. tdwtf at chad org
"""

rows = list()
rows.append((l, r))
while abs(l) > 1:
l = l // 2
r = r * 2
rows.append((l, r))

if l < 0:
return 0 - sum(r for l, r in rows if l%2==1)
else:
return sum(r for l, r in rows if l%2==1)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:26 • by Dave van der Brugge (unregistered)
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)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:28 • by jjs105 (unregistered)

function russian_multiply_true_lookup (left, right) {

if (left == 0) return 0;
if (left == 1) return right;

var lookup = [{left: left, right: right}];

while (left > 1) {
left = Math.floor(left / 2);
right = right * 2;
lookup.push({left: left, right: right});
}

var result = 0;

for (var index = 0; index < lookup.length; index++)
if (lookup[index].left % 2 == 1)
result += lookup[index].right;

return result;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:29 • by darklajid
Forget about the sticker, I played a lot with F# today. Thanks for the motivation.


let russianMultiplication x y =
let rec l a b = seq { yield (a, b); yield! l (a>>>1) (b<<<1) }
l x y |> Seq.takeWhile (fun c -> fst c > 0) |> Seq.fold (fun acc (x,y) ->
if x % 2 = 1 then acc + y else acc
) 0

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:31 • by imhe
Accounts for 0 and negative numbers, tested with main
//Earlier posted as guest, now posting as member}

package com.timepass;

public class RussianMultiply {

private int mulTotal = 0;
private boolean isMulTotalNegative = false;
RussianMultiply(){
super();
}
private void multiply(int first,int second, boolean isFirstTime){
// if any number 0 return
if(first == 0 || second ==0){
return;
}
//check for negative numbers
if(isFirstTime){

if(first < 0 && second < 0) {
isMulTotalNegative = false;
first = first*-1;
second = second * -1;
}
if(first < 0){
isMulTotalNegative = true; first = first*-1;
}
if(second < 0){
isMulTotalNegative = true;second = second * -1;
}
}
// first time and odd number add to total
if(isFirstTime && first%2!=0){
mulTotal = mulTotal + second;
}

// 1st column not even , add to total
int tempFirst = first/2;
int tempSecond = second*2;
if(tempFirst%2!=0){
mulTotal = mulTotal + tempSecond;
}
// first colum not 1, do it again
if(tempFirst != 1){
multiply(tempFirst,tempSecond,false);
}
}
public void multiply(int first,int second){
multiply(first,second,true);
}

public void clearMulTotal(){
setMulTotal(0);
}

public int getMulTotal() {
if(isMulTotalNegative()){
return -1*this.mulTotal;
}
return this.mulTotal;
}
public void setMulTotal(int mulTotal) {
this.mulTotal = mulTotal;
}


/**
* @param args
*/
public static void main(String[] args) {
RussianMultiply rm = new RussianMultiply();

rm.clearMulTotal();
rm.multiply(18, 23);
System.out.println("Multiplication of 18 and 23:" + rm.getMulTotal());

rm.clearMulTotal();
rm.multiply(13, 12);
System.out.println("Multiplication of 13 and 12:" + rm.getMulTotal());

rm.clearMulTotal();
rm.multiply(12, 12);
System.out.println("Multiplication of 12 and 12:" + rm.getMulTotal());

rm.clearMulTotal();
rm.multiply(-12, -12);
System.out.println("Multiplication of -12 and -12:" + rm.getMulTotal());

rm.clearMulTotal();
rm.multiply(-12, 12);
System.out.println("Multiplication of -12 and 12:" + rm.getMulTotal());

}
public boolean isMulTotalNegative() {
return isMulTotalNegative;
}
// public void setMulTotalNegative(boolean isMulTotalNegative) {
// this.isMulTotalNegative = isMulTotalNegative;
// }


}



Multiplication of 18 and 23:414
Multiplication of 13 and 12:156
Multiplication of 12 and 12:144
Multiplication of -12 and -12:144
Multiplication of -12 and 12:-144

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 12:32 • by Codism (unregistered)
Yet another Linq solution:
public static int rpm(int a, int b)
{
return Enumerable.
Range(0, a < 2 ? 1 : (int)Math.Ceiling(Math.Log(a % 2 == 0 ? a + 1 : a, 2)))
.Select(i => new { L = a / (1 << i), R = b * (1 << i) })
.Where(x => x.L % 2 != 0).Sum(x => x.R);
}
« PrevPage 1 | Page 2 | Page 3 | Page 4 | Page 5 | Page 6 | Page 7 | Page 8 | Page 9 | Page 10 | Page 11 | Page 12 | Page 13 | Page 14 | Page 15 | Page 16Next »

Add Comment