The Daily WTF: Curious Perversions in Information Technology

2009-07-22 Reply Admin

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)

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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)

2009-07-22 Reply Admin

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.

2009-07-22 Reply Admin

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; }

2009-07-22 Reply Admin

the wtf is of course that my spaces got eaten... =)

2009-07-22 Reply Admin

echo "In soviet russia, multiplication does YOU!"

2009-07-22 Reply Admin

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!

2009-07-22 Reply Admin

using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace RussianPeasantMultiplication
{
    /// 
    /// The biggest WTF, of course, is there are tests!
    /// 
    [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));
        }
    }

    /// 
    /// What kind of entry would it be, if the expected code quality wasn't posted?
    /// 
    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);
        }
    }

    /// 
    /// Another WTF is to actually try to write readable, understandable code.
    /// 
    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);
        }
    }
}

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

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));
}

2009-07-22 Reply Admin

This actually misses adding the first row if the initial lval is odd.

2009-07-22 Reply Admin

(sorry, I meant the first sample given)

2009-07-22 Reply Admin

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;

2009-07-22 Reply Admin

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

2009-07-22 Reply Admin

I salute you sir!

joeyadams · 2009-07-22 Reply Admin

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.

2009-07-22 Reply Admin

You spent more than 5 minutes on a 3 minute problem. Congratulations.

jnz · 2009-07-22 Reply Admin

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;
}

2009-07-22 Reply Admin

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;
}

2009-07-23 Reply Admin

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 + " * " + 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 + "" + two + "";
		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 = "" + newCell.innerHTML + "";
		r.appendChild(newCell);
		newCell = document.createElement("td");
		if (rowIndices[i])
		{
			newCell.innerHTML = addValues[i];
			if (!first) newCell.innerHTML = "+ " + newCell.innerHTML;
			newCell.innerHTML = "" + newCell.innerHTML + "";
			first = false;
		}
		else
			newCell.innerHTML = " ";
		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>



Russian Peasant Multiplication

2009-07-23 Reply Admin

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)

cmugford · 2009-07-23 Reply Admin

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);

2009-07-23 Reply Admin

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

2009-07-23 Reply Admin

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

2009-07-23 Reply Admin

;; 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)))

2009-07-23 Reply Admin

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

2009-07-23 Reply Admin

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

arke · 2009-07-23 Reply Admin

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.

sxeraverx · 2009-07-23 Reply Admin

int mult(int a, int b) { return a*b; } /because that's how computers do it in hardware, anyway./

2009-07-23 Reply Admin

The question is, why would I want to?

2009-07-23 Reply Admin

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.

joeyadams · 2009-07-23 Reply Admin

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?

2009-07-23 Reply Admin

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

2009-07-23 Reply Admin

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

mneimeyer · 2009-07-23 Reply Admin

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")."'>".$a."".$b.""; 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">

x

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

\n"; echo "\n"; $c = Russian($_GET['a'],$_GET['b']); echo "\n"; echo "

Sum:

".$c."

\n"; } ?> </body> </html>

2009-07-23 Reply Admin

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
</pre>

2009-07-23 Reply Admin

#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::value>::value }; };

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

2009-07-23 Reply Admin

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

SlyEcho · 2009-07-23 Reply Admin

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

subanark · 2009-07-23 Reply Admin

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;
}

2009-07-23 Reply Admin

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$_";

freewildebeest · 2009-07-23 Reply Admin

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$_";

2009-07-23 Reply Admin

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;
    }

2009-07-23 Reply Admin

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

2009-07-23 Reply Admin

whoops...

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

420 PRINT "THE PRODUCT IS "; A * SIGN

There, fixed.

CYA

2009-07-23 Reply Admin

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

2009-07-23 Reply Admin

    ; 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

2009-07-23 Reply Admin

And of course in Haskell:

multiply n m = sum $ map snd $ filter (odd . fst) $ russian n m where russian 1 m = [(1,m)] russian n m = (n,m) : russian (n div 2) (m * 2)

Russian Peasant Multiplication

Leave a comment on “Russian Peasant Multiplication”