# Russian Peasant Multiplication

The Daily WTF posted a challenge to code the Russian Peasant Multiplication. Here’s mine:

Function RussianPeasant(lFirst As Long, lSecond As Long) As Double

Dim lDiv As Long
Dim lMult As Long
Dim lMod As Long

lDiv = lFirst
lMult = lSecond

Do Until lDiv = 1
Debug.Print lDiv, “x”, lMult
If lDiv Mod 2 = 1 Then
<strike>lMod = lMult</strike>
lMod = lMod + lMult
End If

lDiv = lDiv 2
lMult = lMult * 2
Loop

Debug.Print lMult, “+”, lMod

RussianPeasant = lMult + lMod

End Function

The backward division sign means integer divison. I checked the first BASIC entry in the comments and it was done in five lines. Clearly I have some variable declarations, debugs, and white space that he doesn’t, but reading his code caused me to think about the problem in a slightly different way. He just aggregates lMult every time lDiv is odd, whereas I do the same thing just not as concisely.

Posted in Uncategorized

## 9 thoughts on “Russian Peasant Multiplication”

1. Something looks wrong with your function… have you tested RussianPeasant(99, 100) ?

2. Dick – your code doesn’t always give the right answer. The line:
lMod = lMult
should be
lMod = lMult + lMod

Here’s my effort:

Function RPMult(Num1 As Long, Num2 As Double) As Double
Do While Num1 >= 1
If Num1 Mod 2 = 1 Then RPMult = RPMult + Num2
Num1 = (Num1 2)
Num2 = Num2 * 2
Loop
End Function

I made Num2 a double so it didn’t overflow so quickly.
I’ll be intrerested to see the worksheet approach (I had a think about it, but my brain crashed).

3. The best I can do…

Array formula in Excel:
=SUM(IF(MOD(INT(G9/2^(-1+ROW(INDIRECT(“1:”&CEILING(LOG(G9)/LOG(2),1))))),2)=1,G10*INT(2^(-1+ROW(INDIRECT(“1:”&CEILING(LOG(G9)/LOG(2),1)))))))
where G9 and G10 contain the numbers to be multiplied.

and in VBA

Option Explicit

Function RussianPeasant(ByVal Int1 As Long, ByVal Int2 As Long) As Long
If Int1 = 0 Or Int2 = 0 Then Exit Function
Dim SignMult As Integer: SignMult = Sgn(Int1) * Sgn(Int2)
Int1 = Abs(Int1): Int2 = Abs(Int2)
Do
RussianPeasant = RussianPeasant + IIf(Int1 Mod 2 = 1, Int2, 0)
Int2 = Int2 * 2: Int1 = Int1 2
Loop Until Int1 = 0
RussianPeasant = RussianPeasant * SignMult
End Function

4. Lizz says:

I’ve tried doing this in a plain spreadsheet (and I’m not that great at maths so I may have missed something), but it seems to only work if the number being divided is even. It gets the wrong answer if it’s odd.

So 19 * 23 comes out using this method:

19X23=437

94646
492
2184
1368368
414

Have I misunderstood this completely?

5. Bob Phillips says:

Lizz,

You have missed the other odd element in the list.

It decomposes to

1923
946
492
2184
1368

so you add all of the odds, 368+46+23. You seem to have missed the starting element which is also odd.

6. Yeah, I was thinking that the first number would only be odd once. But that’s clearly not true. I have no excuse as I was sober when I wrote this post.

7. Lizz says:

Ah, that makes sense, thank you :o) I hadn’t realised the original numbers were included.

8. Bob Phillips says: