The Daily WTF: Curious Perversions in Information Technology

samanddeanus · 2009-07-22 Reply Admin

Scheme with fold and unfold:

(define (mul a b)
  (fold +
	0
	(unfold (lambda (x)
		  (zero? (car x)))
		(lambda (x) 
		  (if (odd? (car x))
		      (cdr x)
		      0))
		(lambda (x)
		  (cons (quotient (car x) 2)
			(+ (cdr x) (cdr x))))
		(cons (abs a) 
		      (if (negative? a) 
			  (- b)
			  b)))))

2009-07-22 Reply Admin

moltonel:
#!/bin/sh grep -q '^1\*' <<< $1 && echo $(( $1 )) || $0 "$(( $(sed 's/\*.*//' <<< $1)/2 ))*$(( $(sed 's/.*\*//;s/+.*//' <<< $1)*2 ))$(grep -oE '[13579]\*[0-9]+' <<< $1| sed 's/.*\*/+/')$(grep -o '\+.*' <<< $1)"

I can't get this to work properly. With BSD sh it doesn't parse, with Bash it runs, but produces incorrect answers for the simplest arguments (and when the first argument is 1, it doesn't produce a result at all).

Any explanation? Maybe some of the code got mangled while posting, or you're using yet a different shell?

2009-07-22 Reply Admin

I can beat that...

int RussianPeasantMultiplyFor18And23( ) { return 414; }

OMG.. my code is fastest?

moltonel · 2009-07-22 Reply Admin

Maks Verver:
moltonel:
#!/bin/sh grep -q '^1\*' <<< $1 && echo $(( $1 )) || $0 "$(( $(sed 's/\*.*//' <<< $1)/2 ))*$(( $(sed 's/.*\*//;s/+.*//' <<< $1)*2 ))$(grep -oE '[13579]\*[0-9]+' <<< $1| sed 's/.*\*/+/')$(grep -o '\+.*' <<< $1)"
I can't get this to work properly. With BSD sh it doesn't parse, with Bash it runs, but produces incorrect answers for the simplest arguments (and when the first argument is 1, it doesn't produce a result at all).
Any explanation? Maybe some of the code got mangled while posting, or you're using yet a different shell?

Yes, bash, sorry. You'll have to give it two numbers, without space, and the multiplication sign must be an actual '*'.

eg: $ ./russian.sh 1929 551 $ ./russian.sh 1823 414

2009-07-22 Reply Admin

improvement for some problems starting with even number:

(define (rmul x y , (s 0))
  (until (= x 1)
    (unless (zero? (% x 2))
      (inc s y))
    (setq x (>> x) y (<< y)))
  (+ y s)
)

2009-07-22 Reply Admin

Why recurse when you can use a linked list?

#include <stdio.h>
#include <stdlib.h>

struct rus_row {
    long left;
    long right;
    struct rus_row *next;
};
int main(int, char **);
long rus_multiply(long, long, int);
struct rus_row *make_row(long, long, struct rus_row *);
void rus_freemem(struct rus_row *);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        printf("Usage: %s <num> <num>\n", argv[0]);
        exit(1);
    }
    long a = atol(argv[1]);
    long b = atol(argv[2]);
    long result = rus_multiply(a, b, 1);
    return 0;
}

long rus_multiply(long a, long b, int print) {
    long total = 0;
    
    struct rus_row *head = make_row(a, b, NULL);
    struct rus_row *tail = head;
    while(tail->left > 1) {
        struct rus_row *new_row = make_row(tail->left / 2, tail->right * 2, NULL);
        tail->next = new_row;
        tail = tail->next;
    }
    struct rus_row *curr = head;
    while (curr) {
        if (curr->left & 1) {
            // odd
            if (print) {
                printf ("%ld\t%ld\t+ %ld\n", curr->left, curr->right, curr->right);
            }
            total = total + curr->right;
            
        } else {
            // even
            if (print) {
                printf ("%ld\t%ld\n", curr->left, curr->right);
            }
        }
        curr = curr->next;
    }
    if (print) {
        printf ("\t\t-----\n\t\t= %ld\n", total);
    }
    rus_freemem(head);
    return total;
}

struct rus_row *make_row(long left, long right, struct rus_row *next) {
    struct rus_row *row = (struct rus_row *) malloc(sizeof(struct rus_row));  //todo:  check for malloc failure
    row->left = left;
    row->right = right;
    row->next = next;
    return row;
}

void rus_freemem(struct rus_row *head) {
    struct rus_row *next = head;
    while (next) {
        struct rus_row *curr = next;
        next = curr->next;
        free(curr);
    }
}

2009-07-22 Reply Admin

Nice callback to the futility closet article from last week. It is interesting to see how many different languages / methods people found for executing this procedure.

2009-07-22 Reply Admin

Here is my solution in C#:

        static int PeasantMult(int x, int y)
        {
            switch (x)
            {
                case -1: return -y;
                case 0: return 0;
                case 1: return y;
                default: return PeasantMult(x % 2, y) + PeasantMult(x / 2, y + y);
            }
        }

-Works with negative values on any or both operands -No multiplication

2009-07-22 Reply Admin

MG:
Why recurse when you can use a linked list?

You could always recurse over linked lists and get the best of both worlds :P

2009-07-22 Reply Admin

I think everybody misrepresented my comment on using multiplication/division instead of bitshifting being fail as a performance comment. What I was aiming at is that if you're defining multiplication, multiplying is kind of lame. Then, I changed my mind and started using ( left & 1 ) * right, but that was just a shortcut :). Also, bitshifting was closer to the original demonstration in the "spec".

I agree with all that multiplying here is safer and probably close in performance. I doubt most of the compilers present (python, java, c#, vb.net, javascript, etc) will optimize it to the same thing, but who cares? (btw, I do think C, C++, Delphi, Scheme, Haskell and a few others may optimize).

2009-07-22 Reply Admin

Google Search (by far the most commonly used programming language):

http://lmgtfy.com/?q=russian+peasant+multiplication

2009-07-22 Reply Admin

C#, just for fun :

namespace Test
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    class Program
    {
        class Elem
        {
            public int Left { get; set; }
            public int Right { get; set; }
        }

        static IEnumerable<Elem> DivideUntilOneOnLeft(Elem e)
        {
            while (e.Left != 1)
            {
                e = new Elem() { Left = e.Left / 2, Right = e.Right * 2 };
                yield return e;
            }
        }

        static int Mutiply(int left, int right)
        {
            return DivideUntilOneOnLeft(new Elem() { Left = left, Right = right })
                .Where(e => e.Left % 2 != 0)
                .Aggregate(0, (accum, e) => accum + e.Right);
        }

        static void Main(string[] args)
        {
            Console.WriteLine(Mutiply(18, 23));
            Console.ReadLine();
        }
    }
}

2009-07-22 Reply Admin

C# Recursive solution. Handles edge cases (negative integers, 0). Focus is on readability/clarity and not performance:

public static int RussianMultiply(int x, int y)
{
	if (x < 0) return RussianMultiply(-x, -y);
	else if (x == 0) return 0;
	else if (x == 1) return y;
	else if (x % 2 == 1) return y + RussianMultiply(x/2, y*2);
	else return RussianMultiply(x/2, y*2);
}

2009-07-22 Reply Admin

Here is an interesting javascript version

function russia(a,b){ return new (function(){
while(a&1?((this.c?this.c+=b:this.c=b),a=a>>1,b=b<<1,(a==0?false:true)):(a=a>>1,b=b<<1,true)){};
})().c;}

The reason for the anonymous function is because of a variable scope issue that occurs when the function is called multiple times.

2009-07-22 Reply Admin

function [c] = rpm(a,b)
while (a(end)~=1)
    a(end+1)=floor(a(end)/2);
    b(end+1)=b(end)*2;
end
c=sum(b(logical(mod(a,2))));

2009-07-22 Reply Admin

Yet another Haskell version. Distinguishing features: No indented lines, overly verbose

peasant_step :: (Int, Int) -> (Int, Int) peasant_step (x,y) = (div x 2, y + y)

first_is_positive :: (Int, Int) -> Bool first_is_positive (x,y) = x > 0

peasant_list :: (Int, Int) -> [(Int, Int)] peasant_list args = takeWhile first_is_positive $ iterate peasant_step args

first_is_odd :: (Int, Int) -> Bool first_is_odd (x,y) = (mod x 2) == 1

peasant_filter :: [(Int, Int)] -> [(Int, Int)] peasant_filter = filter first_is_odd

accumulate_second :: (Int, Int) -> Int -> Int accumulate_second (x,y) a = y + a

peasant_sum :: [(Int, Int)] -> Int peasant_sum = foldr accumulate_second 0

peasant_multiply :: Int -> Int -> Int peasant_multiply x y = peasant_sum $ peasant_filter $ peasant_list (x,y)

2009-07-22 Reply Admin

In excel:

Column A: A1: number_1 A2: =rounddown(A1/2,0) A3: =rounddown(A2/2,0) A4: and so on

Column B: B1: number_2 B2: =if(A2,B12,0) B3: =if(A3,B22,0) B4: and so on

Column C: C1: =if(mod(A1,2)=0,0,1) C2: =if(mod(A2,2)=0,0,1) C3: and so on

Column D: D1: =sumproduct(B:B,C:C)

2009-07-22 Reply Admin

Anyone done is using a .BAT script yet?

2009-07-22 Reply Admin

//C# public static void Go() { Console.WriteLine(PraxisMultiply(18, 23).ToString()); }

public static int PraxisMultiply(int number1, int number2)
{
	List<PraxisPair> pairs = new List<PraxisPair>();
	pairs.Add(new PraxisPair(number1, number2));
	while(number1 > 1)
	{
		number1 = number1 / 2;			
		number2 = number2 * 2;
		pairs.Add(new PraxisPair(number1, number2));
	}					
	int result = 0;
	foreach(PraxisPair p in pairs)
	{			
		if(p.Left % 2 == 0)
		{
			p.Right = 0;				
		}
		result += p.Right;
	}
	return result;		
}

public class PraxisPair
{
	
	public PraxisPair(int left, int right)
	{
		Left = left;
		Right = right;
	}
	
	
	public int Left{ get; set; }
	public int Right{ get; set; }
}

2009-07-22 Reply Admin

Short as can be

public static int russian(int multiplier1, int multiplier2) { int result = 0; while (multiplier1 >= 1) { result += (multiplier1 % 2 == 1)? multiplier2: 0; multiplier2 *= 2; multiplier1 /= 2; } return result; }

2009-07-22 Reply Admin

I'm not going to read through all the 400+ comments to see if this exact version's been done yet, but here's an implementation in Python:

def multtwo(one, two):
    result = 0
    while (one >= 1):
        if (one & 1):
            result += two
        one >>= 1
        two <<= 1
    return result

I did scan through the code a little bit though, and seeing so many people using division and modulo operators made me sad. Don't they teach kids anything about bitwise operators anymore?

2009-07-22 Reply Admin

SoaperGEM:
I did scan through the code a little bit though, and seeing so many people using division and modulo operators made me sad. Don't they teach kids anything about bitwise operators anymore?

See post #278250 Maybe it's time to go back to school :P

2009-07-22 Reply Admin

recursive scheme solution:

(define (russian_m a b) (if (= b 1) a (russian a b) ) )

(define (russian a b) (if (= a 1) b (+ (if (= (remainder a 2) 0) 0 b) (russian (/ a 2) (* b 2)) ) ) )

not tested

2009-07-22 Reply Admin

blueberry:
SoaperGEM:
I did scan through the code a little bit though, and seeing so many people using division and modulo operators made me sad. Don't they teach kids anything about bitwise operators anymore?

See post #278250 Maybe it's time to go back to school :P

As long as we don't multiply directly A * B, we are not violating any of the "original requirements". Of course using bit shifting can give you points, if we were at school (and may give you points here too :), but if it is not part of the requirements, I don't think we should feel forced to use it.

Cheers and good luck (I want my Sticker!)

2009-07-22 Reply Admin

You win so far :) As long as that works, obviously.

2009-07-22 Reply Admin

(defun rmul (x y)
           (let ((l (truncate x 2))
		 (r (* y 2)))
	     (reduce '+ (do ((sums '())
			     (l l (truncate l 2))
			     (r r (* r 2)))
			    ((< l 1) sums)
			  (when (oddp l)
			    (push r sums))))))

2009-07-22 Reply Admin

Recursive Python. Pretty disappointed with my work after seeing some of the others!

def peasant(x, y): 
  n = 1 
  m = n 
  while (n < y): 
    m = n 
    n = n * 2 
  out = m * x 
  d = y - m 
  if (d == 0): 
    return out 
  else:
    return peasant(x, d) + out

2009-07-22 Reply Admin

anyone done this in javascript? function multiply (x, y, total) { (x == 0) ? alert(total) : multiply (Math.floor(x/2),Math.floor(y*2),(x % 2 == 0) ? total : total+y); }

Resistance · 2009-07-22 Reply Admin

In spite of being epic late, here's mine:

#include <stdio.h>

int main() {
  int a;
  int b;
  int c;

  printf("A = ");
  scanf("%d", &a);
  printf("B = ");
  scanf("%d", &b);

  asm(
    "movl $0, %%ecx\n\t"
    "loop:\n\t"
    "shrl $1, %%eax\n\t"    // divide left side by 2
    "jnc skip_add\n\t"      // carry is set if eax was odd
    "addl %%ebx, %%ecx\n\t" // accumulate right side
    "skip_add:\n\t"
    "shll $1, %%ebx\n\t"    // multiply right side by 2
    "cmpl $0, %%eax\n\t"
    "jne loop"              // equal if left side was 1
    : "=c" (c)              // out: ecx - result
    : "a" (a), "b" (b)      // in: eax - left side, ebx - right side
  );

  printf("A * B = %d\n", c);

  return 0;
}

2009-07-22 Reply Admin

how about PL/pgSQL?

DECLARE
  tmp1 INTEGER;
  tmp2 INTEGER;
BEGIN
  CREATE TEMPORARY TABLE tmp_columns ( "left_col" INTEGER NOT NULL, "right_col" INTEGER NOT NULL );
  tmp1 := $1;
  tmp2 := $2;
  INSERT INTO tmp_columns (left_col, right_col) VALUES (tmp1, tmp2);
  WHILE tmp1 != 1 LOOP
      tmp1 := tmp1 / 2;
      tmp2 := tmp2 + tmp2;
      INSERT INTO tmp_columns (left_col, right_col) VALUES (tmp1, tmp2);
  END LOOP;
  return ( SELECT SUM(right_col) FROM tmp_columns WHERE (left_col % 2) = 1 );
END

dontera · 2009-07-22 Reply Admin

        private static int CalculateLikeRussianPeasant(int a, int b, List<int[]> lines)
        {
            if (lines == null)
            {
                lines = new List<int[]>();
                int[] lr = new int[2];
                lr[0] = a;
                lr[1] = b;
                lines.Add(lr);
                CalculateLikeRussianPeasant(-1, -1, lines);
            }

            int[] lastLr = lines[lines.Count - 1];
            if (lastLr[0] != 1)
            {
                int[] lr = new int[2];
                lr[0] = lastLr[0] / 2;
                lr[1] = lastLr[1] * 2;
                lines.Add(lr);
                if (lr[0] != 1)
                    CalculateLikeRussianPeasant(-1, -1, lines);
            }

            int result = 0;
            lines.ForEach(delegate(int[] lr)
            {
                if (lr[0] % 2 != 0)
                    result += lr[1];
            });

            return result;
        }

call into it with CalculateLikeRussianPeasant(101, 202, null);

2009-07-22 Reply Admin

I'm at the end of the third page of comments and have yet to see an Objective C solution.

What, no Apple/iPhone developers here? WTF?

2009-07-22 Reply Admin

C# (assumes a,b,c are defined and assigned elsewhere)

for(c=(a&1)b;(a>1);c+=((a>>=1)&1)(b<<=1));

44 characters

2009-07-22 Reply Admin

Arrgh, some challenges are just too challenging... 35 characters, freestanding, no need to declare and assign delegates ;-)

C++, supports negative (at least the C++ dialect of Borland C++ Builder 5, the sign of (negative number % another number) is implementation defined in C++... sigh). int r=0;for(;b;r+=b%2c;b/=2;c=2;}

Or a recursive version in 42 characters: int a(b,c){return b?a(b/2,c*2)+(b%2)*c:0;}

C++ template meta programming: template <int b, int c> struct r { static const int s = b?r<b/2,c2>::s+b%2c:0; };

Javascript 35 characters (works in firefox 3.0.11 and IE6). Damn, difficult to do integer division by 2 that also works good for negative numbers. for(r=0;b/=2;b-=d=b%1,r+=d*(c*=2));

2009-07-22 Reply Admin

Oops, copy-paste for the fail.

Real C++ version: int r=0;for(;b;r+=b%2c,b/=2,c=2);

2009-07-22 Reply Admin

Shifty recursive Scala

def rusMult(x: Int, y: Int): Int =
    rusMult(x, y, 0)

def rusMult(x: Int, y: Int, sum: Int): Int = 
    if ((x == 0) || (y == 0)) 0
    else
        x match {
            case 1 =>
                sum + y
            case _ =>
                rusMult(x >> 1, y << 1, (if (x % 2 == 0) sum else sum + y))
        }

2009-07-22 Reply Admin

newlisp.org:
improvement for some problems starting with even number:
(define (rmul x y , (s 0))
  (until (= x 1)
    (unless (zero? (% x 2))
      (inc s y))
    (setq x (>> x) y (<< y)))
  (+ y s)
)

If you're gonna do it in good LISP, don't use setq so much.

2009-07-22 Reply Admin

Hell with them, just do:

Function mult (a,b) mult = a*b end

Screw the Russians

2009-07-22 Reply Admin

Free format RPGLE

  SOURCE FILE . . . . . . .  QRPGLESRC
  MEMBER  . . . . . . . . .  RUSPEASANT
  SEQNBR*...+... 1 ...+... 2 ...+... 3 ...+... 4 ...+... 5 ...+... 6 ...+... 7 ...+... 8
    100       * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
    200      H DEBUG OPTION(*SRCSTMT:*NODEBUGIO) DFTACTGRP(*NO)                         
    300       * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
    400      Fqsysprt   O    F   85        printer OFLIND(*INOF)                        
    500       * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    600      D A               S             10I 0                                     
    700      D B               S             10I 0                                     
    800      D DIV             S             10I 0                                     
    900      D REM             S             10I 0                                     
   1000      D RESULT          S             10I 0                                     
   1100       * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   1200      D  RUSPEASANT     PR                                                      
   1300      D    IN_A                       15P 5                                     
   1400      D    IN_B                       15P 5                                     
   1500      D  RUSPEASANT     PI                                                      
   1600      D    IN_A                       15P 5                                     
   1700      D    IN_B                       15P 5                                     
   1800       * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   1900       /FREE                                                                    
   2000          A = IN_A                                                              ;
   2100          B = IN_B                                                              ;
   2200          RESULT = A * B                                                        ;
   2300          except head                                                           ;
   2400          except detail1                                                        ;
   2500          dow A > 1                                                             ;
   2600              A = %div(A:2)                                                     ;
   2700              REM = %REM(A:2)                                                   ;
   2800              B = B * 2                                                         ;
   2900              if rem > 0                                                        ;
   3000                    RESULT += B                                                 ;
   3100              endif                                                             ;
   3200              except detail2                                                    ;
   3300              if *INOF                                                          ;
   3400                    except head                                                 ;
   3500              endif                                                             ;
   3600          enddo                                                                 ;
   3700          except total                                                          ;
   3800          *INLR = *on                                                           ;
   3900          return                                                                ;
   4000       /END-FREE                                                                 
   4100      Oqsysprt   E            head           1  1                                
   4200      O                                           20 'Russian Peasant '          
   4300      O                                           34 'Multiplication'            
   4400      O          E            detail1        1                                   
   4500      O                       A             Z     15                             
   4600      O                                           20 '*'                         
   4700      O                       B             Z     35                             
   4800      O                                           40 '='                         
   4900      O                       RESULT        ZB    55                             
   5000      O          E            detail2        1                                   
   5100      O                       A             Z     15                             
   5200      O                       B             Z     35                             
   5300      O          E            total          1                                   
   5400      O                       RESULT        Z     55                
                                  * * * *  E N D  O F  S O U R C E  * * * *

2009-07-22 Reply Admin

SoaperGEM:
I did scan through the code a little bit though, and seeing so many people using division and modulo operators made me sad.

Alex Papadimoulis:
Your challenge: write a function that multiplies two numbers using the Russian peasant algorithm.

I didn't see anything in the original article about the peasants using bit shifting. I did see information about the peasants multiplying by two, and dividing by two and dropping the remainder.

But hey, maybe I missed something.

2009-07-22 Reply Admin

Threaded solution for maximum performance on a multicore system - not yet capable of negative or zero first multiplicand:

using System;
using System.Collections.Generic;
using System.Text;
using System.ComponentModel;
using System.Threading;

namespace RussianMultiply
{
    struct Multiplicands
    {
        public ManualResetEvent waitHandle;
        public int a;
        public int b;
    }

    class RussianMultiplyData
    {
        public volatile int result;
        public RussianMultiplyData()
        {
            result = 0;
        }
        public void PartialCalculateMultiplication(object o, DoWorkEventArgs dwea)
        {
            Multiplicands mp = (Multiplicands)dwea.Argument;
            if ((mp.a % 2) == 1) result += mp.b;
            mp.waitHandle.Set();
        }
    };

    class Program
    {
        static int MultiplyMultiCore(int a, int b)
        {
            List<BackgroundWorker> multiplicationWorkers = new List<BackgroundWorker>();
            List<ManualResetEvent> threadCompletedEvents = new List<ManualResetEvent>();
            RussianMultiplyData rmd = new RussianMultiplyData();
            while (a > 0)
            {
                BackgroundWorker bw = new BackgroundWorker();
                Multiplicands mps;
                mps.waitHandle = new ManualResetEvent(false);
                mps.a = a;
                mps.b = b;
                threadCompletedEvents.Add(mps.waitHandle);
                bw.DoWork += rmd.PartialCalculateMultiplication;
                bw.RunWorkerAsync(mps);
                multiplicationWorkers.Add(bw);

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

            WaitHandle.WaitAll(threadCompletedEvents.ToArray());
            return rmd.result;
        }

        static void Main(string[] args)
        {
            Console.WriteLine(MultiplyMultiCore(18, 23));
        }
    }
}

Bodestone · 2009-07-22 Reply Admin

I happened to be in SQL server at the the time so...

DECLARE @factor1 INT, @factor2 INT SET @factor1 =18 SET @factor2 = 23

SELECT	SUM(rightCol)
		FROM	(SELECT	@factor1/POWER(2,N) AS leftCol, @factor2*POWER(2,N) AS rightCol
				FROM	Tally
				WHERE	N < cast(log10(@factor1)/log10(2) as int) +1) таблица
		WHERE leftCol%2=1

This does require that you have a Tally table with the integers 0 to x where x is big enough to do any calculation that won't overflow.

mxsscott · 2009-07-22 Reply Admin

A solution in C that must be given the input as English transliterations of Russian numbers, in case voice input is used [a must for all future programs]. e.g. 18x23 is

./russianmultiply AdeenDva TriVosyem

It outputs in a similar form, as well as digits.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Must be 1+7 (not 8 or 7+1) */
#define MAGIC_LEN 1+7
const char* numerals[] = 
{
   "Nol","Adeen","Dva","Tri","Chetyre","Pyat’","Shest","Syem","Vosyem","Dyeviat"
};

char* intToRussian(unsigned int num)
{
    char b[11];
    sprintf(b,"%lu",num);
    /* Allocate enough for longest string int and one terminating character */
    char* russian = calloc(MAGIC_LEN * 10, sizeof(char));
    for (int i = 0; i < 10 && b[i]; ++i)
    {
        strcat(russian, numerals[b[i] - '0']);
    }
    return russian;
}

unsigned int russianToInt(const char *russian)
{
    int i,j,num;
    num = j - j;
    for (i = num ; i < strlen(russian); ++i)
    {
        for (j = i - i; j < 0x0A; ++j)
        {
            if ((j - j) == strncmp(russian + i, numerals[j], strlen(numerals[j])))
            {
                num *= 10;
                num += j;
            }
        }
    }
    return num;
}

char *multiply(const char* a, const char* b)
{
    unsigned int a1 = russianToInt(a);
    unsigned int b1 = russianToInt(b);
    
    unsigned int answer = 0;
    while (a1 > 0)
    {
        a1 = a1 >> 1;
        b1 = b1 << 1;
        if (a1 & 0x01)
            answer += b1;
    }
    return intToRussian(answer);
}

int main (int argc, const char * argv[]) {
    char *answer = multiply(argv[1], argv[2]);
    printf("%s\n", answer);
    printf("%lu\n", russianToInt(answer));
    return 0;
}

astonerbum · 2009-07-22 Reply Admin

Beat by the system:
anyone done this in javascript? function multiply (x, y, total) { (x == 0) ? alert(total) : multiply (Math.floor(x/2),Math.floor(y*2),(x % 2 == 0) ? total : total+y); }

http://thedailywtf.com/Comments/Programming-Praxis-Russian-Peasant-Multiplication.aspx?pg=8#278264

Also an inefficiency I had was not using shift for multiply by two. I added the y to itself. Also I coulda removed one comparison. Hey we want ultimate efficiency.

I still wonder if this algorithm is what is used for doing multiplication internally in the processor. Seems a WHOLE lot more efficient than doing addition a whole lota times, or even doing times tables or whatever... Those brilliant russian peasents :)

function rpmult(x, y){
  if (x === 0) {
    return 0;
  }
  if (x === 1) {
    return y;
  }

  var flip = false;
  if (x < 0) { 
    x = -x;
    flip = true;
  }
  var added = (((0x1 & num) === 0x1) ? 0 : y);
  var recurse = rpmult(x >> 1, y << 1);
  return flip ? - (added + recurse) : added + recurse;
}

2009-07-22 Reply Admin

Unlike the perl one-liner, this newlisp one-liner is actually readable!

(define (rmul x y) (if (= x 1) y (+ (if (zero? (% x 2)) 0 y) (rmul (>> x) (<< y)))))

2009-07-22 Reply Admin

My javascript version uses no multiplication, division, nor bit-shifting. Handles decimals, but negatives are left as an exercise for the reader.

<html><head><title>Multiply WFT</title><script>
double={0:0,1:2,2:4,3:6,4:8,'.':'.'};
doubleNeedsCarry={5:0,6:2,7:4,8:6,9:8};
carriedDouble={0:1,1:3,2:5,3:7,4:9};
carriedDoubleNeedsCarry={5:1,6:3,7:5,8:7,9:9,'.':'.'};
halve={0:0,2:1,4:2,6:3,8:4,'.':'.'}
halveHasRemainder={1:0,3:1,5:2,7:3,9:4};
RemainderedHalve={0:5,2:6,4:7,6:8,8:9};
RemainderedHalveHasRemainder={1:5,3:6,5:7,7:8,9:9,'.':'.'};
function halveRow(row){
var cells=row.cells;
var out=document.createElement('tr');
var remaindered=false;
var leading=true;
var visible='hidden';
for(var cellIndex=0;cellIndex<cells.length;cellindex++){ var="" cell="cells[cellIndex];" var="" cellvalue="cell.innerHTML;" var="" newcell="document.createElement('td');" if(remaindered="=false){" if(cellvalue="" in="" halve){="" newcell.innerhtml="halve[cellValue];}" if(cellvalue="" in="" halvehasremainder){="" newcell.innerhtml="halveHasRemainder[cellValue];}}" else="" if(remaindered="true){" if(cellvalue="" in="" remainderedhalve){="" newcell.innerhtml="RemainderedHalve[cellValue];}" if(cellvalue="" in="" remainderedhalvehasremainder){="" newcell.innerhtml="RemainderedHalveHasRemainder[cellValue];}}" if(!remaindered="" &&="" cellvalue="" in="" halve="" ||="" remaindered="" &&="" !(cellvalue="" in="" remainderedhalvehasremainder)){="" remaindered="false;}" else{="" remaindered="true;}" if(leading="=true){" if(newcell.innerhtml="='0'){" newcell.style.visibility="visible;}" else="" if(newcell.innerhtml="='.'){" visible="" ;}="" else="" leading="false;}" out.appendchild(newcell);}="" if(newcell.innerhtml="" in="" halve){="" out.style.textdecoration="line-through" ;}="" row.parentnode.appendchild(out);="" if(leading="=true){" out.style.visibility="hidden" ;="" return="" false;}="" else{="" return="" !leading;}}="" function="" doublerow(row){="" var="" cells="row.cells;" var="" cellindex="cells.length;" var="" out="document.createElement('tr');" var="" carried="false;" while(cellindex--){="" var="" cell="cells[cellIndex];" var="" cellvalue="cell.innerHTML;" var="" newcell="document.createElement('td');" if(carried="=false){" if(cellvalue="" in="" double){="" newcell.innerhtml="double[cellValue];}" if(cellvalue="" in="" doubleneedscarry){="" newcell.innerhtml="doubleNeedsCarry[cellValue];}}" else="" if(carried="true){" if(cellvalue="" in="" carrieddouble){="" newcell.innerhtml="carriedDouble[cellValue];}" if(cellvalue="" in="" carrieddoubleneedscarry){="" newcell.innerhtml="carriedDoubleNeedsCarry[cellValue];}}" if(!carried="" &&="" cellvalue="" in="" double="" ||="" carried="" &&="" !(cellvalue="" in="" carrieddoubleneedscarry)){="" carried="false;}" else{="" carried="true;}" out.insertbefore(newcell,out.firstchild);}="" if(carried!="false){" var="" newcell="document.createElement('td');" newcell.innerhtml="carriedDouble['0'];" out.insertbefore(newcell,out.firstchild);}="" var="" tb="row.parentNode;" tb.appendchild(out);="" if(row.cells.length="=out.cells.length){}" else{="" for(var="" i="0;i<tb.rows.length;i++){" while(tb.rows[i].cells.length<out.cells.length){="" var="" blank="document.createElement('td');" blank.innerhtml="0" ;="" blank.style.visibility="hidden" ;="" tb.rows[i].insertbefore(blank,tb.rows[i].firstchild);}}}}="" function="" multiply(form){="" var="" a="form.inta.value;" var="" b="form.intb.value;" if(a.charat(a.length-1)="='.'){a+='0'}" if(b.charat(b.length-1)="='.'){b+='0'}" var="" row="document.getElementsByTagName('tr')[0];" var="" t="document.createElement('table');" t.cellspacing="0;" var="" tb="document.createElement('tbody');" var="" tr="document.createElement('tr');" t.appendchild(tb).appendchild(tr);="" var="" digits="a.split('');" for(var="" i="0;i<digits.length;i++){" var="" td="document.createElement('td');" td.innerhtml="digits[i];" tr.appendchild(td);}="" if(digits[digits.length-1]="" in="" halve){="" tr.style.textdecoration="line-through" ;}="" row.cells[0].innerhtml="" ;="" row.cells[0].appendchild(t);="" row.cells[1].innerhtml="<table cellSpacing=0><tbody><tr><td> X</td></tr></tbody></table>" ;="" t="document.createElement('table');" t.cellspacing="0;" tb="document.createElement('tbody');" tr="document.createElement('tr');" t.appendchild(tb).appendchild(tr);="" if(digits.pop()="" in="" halve){="" tr.style.textdecoration="line-through" ;}="" digits="b.split('');" for(var="" i="0;i<digits.length;i++){" var="" td="document.createElement('td');" td.innerhtml="digits[i];" tr.appendchild(td);}="" row.cells[2].innerhtml="" ;="" row.cells[2].appendchild(t);="" while(halverow(row.cells[0].firstchild.firstchild.lastchild)="" ){="" doublerow(row.cells[2].firstchild.firstchild.lastchild);="" row.cells[2].firstchild.firstchild.lastchild.style.textdecoration="row.cells[0].firstChild.firstChild.lastChild.style.textDecoration" row.cells[1].firstchild.firstchild.insertrow(-1).insertcell(0).innerhtml=" " ;}="" row.cells[1].firstchild.firstchild.insertrow(-1).insertcell(0).innerhtml=" " ;="" row.cells[2].firstchild.firstchild.insertrow(-1).insertcell(0).innerhtml=" " ;="" row.cells[1].firstchild.cellspacing="0;" t="document.createElement('table');" t.cellspacing="0;" tb="document.createElement('tbody');" tr="document.createElement('tr');" t.appendchild(tb).appendchild(tr);="" row.cells[3].innerhtml="" ;="" row.cells[3].appendchild(t);="" var="" decimala="0;" for(var="" i="0;i<row.cells[0].firstChild.firstChild.firstChild.cells.length;i++){" if(row.cells[0].firstchild.firstchild.firstchild.cells[i].innerhtml="='.'){" decimala="row.cells[0].firstChild.firstChild.firstChild.cells.length-i;" break}}="" var="" decimalb="0;" for(var="" i="0;i<row.cells[2].firstChild.firstChild.firstChild.cells.length;i++){" if(row.cells[2].firstchild.firstchild.firstchild.cells[i].innerhtml="='.'){" decimalb="row.cells[2].firstChild.firstChild.firstChild.cells.length-i;" break}}="" var="" r="row.cells[2].firstChild.firstChild.lastChild;" while(r="r.previousSibling){" var="" newrow="tb.insertBefore(r.cloneNode(true),tb.firstChild);" if(tb.firstchild.style.textdecoration){="" tb.firstchild.style.visibility="hidden" ;}="" if(decimala="" &&="" decimalb){="" var="" dec="newRow.removeChild(newRow.cells[newRow.cells.length-decimalb]);" newrow.insertbefore(dec,="" newrow.cells[newrow.cells.length-decimalb-decimala+2]);}="" if(decimala="" &&="" !decimalb){="" var="" dec="document.createElement('td');" dec.innerhtml="." ;="" newrow.insertbefore(dec,="" newrow.cells[newrow.cells.length-decimala+1]);}}="" var="" carry="0;" for(var="" i="tb.rows[0].cells.length;i;){" --i;="" var="" t="carry*1;" carry="0;" for(var="" j="0;j<tb.rows.length-1;j++){" if(tb.rows[j].style.visibility="='hidden')" continue;="" if(tb.rows[j].cells[i].innerhtml="='.'){" carry="t;" t="." ;="" break;}="" t+="parseInt(tb.rows[j].cells[i].innerHTML);}" if(t="">9){
var s=t.toString().split('');
t=s.pop();
carry=s.join('');}
tb.lastChild.insertCell(0).innerHTML=t;}
if(carry!='0'){
for(j=0;j<tb.rows.length;j++){ var="" blank="document.createElement('td');" blank.innerhtml="0" ;="" blank.style.visibility="hidden" ;="" tb.rows[j].insertbefore(blank,tb.rows[j].firstchild);}="" blank.innerhtml="carry;" blank.style.visibility="visible" ;}="" row.cells[3].getelementsbytagname('tr')[row.cells[3].getelementsbytagname('tr').length-1].style.textdecoration="overline" ;}="" <="" script>="" <="" head><body><form="" action=""javascript:multiply(document.forms[0])"><br">
<input name=inta><br/>
<input name=intb><br/>
<input type=submit value=multiply><br/>
<table cellspacing="5"><tbody><tr><td></td><td></td><td></td><td></td></tr></tbody></table>
</body></html></tb.rows.length;j++){></cells.length;cellindex++){>

2009-07-22 Reply Admin

The program listed above produces this output

Russian Peasant Multiplication                     
         18    *             23    =            414
          9                  46                    
          4                  92                    
          2                 184                    
          1                 368                    
                                                414

2009-07-22 Reply Admin

My WTF is that I'd just create a huge times-table in MS Access and use DAO calls to read it back.

2009-07-22 Reply Admin

This problem is trivial in ML (4 lines):

fun peasant (1,r,q) = sum(r::q) | peasant (l,r,q) = if(l mod 2 = 1) then peasant((l div 2),(r2),(r::q)) else peasant((l div 2),(r2),q);

...a wrapper function to make it nice:

fun russian(x,y) = peasant(x,y,[]);

...and in case you need a sum function (most ml versions come with standard functions such as sum):

fun sum [] = 0 | sum (x::xs) = x + sum(xs);

2009-07-22 Reply Admin

In C, C++, C#, taking zeros and negative numbers into account:

Recursive (not tested):

INT Multiply(INT a, INT B)
{
  INT c, PosNeg = 1;

  // first, deal with zeros
  if ((a == 0) || (b == 0))
    return 0;

  // now, deal with negative numbers
  if (a < 0)
  {
    a = -a;
    PosNeg = -PosNeg;
  }
  if (b < 0)
  {
    b = -b;
    PosNeg = -PosNeg;
  }

  // now, the meat of the problem
  if (a == 1)
    return b;
  else
    return (b * (a & 1) + Multiply(a / 2, b * 2)) * PosNeg;
}

Alternatively, if you use the following as the last line, you accomplish this using only one multiplication (the one dealing with +/-) and one division per step:

    return ((a & 1) ? b : 0) + Multiply(a / 2, b + b)) *
PosNeg;

Non-recursive (also not tested):

INT Multiply(INT a, INT B)
{
  INT c = 0, PosNeg = 1;

  // first, deal with zeros
  if ((a == 0) || (b == 0))
    return 0;

  // now, deal with negative numbers
  if (a < 0)
  {
    a = -a;
    PosNeg = -PosNeg;
  }
  if (b < 0)
  {
    b = -b;
    PosNeg = -PosNeg;
  }

  // now, the meat of the problem
  while (a > 0)
  {
    if (a & 1)
      c += b;
    a /= 2;
    b *= 2; // or b += b; if you want to get rid of a multiplication
  }
  return c * PosNeg;
}

(Of course, in C++ and C#, you would probably move the declarations for c and PosNeg down closer to where they're actually used.)

Russian Peasant Multiplication

Leave a comment on “Russian Peasant Multiplication”