2020-02-05 10:21:40 -08:00
2016-08-18 18:21:06 -07:00
2016-08-18 17:43:21 -07:00
2016-08-18 17:42:31 -07:00
2020-02-05 10:21:40 -08:00
2016-08-18 17:42:31 -07:00
2016-08-18 17:42:48 -07:00
2020-02-05 09:38:31 -08:00
2016-08-18 18:21:06 -07:00

Russian Peasant Multiplication

From Assembly to Basic to C to Javascript!

Here are my implementations of Russian Peasant Multiplication implemented in various languages:

  • 6502 Assembly Language (Both ca65 and merlin32 sources)
  • Applesoft BASIC
  • JavaScript (Procedural version)
  • JavaScript (OOP version)

A .dsk image has been provided as an convenience.

To see how much faster the Assembly version is then the BASIC version:

RUN  RPM.BAS
BRUN RPM.BIN

And enter in 123456789 * 987654321 respectively for A and B ...

Version Time
Applesoft 33 s
Assembly ~1 s

So what the heck is it?

An alternative algorithm to implement multiplication using only:

  • bit-shifts (left and right), and
  • addition.

Algorithm

  1. Initialize sum <- ZERO.
  2. IF b is ZERO then STOP.
  3. IF b is ODD then ADD a to sum.
  4. MULTIPLY a by 2. That is, shift a left once.
  5. DIVIDE b by 2. That is, shift b right once.
  6. GOTO step 2

Paste the following program into an online C compiler

#include <stdio.h>

int RPM( int a, int b )
{
    int sum = 0;

    while( b )
    {
        if( b & 1 )
            sum += a;

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

    return sum;
}

int main()
{
    return printf( "%d\n", RPM( 86, 57 ) );
}

Examples

Example of "traditional" multiplication:

In base 10:

             86
           x 57
           ----
            602
           430
           ====
           4902

In base 2:

        01010110  (86)
      x 00111001  (57) -+
        --------        V
        01010110  (86 * 1*2^0 =   86)
       00000000   (86 * 0*2^1 =  172) <- wasted work, partial sum = 0
      00000000    (86 * 0*2^2 =  344) <- wasted work, partial sum = 0
     01010110     (86 * 1*2^3 =  688)
    01010110      (86 * 1*2^4 = 1376)
   01010110       (86 * 1*2^5 = 2752)
  ==============
  01001100100110  (4902 = 86*2^0 + 86*2^3 + 86*2^4 + 86*2^5)

Example of Russian Peasant multiplication:

In Base 10:

               A          B   B Odd?   Sum =    0
              86         57   Yes      + A =   86
      x 2 =  172   / 2 = 28   No           =   86
      x 2 =  344   / 2 = 14   No           =   86
      x 2 =  688   / 2 =  7   Yes      + A =  774
      x 2 = 1376   / 2 =  3   Yes      + A = 2150
      x 2 = 2752   / 2 =  1   Yes      + A = 4902

In Base 2:

               A          B   B Odd?   Sum = 0
        01010110   00111001   Yes      + A = 00000001010110
       010101100   00011100   No           = 00000001010110
      0101011000   00001110   No           = 00000001010110
     01010110000   00000111   Yes      + A = 00001100000110
    010101100000   00000011   Yes      + A = 00100001100110
   0101011000000   00000001   Yes      + A = 01001100100110

In Base 8:

                A          B   B Odd?   Sum =     0
              126         71   Yes      + A =   126
       x 2 =  254   / 2 = 34   No           =   126
       x 2 =  530   / 2 = 16   No           =   126
       x 2 = 1260   / 2 =  7   Yes      + A =  1406
       x 2 = 2540   / 2 =  3   Yes      + A =  4146
       x 2 = 5300   / 2 =  1   Yes      + A = 11446

In Base 16:

               A          B   B Odd?   Sum =    0
              56         39   Yes      + A =   56
       x 2 =  AC   / 2 = 1C   No           =   56
       x 2 = 158   / 2 =  E   No           =   56
       x 2 = 2B0   / 2 =  7   Yes      + A =  306
       x 2 = 560   / 2 =  3   Yes      + A =  866
       x 2 = AC0   / 2 =  1   Yes      + A = 1326

Bases

Does this algorithm work in other bases such as 2, 8, or 16?

Consider the question:

Q. Does multipling by 2 work in other bases?

A. Yes.

Q. Why?

A. When we write a number in a different base we have the same representation but a different presentation.

Adding, subtracting, multiplying, dividing all function the same regardless of which base we use.

This is the exact same reason that 0.999999... = 1.0. The exact same represented number is presented differently -- which confuses the uninformed. It is a "Mathematical illusion."

Proof:

       1 = 1                Tautology
     1/3 = 1/3              Divide by sides by 3
 3 * 1/3 = 3 * 1/3          Multiply by sides by 3
 3 * 1/3 = 3 * 0.333333...  Express integer fraction in decimal
     1   = 3 * 0.333333...  Simply left side (fractions cancel)
     1   =     0.999999...  Simply right side

QED.

Efficiency

For a "BigInt" or "BigNumber" library this is NOT the most efficient (*) way to multiply numbers as it doesn't scale (**). However, it is rather trivial to implement. You only need a few functions:

  • isEven()
  • isZero()
  • Shl()
  • Shr()
  • AddTo()

Notes:

(*) Almost everyone uses FFT (Fast Fourier Transforms), Toom, and/or Karatsuba for multiplication. For example GMP, GNU Multiple Precision arithmetic library, uses seven different multiplication algorithms!

  • Basecase
  • Karatsuba
  • Toom-3
  • Toom-4
  • Toom-6.5
  • Toom-8.5
  • FFT

(**) What do we mean by "Doesn't scale"? As the input numbers uses more bits we end up doing more work other other algorithms.

References

Description
Russian Peasant Multiplication
Readme 69 KiB
Languages
Assembly 69.6%
JavaScript 22.8%
BASIC 6.1%
Shell 1.1%
C 0.4%