2016-08-19 01:25:18 +00:00

`# Russian Peasant Multiplication`

```
```

2020-02-05 17:37:39 +00:00

`From Assembly to Basic to C to Javascript!`

2016-08-19 01:33:28 +00:00

```
```

2020-02-05 16:46:06 +00:00

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

2016-08-19 01:25:18 +00:00

```
```

2020-02-05 16:46:06 +00:00

`* 6502 Assembly Language (Both [ca65](rpm_ca65.s) and [merlin32](rpm_m32.s) sources)`

2016-08-19 01:25:18 +00:00

`* Applesoft BASIC`

`* JavaScript (Procedural version)`

`* JavaScript (OOP version)`

```
```

2016-08-19 01:33:28 +00:00

`A .dsk image has been provided as an convenience.`

2016-08-19 01:25:18 +00:00

```
```

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

```
```

2016-08-19 14:17:35 +00:00

`# So what the heck is it?`

```
```

2016-08-19 14:52:19 +00:00

`An alternative algorithm to implement multiplication using only:`

2016-08-19 14:17:35 +00:00

```
```

2020-02-05 16:46:25 +00:00

`* bit-shifts (left and right), and`

2016-08-19 14:17:35 +00:00

`* addition.`

```
```

2020-02-05 17:25:21 +00:00

`# Algorithm`

```
```

2020-02-05 18:21:40 +00:00

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

2020-02-05 17:25:21 +00:00

```
```

2020-02-05 17:37:39 +00:00

`Paste the following program into an [online C compiler](https://www.onlinegdb.com/online_c_compiler)`

```
```

````c`

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

`}`

`````

```
```

2020-02-05 17:25:21 +00:00

`# Examples`

```
```

2016-08-19 15:13:09 +00:00

`Example of "traditional" multiplication:`

2016-08-19 14:17:35 +00:00

```
```

`In base 10:`

```
```

`````

` 86`

` x 57`

` ----`

` 602`

` 430`

` ====`

` 4902`

`````

```
```

`In base 2:`

```
```

2016-08-19 14:20:26 +00:00

`````

2016-08-19 14:17:35 +00:00

` 01010110 (86)`

2020-02-05 18:16:38 +00:00

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

2016-08-19 14:17:35 +00:00

` ==============`

` 01001100100110 (4902 = 86*2^0 + 86*2^3 + 86*2^4 + 86*2^5)`

2016-08-19 14:20:26 +00:00

`````

2016-08-19 14:17:35 +00:00

```
```

`Example of Russian Peasant multiplication:`

```
```

`In Base 10:`

```
```

`````

2020-02-05 16:48:04 +00:00

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

2016-08-19 14:17:35 +00:00

`````

```
```

`In Base 2:`

```
```

`````

2020-02-05 16:50:19 +00:00

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

2016-08-19 14:17:35 +00:00

`````

2020-02-05 16:48:04 +00:00

```
```

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

`````

```
```

2020-02-05 17:37:54 +00:00

`# 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?`

2020-02-05 17:55:49 +00:00

```
```

2020-02-05 17:37:54 +00:00

`A. Yes.`

```
```

`Q. Why?`

```
```

2020-02-05 17:55:49 +00:00

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

2020-02-05 17:37:54 +00:00

```
```

2020-02-05 17:25:21 +00:00

`# Efficiency`

2020-02-05 16:48:54 +00:00

```
```

2020-02-05 17:25:21 +00:00

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

2020-02-05 16:48:54 +00:00

` functions:`

```
```

`* `isEven()``

`* `isZero()``

`* `Shl()``

`* `Shr()``

`* `AddTo()``

2020-02-05 16:48:04 +00:00

```
```

2020-02-05 17:25:21 +00:00

`Notes:`

```
```

2020-02-05 17:38:10 +00:00

`(\*) Almost everyone uses FFT (Fast Fourier Transforms), Toom, and/or Karatsuba for multiplication. For example [GMP](https://gmplib.org/manual/), GNU Multiple Precision arithmetic library, uses **[seven](https://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms)** different multiplication algorithms!`

2020-02-05 17:25:21 +00:00

```
```

`* 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`

```
```

`* https://tspiteri.gitlab.io/gmp-mpfr-sys/gmp/Algorithms.html#Multiplication-Algorithms`

`* https://en.wikipedia.org/wiki/Multiplication_algorithm`

2020-02-05 17:55:49 +00:00

`* Multiplication is associative`

`* Multiplication is commutative`

`* https://en.wikipedia.org/wiki/Order_of_operations`