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 20:19 • by Twey (unregistered)
This is, of course, a one- or two-liner (depending how long you like your lines) in Haskell and probably most other functional languages:


-- Just for neatness; without this, ((`div` 2) *** (* 2)) can be
-- written (\(a, b) -> (a `div` 2, b * 2))
import Control.Arrow ((***))

rus n m = sum . map snd . filter ((/= 0) . (`mod` 2) . fst)
. takeWhile ((> 0) . fst) $ iterate ((`div` 2) *** (* 2)) (n, m)


Or adding some labels for clarity:


rus n m = sum . rightColumn . filter hasOddRight
. takeWhile nonZeroLeft $ makeColumns (n, m)
where rightColumn = map snd
hasOddRight = (/= 0) . (`mod` 2) . fst
makeColumns = iterate multiplyAndDivide
multiplyAndDivide = ((`div` 2) *** (* 2))
nonZeroLeft = ((> 0) . fst)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:22 • by Mike McNally (unregistered)
278440 in reply to 278434
oops the last 2 lines are busted (great idea to refactor just before posting :-)


rsum([M, N} | P], S) ->
rsum(P, S + case M rem 2 of 0 -> 0; 1 -> N end).

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 20:34 • by tdh (unregistered)
Not the shortest or simplest bit of code, but a pretty elegant way of mirroring the Russian Peasant method, as opposed to looking more like binary multiplication.

Python:

def multiply(a, b):
def pairs():
nonlocal a, b
while a:
yield a, b
a //= 2
b *= 2
return sum(j for (i, j) in pairs() if i % 2)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:19 • by brian (unregistered)
I'm sure this is lost in the haze:

int peasant(int x, int y)
{
int result = 0;

do
{
result += (x % 2) * y;
x /= 2;
y *= 2;
}
while(x > 0);

return result;
}

Didn't bother with bitshifting. Looking at the generated assembly is an interesting excersize.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:25 • by 0ffh (unregistered)
I feel daring today and throw this in untested.
thx for spoiler alert i did it in a text editor
before scrolling down to comment. =)

// russian multiply
// the usual limitations on result size apply
int ru_mul(int fac0,int fac1) {
int prod=0;
do {
prod+=(fac0&1)*fac1;
fac1<<=1;
} while (fac0>>=1);
return prod;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:27 • by 0ffh (unregistered)
the wtf is of course that my spaces got eaten... =)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:35 • by Bob (unregistered)
echo "In soviet russia, multiplication does YOU!"

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 21:48 • by 0ffh (unregistered)
nah, the real wtf is:
ye shouldnae do sucha thing that i did there:
late night surfing on coding sites while not sober.
speaking of test-driven development, hihi!
i inadvertedly coded for unsingeds...
take brians solution!

Yet another C# version, with tests

2009-07-22 21:50 • by Thomas Eyde (unregistered)

using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace RussianPeasantMultiplication
{
/// <summary>
/// The biggest WTF, of course, is there are tests!
/// </summary>
[TestClass]
public class Multiply_numbers
{
[TestMethod]
public void Multiply_some_numbers()
{
Assert.AreEqual(18*23, WtfPeasantCalculator.Multiply(18, 23));
Assert.AreEqual(0*1, WtfPeasantCalculator.Multiply(0, 1));
Assert.AreEqual(1*0, WtfPeasantCalculator.Multiply(1, 0));
Assert.AreEqual(11*13, WtfPeasantCalculator.Multiply(11, 13));
}

[TestMethod]
public void Multiply_with_cryptic_version()
{
Assert.AreEqual(18*23, CrypticPeasantCalculator.Multiply(18, 23));
}
}

/// <summary>
/// What kind of entry would it be, if the expected code quality wasn't posted?
/// </summary>
internal static class CrypticPeasantCalculator
{
public static long Multiply(int a, int b)
{
return a < 1 ? 0 : (a%2 != 0 ? b : 0) + Multiply(a/2, b*2);
}
}

/// <summary>
/// Another WTF is to actually try to write readable, understandable code.
/// </summary>
internal static class WtfPeasantCalculator
{
public static long Multiply(int a, int b)
{
if (ThereIsNothingLeftToAccumulate(a)) return 0;
return ValueToAccumulate(a, b) + FollowingAccumulatedValues(a, b);
}

private static bool ThereIsNothingLeftToAccumulate(int a)
{
return a < 1;
}

private static int ValueToAccumulate(int a, int b)
{
return IsOddNumber(a) ? b : 0;
}

private static bool IsOddNumber(int number)
{
return number%2 != 0;
}

private static long FollowingAccumulatedValues(int a, int b)
{
return Multiply(a/2, b*2);
}
}
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:00 • by Mr.'; Drop Database -- (unregistered)
def russianpeasants(x, y):

print 'Useless waste of time. Any idiot could write this.'

def multiply(x, y):
if x < 0 and y < 0: x = -x; y = -y
elif x < 0 or y < 0: return -multiply(abs(x), abs(y))
if x == 0 or y == 0: return 0
if x == 1 or y == 1: return x+y-1
bits = 0; tempx = x; tempy = y
while tempx: tempx >>= 1; bits += 1
while tempy: tempy >>= 1; bits += 1
bits >>= 2
a = x >> bits; b = x & ((1 << bits) - 1)
c = y >> bits; d = y & ((1 << bits) - 1)
ac = multiply(a, c); bd = multiply(b, d)
abcd = multiply(a+b, c+d)
return (bd
+ ((abcd - bd - ac) << bits)
+ (ac << (bits + bits)))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:18 • by bluebearr (unregistered)
Got to add AutoIt:

Func _RussianMultiplication( $var1, $var2)

Dim $iResult=0, $iLeft = $var1, $iRight = $var2
While Abs($iLeft) >= 1
If StringInStr("13579", StringRight($iLeft, 1)) > 0 Then $iResult+=$iRight
$iLeft = Int($iLeft/2)
$iRight *= 2
WEnd
If $var1 < 0 Then $iResult *= -1
Return $iResult
EndFunc

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:22 • by Joel (unregistered)
Short recursive C# technique:

int Russian(int left, int right, int progress){

if(x==0) return progress;
return Russian(left/2, right*2, progress+((left%2==1)?right:0));
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:44 • by Bruce (unregistered)
278464 in reply to 277748
This actually misses adding the first row if the initial lval is odd.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:46 • by Bruce (unregistered)
278466 in reply to 278464
(sorry, I meant the first sample given)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 22:51 • by J (unregistered)
Tail-recursive Mathematica implementation:

RussianPeasantTimes[x_Integer, y_Integer] :=
Sign[x] RussianPeasantTimesImpl[Abs[x], y, 0];

RussianPeasantTimesImpl[x_, y_, res_] :=
RussianPeasantTimesImpl[Quotient[x, 2], 2 y, res + Mod[x, 2] y];
RussianPeasantTimesImpl[1, y_, res_] := res + y;
RussianPeasantTimesImpl[0, _, res_] := res;

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:14 • by noSignal (unregistered)
Scheme:

(define peasant
(lambda (x y)
(letrec
((loop
(lambda (ls1 ls2)
(if (eq? (car ls1) 1)
(apply + (select odd? ls1 ls2))
(loop (cons (quotient (car ls1) 2) ls1) (cons (* 2 (car ls2)) ls2))))))
(loop (list x) (list y)))))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:17 • by noSignal (unregistered)
278470 in reply to 278370
I salute you sir!

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:17 • by joeyadams
I found a neat little trick to it. See if you can figure out what I did ;-) :

uint32_t multiply(uint32_t a, uint32_t b) {

uint64_t ab = 0;
uint32_t r = 9;
while (--r) {
ab <<= 4;
ab |= ((0xf7b3d591e6a2c480ULL>>((a&0xF)<<2)) & 0xF);
a >>= 4;
}
ab <<= 32;
ab |= b;
while (ab >> 32) {
if (ab >> 63)
r += ab;
ab <<= 1;
ab &= 0xFFFFFFFEFFFFFFFFULL;
}
return r;
}


I stress tested this (with 100 million random trials against the * operator) on an x86 and a PPC machine, so it works, trust me.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:20 • by noSignal (unregistered)
278472 in reply to 278471
You spent more than 5 minutes on a 3 minute problem. Congratulations.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:25 • by jnz
Here's a version in C that multiplies two 8-bit numbers and produces a 16-bit result. It requires a 64-bit unsigned type. I know it doesn't look much like the original algorithm but that's because it treats the 64-bit variables as an array of 8-bit values that can be operated on in parallel.

unsigned int mult(unsigned char a, unsigned char b)

{
uint64_t x, y;

x = a; y = b;
x |= x << 7; y |= y << 8;
x |= x << 14; y |= y << 16;
x |= x << 28; y |= y << 32;

x &= 0x0101010101010101ULL;
x = (0x8080808080808080ULL - x) ^ 0x8080808080808080ULL;
x &= y;

x = (x & 0x00FF00FF00FF00FFULL) + ((x & 0xFF00FF00FF00FF00ULL) >> 7);
x = (x & 0x0000FFFF0000FFFFULL) + ((x & 0xFFFF0000FFFF0000ULL) >> 14);
x = (x & 0x00000000FFFFFFFFULL) + ((x & 0xFFFFFFFF00000000ULL) >> 28);

return (unsigned int)x;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:28 • by JXO (unregistered)
C code. FACTOR can be changed to another integer > 1 without breaking the code.

#define FACTOR 2
unsigned int ruski_mul(unsigned int a, unsigned int b)
{
unsigned int result = 0;
while (a >= 1)
{
result += (a % FACTOR) * b;
a /= FACTOR;
b *= FACTOR;
}
return result;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-22 23:45 • by zcl (unregistered)

Yes ,your article is very good, we have the same belief with you,so let me introduce the area to you.Now Juicy Jewelry become more adn more popular within all kind of people. Juicy couture is a kind of juicy series . It won a good reputation. Juicy sale often held its regular discount juicy activities,such as juicy charms,cheap juicy and so on.In these activities juicy couture sale got great success. juicy couture consists of two main aspects, juicy couture jewelry and juicy couture accessories
Juicy couture series are worthwhile than other juicy on sales. They have a lot of discounted jewelry,for example discount Juicy Couture necklaces, juicy earrings , juicy bracelets and rings on sale. Benefit from the discount,you can get juicy jewelry save up to 30%, We assure you of our best services at all times.

Re: Programming Praxis: Russian Peasant Multiplication [JavaScript implementation]

2009-07-23 00:14 • by Chris (unregistered)
Here my implementation i JavaScript (yeah, I know, not a programming language :D )

Ok, the WTF is also that it doesn't work in IE, and looks funny in Opera. And that it's a bit long, not because of the calculation, but because of the whizbang :)


<script language="JavaScript">
function PeasantMultiply()
{
var one = Math.round(document.getElementById("first_value").value * 1);
var two = Math.round(document.getElementById("second_value").value * 1);
var mytable = document.getElementById("my_table");
var columns = 1;
var rows = 1;
var newRow = null;
var newCell = null;
var rowIndices = new Array();
var addValues = new Array();
if (one < 1 || two < 1)
{
alert ("Russian Peasants only knew how to multiply positive integer numbers!");
return false;
}
mytable.innerHTML = "";
newRow = document.createElement("tr");
newCell = document.createElement("td");
newCell.innerHTML = one + "&nbsp;*&nbsp;" + two;
newRow.appendChild(newCell);
mytable.appendChild(newRow);
if (one % 2)
{
rowIndices.push(true);
addValues.push(two);
}
else
{
rowIndices.push(false);
addValues.push(0);
}
while (true)
{
one >>= 1;
if (one <= 0) break;
two *= 2;
if (one % 2)
{
rowIndices.push(true);
addValues.push(two);
}
else
{
rowIndices.push(false);
addValues.push(0);
}
newCell = document.createElement("td");
newCell.innerHTML = one + "<span style='float:right'>" + two + "</span>";
newRow = document.createElement("tr");
for (r=null, i=0; i < mytable.getElementsByTagName("tr").length; i++)
{
r = mytable.getElementsByTagName("tr")[i];
//window.alert(r.innerHTML);
r.appendChild(r.lastChild.cloneNode(true));
}
for (var i=0; i < columns; i++)
{
newRow.appendChild(document.createElement("td"));
}
//window.alert("hello world 3");
newRow.appendChild(newCell);
//window.alert("almost done!");
mytable.appendChild(newRow);
columns++; rows++;
}
var first = true;
for (r=null, i=0; i < mytable.getElementsByTagName("tr").length; i++)
{
r = mytable.getElementsByTagName("tr")[i];
newCell = r.lastChild.cloneNode(true);
if (!(rowIndices[i]))
newCell.innerHTML = "<strike>" + newCell.innerHTML + "</strike>";
r.appendChild(newCell);
newCell = document.createElement("td");
if (rowIndices[i])
{
newCell.innerHTML = addValues[i];
if (!first) newCell.innerHTML = "+ " + newCell.innerHTML;
newCell.innerHTML = "<span style='float:right'>" + newCell.innerHTML + "</span>";
first = false;
}
else
newCell.innerHTML = "&nbsp;";
r.appendChild(newCell);
}
newCell = document.createElement("td");
newCell.setAttribute( "rowspan", rows);
newCell.setAttribute("style", "vertical-align:middle; padding-left:5px; padding-right: 5px;");
newCell.innerHTML = "=";
mytable.firstChild.appendChild(newCell);

newCell = document.createElement("td");
newCell.setAttribute( "rowspan", rows);
newCell.setAttribute("style", "vertical-align:middle; padding-left:5px; padding-right: 5px;");
newCell.innerHTML = eval(addValues.join(" + "));
mytable.firstChild.appendChild(newCell);

return false;
}
</script>

<style type="text/css">
td {
border: 1px solid black;
padding: 2px;
}
</style>

<form>
Multiply: <input type="text" id="first_value" />
By: <input type="text" id="second_value" />
<input type="button" value="using russian peasant multiplication" onClick="javascript:PeasantMultiply(); return false;" />
</form>

<table id="my_table" style="border: 1px solid black; border-collapse: collapse; font-family: Arial,Helvetica;">
<tr id="row_0">
<td id="cell_0_0">
Russian Peasant Multiplication
</td>
</tr>
</table>

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:33 • by Julian Calaby (unregistered)
Bash: abusing the arithmetic evaluation to fit the bulk of the algorithm on one line. (Everything except the line starting with echo is to handle the first argument being negative.)

#! /bin/bash


if [ $1 -lt 0 ]; then
$0 $(( $1 * -1 )) $(( $2 * -1 ))
else
echo $(( $([ $(($1 & 1)) -eq 1 ] && echo $2 +) $(if [ $1 -gt 1 ]; then $0 $(($1 >> 1)) $(($2 << 1)); else echo 0; fi) ))
fi


Remove the outermost arithmetic brackets on the second last line to see the working.

(Note that this doesn't work unless it's in an actual script file and called as such)

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:37 • by cmugford
Couldn't see if this had been done - but anyway how about some F#.

let rec multiply x y = match x with
| 0 -> 0
| 1 -> y
| -1 -> -y
| x when x % 2 = 0 -> multiply (x / 2) (y * 2)
| x when x > 0 -> y + multiply (x / 2) (y * 2)
| x when x < 0 -> -y + multiply (x / 2) (y * 2);

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:50 • by James (unregistered)
278489 in reply to 277748

If you've got a copy of Excel you can always do it this way, and lets face if, if you've got Excel why wouldn't you?

-----
Sub WhyOhWhy()
Dim iRowNo As Integer
Dim sValue As String

iRowNo = 2

sValue = InputBox("Enter first value to mulitply", "Peasant Multiply")
If sValue = "" Then
MsgBox "You're not playing the game..."
Do Until sValue <> ""
sValue = InputBox("Enter first value to mulitply", "Peasant Multiply")
If Not IsNumeric(sValue) Then
MsgBox "You're not playing the game..."
sValue = ""
Else
If CLng(sValue) > 33554431 Then
MsgBox "Upper limit on first number is 33,554,431"
sValue = ""
End If
End If

Loop
End If
Cells(iRowNo, 3).Value = CLng(sValue)

sValue = InputBox("Enter second value to mulitply", "Peasant Multiply")
If sValue = "" Then
MsgBox "You're not playing the game..."
Do Until sValue <> ""
sValue = InputBox("Enter second value to mulitply", "Peasant Multiply")
If Not IsNumeric(sValue) Then
MsgBox "You're not playing the game..."
sValue = ""
End If
Loop
End If
Cells(iRowNo, 4).Value = CLng(sValue)

Cells(iRowNo, 3).Interior.ColorIndex = 36
Cells(iRowNo, 4).Interior.ColorIndex = 36
Cells(iRowNo, 5).Interior.ColorIndex = 45
Cells(iRowNo, 5).FormulaR1C1 = "=SUM(R[1]C:R[24]C)"

iRowNo = iRowNo + 1
Cells(iRowNo, 3).Value = Cells(iRowNo, 3).Value
Cells(iRowNo, 4).Value = Cells(iRowNo, 4).Value
Cells(iRowNo, 5).FormulaR1C1 = "=IF(RC[-2]<>"""",IF(MOD(RC[-2],2)<>0,RC[-1],0),"""")"

For iRowNo = 3 To 26
Cells(iRowNo, 3).FormulaR1C1 = "=IF(OR(R[-1]C=1,R[-1]C=""""),"""",INT(R[-1]C/2))"
Cells(iRowNo, 4).FormulaR1C1 = "=IF(RC[-1]<>"""",R[-1]C*2,"""")"
Cells(iRowNo, 5).FormulaR1C1 = "=IF(RC[-2]<>"""",IF(MOD(RC[-2],2)<>0,RC[-1],0),"""")"
Next iRowNo
MsgBox "There you go, the answer is " & Format(Cells(2, 5).Value, "#,##0")
End Sub

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:56 • by iamtim2 (unregistered)
278491 in reply to 277783
In Newlisp. I came up with & on my own but after reading Tim's version, I used >> and <<. Mine's tested.

; odd? (= (& col1 1) 1) instead of (= (% col1 2) 0)
; half! (>> col1 1) instead of (/ col1 2)
; double! (<< col2 1) instead of (* col2 2)
; because %, / and * are expensive

(define (rus col1 col2)
(let ((t 0))
(do-until (< col1 1)
(if (= (& col1 1) 1)
(setq t (+ col2 t)))
(println col1 " x " col2)
(set 'col1 (>> col1 1) 'col2 (<< col2 1)))
(println t)))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 00:59 • by jvmbsd7 (unregistered)
278493 in reply to 278491
;; Scheme using the design recipe and optimized for lowest number of iterations

(define (russian-multiply m n)
(define (russian-multiply* x y p)
(if (zero? x)
p
(russian-multiply* (quotient x 2) (+ y y) (if (odd? x) (+ p y) p))))
(if (< m n)
(russian-multiply* m n 0)
(russian-multiply* n m 0)))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 01:29 • by agrif (unregistered)
these are all in python

the first is the most verbose:

def russian(x, y):
def generate_list(x, y):
while x != 0:
yield x, y
x /= 2
y *= 2

def filter_even(i):
if i[0] % 2 == 0:
return False
return True

def drop_first_column(i):
return i[1]

l = generate_list(x, y)
l = filter(filter_even, l)
l = map(drop_first_column, l)
return sum(l)

The next one is less verbose, but still easy to follow:

def russian(x, y):
l = []
while x != 0:
if x % 2:
l.append(y)
x /= 2
y *= 2
return sum(l)

Personally, I like this one for it's complete incomprehensibility (and that it says "lambda f,a,b:a", which makes me laugh):

russian = lambda x,y:(lambda f:f(f,x,y))(lambda f,a,b:a and f(f,a/2,b*2)+a%2*b)

agrif - 71aaeb8b415a620bf185b6093ebaf5c5

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 01:35 • by Chris Walton (unregistered)
No branches in the innerloop. Should run pretty fast.

C-version:

int russianMul(int a, int b)
{
int s = 0;
while(a > 1)
{
b <<= 1;
a >>= 1;
s += b & -(a & 1);
}
return s;
}


x86 Assembly version, as compiled by MSVC

00401000 xor eax,eax
00401002 cmp ecx,1
00401005 jle russianMul+1Dh (40101Dh)
00401007 push esi
00401008 sar ecx,1
0040100A mov esi,ecx
0040100C and esi,1
0040100F add edx,edx
00401011 neg esi
00401013 and esi,edx
00401015 add eax,esi
00401017 cmp ecx,1
0040101A jg russianMul+8 (401008h)
0040101C pop esi

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 01:38 • by arke
278501 in reply to 278499
Chris Walton:
...


Oops, I probably should have logged in. :)

Something to add - my version doesn't need the actual CPU's multiply or divide instructions, making it feasible to implement on some processor that doesn't have that. Also, in its current incarnation, it depends on 2's Complement numbers being used.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:11 • by sxeraverx
int mult(int a, int b) { return a*b; }
/*because that's how computers do it in hardware, anyway.*/

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:14 • by Mr M (unregistered)
278506 in reply to 277818
The question is, why would I want to?

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:23 • by Philipp (unregistered)
278510 in reply to 278037
Qwertyuiopas:
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.

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


Ok, so how do I run that? I tried the "Brainfuck Interpreter" (http://koti.mbnet.fi/villes/php/bf.php), but I couldn't get any meaningful result. How do I set the input?

Otherwise: Coolest solution so far -- imho.

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:28 • by joeyadams
278513 in reply to 278477
zcl:

Yes ,your article is very good, we have the same belief with you,so let me introduce the area to you.Now Juicy Jewelry become more adn more popular within all kind of people. Juicy couture is a kind of juicy series . It won a good reputation. Juicy sale often held its regular discount juicy activities,such as juicy charms,cheap juicy and so on.In these activities juicy couture sale got great success. juicy couture consists of two main aspects, juicy couture jewelry and juicy couture accessories
Juicy couture series are worthwhile than other juicy on sales. They have a lot of discounted jewelry,for example discount Juicy Couture necklaces, juicy earrings , juicy bracelets and rings on sale. Benefit from the discount,you can get juicy jewelry save up to 30%, We assure you of our best services at all times.


Can we please end the off-topic rants about Russian peasant multiplication and get back to our juicy jewelry discussion?

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:32 • by Alex Muscar (unregistered)
Common Lisp:

This time it does the expected thing when the first number is negative instead of looping forever :)


(defun rpm4 (m n &optional (acc 0))
(do ((aux (abs m) (ash aux -1)))
((= aux 0) (if (< m 0) (- 0 acc) acc))
(incf acc (if (oddp aux) n 0))
(incf n n)))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 02:45 • by Alex Muscar (unregistered)
Common Lisp:


(defun rpm4 (m n)
(do ((t1 (abs m) (ash t1 -1))
(t2 n (ash t2 1))
(acc 0 (+ acc (if (oddp t1) t2 0))))
((= t1 0) (if (< m 0) (- 0 acc) acc))))

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:08 • by mneimeyer
This feels a little "me too" at this point but I've tried to follow all the "rules".

Here's PHP that accounts for negative numbers, doesn't use * or /, accounts for 0 in either position and generates nifty colored output.

<?php

function Russian($a,$b)
{
echo "\n<tr bgcolor='".($a&1?"green":"red")."'><td>".$a."</td><td>".$b."</td></tr>";
if(!$a || !$b) { return 0; }
if($a < 0) { $a = ($a^-1)+1; $b = ($b^-1)+1; }
return (($a <= 1)?($a?$b:0):((intval($a&1)?$b:0)+Russian(intval($a>>1),$b<<1)));
}

?><html>
<head><title>Russian Peasant</title></head>
<body>

<form method="get">
<table border="0" align="center" cellspacing="0" cellpadding="5">
<tr>
<td><input type="text" size="4" name="a" value="<?= $_GET['a'] ?>"></td>
<td>&nbsp;x&nbsp;</td>
<td><input type="text" size="4" name="b" value="<?= $_GET['b'] ?>"></td>
<td><input type="submit" value="Multiply"></td>
</tr>
</table>
</form>

<?php

if(isset($_GET['a']) && isset($_GET['b']))
{
echo "\n<p align='center'>Quick: ".($_GET['a']*$_GET['b'])."</p>\n";

echo "<table border='0' align='center'>\n";
$c = Russian($_GET['a'],$_GET['b']);
echo "\n<tr><td>Sum:</td><td>".$c."</td></tr>";
echo "</table>\n";
}

?>

</body>
</html>

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:14 • by Hidayat (unregistered)
Another using Oracle PL/SQL

create or replace

function russian(p in number, q in number) return number is
res number;
begin
select sum( decode(mod(floor(p/power(2,level-1)),2),0,0,1) * q * power(2,level-1) ) into res
from dual where floor(p/power(2,level-1))>0 connect by level<q;
return res;
end;

select russian(18,23) from dual

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:15 • by demo (unregistered)
#include <iostream>

template<int I>
struct is_odd
{
enum { value = I % 2 };
};

template<int A, int B, int Odd>
struct russian_impl;

template<int A, int B>
struct russian_impl<A, B, 1>
{
enum { value = B + russian_impl<A/2, B*2, is_odd<A/2>::value>::value };
};

template<int A, int B>
struct russian_impl<A, B, 0>
{
enum { value = russian_impl<A/2, B*2, is_odd<A/2>::value>::value };
};

template<int B>
struct russian_impl<1, B, 1>
{
enum { value = B };
};

template<int A, int B>
struct russian
{
enum { value = russian_impl<A, B, is_odd<A>::value>::value };
};

int main(int argc, char* argv[])
{
std::cout << russian<18, 23>::value << std::endl;
return EXIT_SUCCESS;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:56 • by Don Knisley (unregistered)
In VBA

Function RussianPeasantMultiplication()
Dim a As Integer, b As Integer, c As Integer
a = 18
b = 23
Debug.Print a & " x " & b
Do Until a = 1
a = Int(a / 2)
b = b * 2
If a / 2 <> Int(a / 2) Then
c = c + b
Debug.Print a & vbTab & b & vbTab & b
Else
Debug.Print a & vbTab & b
End If
Loop
Debug.Print vbTab & vbTab & c
End Function

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 03:59 • by SlyEcho
CREATE FUNCTION Peasant_Mul (@A INT, @B INT)
RETURNS INT
AS
BEGIN
    DECLARE @Result INT;
    WITH f AS (
        SELECT @A A, @B B
        UNION ALL
        SELECT A / 2, B * 2 FROM f WHERE A > 1
    )
    SELECT @Result = SUM(B) FROM f
    WHERE A % 2 = 1;

    RETURN @Result;
END
GO

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:04 • by subanark
Here is my solution in Java. It supports really big numbers and does pretty much what you do in Russian peasant multiplication.

public static BigInteger multiply(BigInteger a, BigInteger b)
{
BigInteger two = BigInteger.valueOf(2);
ArrayList<BigInteger> numsToAdd = new ArrayList<BigInteger>();
while(!a.equals(BigInteger.ONE))
{
if(a.mod(two).equals(BigInteger.ONE))
numsToAdd.add(b);
a = a.divide(two);
b = b.multiply(two);
}
//trick: b already holds the last line
for(BigInteger n : numsToAdd)
b = b.add(n);
return b;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:07 • by Toby Gray (unregistered)
In Perl:

print "Enter sum in form \"a x b\":\n";$_=<>;
s!(\n|^)(\d+) x (\d+)\n$!"$1$2 x $3\n".int(($2)/2)." x ".($3 * 2)."\n"!e while!/^1 x \d+$/m;
s!(\n|^)(\d*[24680]) x (\d+)!$1-($2 x $3)-!g;
$v+=$2 while/(\n|^)\d+ x (\d+)/g;$_.="\nTotal: $v\n";
print "Paper working is:\n$_";

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:10 • by freewildebeest
Repost now I've worked out how to create an account...

In Perl:

print "Enter sum in form \"a x b\":\n";$_=<>;
s!(\n|^)(\d+) x (\d+)\n$!"$1$2 x $3\n".int(($2)/2)." x ".($3 * 2)."\n"!e while!/^1 x \d+$/m;
s!(\n|^)(\d*[24680]) x (\d+)!$1-($2 x $3)-!g;
$v+=$2 while/(\n|^)\d+ x (\d+)/g;$_.="\nTotal: $v\n";
print "Paper working is:\n$_";

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:15 • by astander (unregistered)
private int RussianMultiply(int input1, int input2)
{
int retVal = 0;
do
{
retVal += (input1 & 1) * input2;

input1 = input1 >> 1;
input2 = input2 << 1;

} while (input1 > 0);
return retVal;
}

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:45 • by k1 (unregistered)
10 PRINT "HELLO, WELCOME TO THE RUSSIAN (FORMERLY ROMAN) PEASANT MULTIPLICATION"
20 INPUT "PLEASE, ENTER THE TWO OPERANDS: "; A, B
30 SIGN = 1
40 PRINT "IS "; A; " NEGATIVE? (Y/N)"
50 INPUT ANSWER
60 IF ANSWER = "Y" THEN SIGN = -1
70 PRINT "IS "; B; " NEGATIVE? (Y/N)"
80 INPUT ANSWER
90 IF ANSWER = "Y" THEN SIGN = SIGN * -1
100 PRINT A; " EQUALS 0? (Y/N)"
110 INPUT ANSWER
120 IF ANSWER = "Y" THEN PRINT "THE PRODUCT IS 0": END
130 PRINT B; " EQUALS 0? (Y/N)"
140 INPUT ANSWER
150 IF ANSWER = "Y" THEN PRINT "THE PRODUCT IS 0": END
160 PRINT A; " EQUALS 1? (Y/N)"
170 INPUT ANSWER
180 IF ANSWER = "Y" THEN PRINT "THE PRODUCT IS "; B: END
190 PRINT B; " EQUALS 1? (Y/N)"
200 INPUT ANSWER
210 IF ANSWER = "Y" THEN PRINT "THE PRODUCT IS "; A: END
220 INDEX = 1
230 PRINT "IS "; A; " EVEN? (Y/N)"
240 INPUT ANSWER
240 IF ANSWER = "Y" THEN PRINT "USEFUL VALUE "; INDEX; " -> "; B: INDEX = INDEX+1
250 PRINT "PLEASE, DIVIDE "; A; " BY 2 (GIVE ME THE SMALLEST PART):"
260 INPUT A
270 PRINT "PLEASE, DOUBLE "; B
280 INPUT B
290 PRINT A; " EQUALS 1? (Y/N)"
300 INPUT ANSWER
310 IF ANSWER = "Y" THEN PRINT "USEFUL VALUE "; INDEX; " -> "; B: GOTO 330
320 GOTO 250
330 PRINT "PLEASE, GIVE ME THE USEFUL VALUE 1, FROM ABOVE:"
340 INPUT A
350 AINDEX = 1
360 FOR I=2 TO INDEX
370 PRINT "PARTIAL RESULT "; AINDEX; " -> "; A
380 PRINT "PLEASE, SUM USEFUL ANSWER "; I; " WITH PARTIAL RESULT ": AINDEX
390 INPUT A
400 AINDEX = AINDEX + 1
410 NEXT
420 PRINT "THE PRODUCT IS "; A
430 END

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 04:58 • by k1 (unregistered)
278550 in reply to 278548
whoops...
k1:

<snip>
420 PRINT "THE PRODUCT IS "; A
430 END


420 PRINT "THE PRODUCT IS "; A * SIGN

There, fixed.

CYA

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 05:29 • by Boneist (unregistered)
Oracle SQL version, showing the working out:


with my_data as (select :p1 col1, :p2 col2 from dual),
list_gen as (select level -1 lvl
from my_data
connect by power(2,level-1) <= col1),
results as (select lvl,
floor(col1/power(2,lvl)) col3,
col2*power(2, lvl) col4
from my_data,
list_gen)
select col3,
col4,
decode(floor(col3/2)*2,
col3, null,
sum(case when floor(col3/2)*2 != col3 then col4 end) over (order by lvl)) sum_col
from results
order by lvl

Re: Programming Praxis: Russian Peasant Multiplication

2009-07-23 05:49 • by C (unregistered)
; EDX:EAX <- ECX * EBX (untested)
; (all other gp registers trashed)
MOV ECX, multiplicand
MOV EBX, multiplier
multiply:
XOR EAX, EAX
XOR EDX, EDX
CMP ECX, EAX
JNL .ps
NEG ECX
NEG EBX
.ps: XOR EDI, EDI
CMP EBX, EAX
SBB EBP, EBP
SHR ECX, 1
JZ .nd
.lp: SBB ESI, ESI
MOV EDI, ESI
AND ESI, EBX
AND EDI, EBP
ADD EBX, EBX
ADC EBP, EBP
ADD EAX, ESI
ADC EDX, EDI
SHR ECX, 1
JNZ .lp
.nd: SBB ESI, ESI
MOV EDI, ESI
AND ESI, EBX
AND EDI, EBP
ADD EAX, ESI
ADC EDX, EDI
; done
; ... or just use IMUL
« 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