#### 218 lines 5.5 KiB Plaintext Raw Permalink Normal View History

 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.` ``` ``` `# 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:37:39 +00:00 `Paste the following program into an [online C compiler](https://www.onlinegdb.com/online_c_compiler)` ``` ``` ````c` `#include ` ``` ``` `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` ``` ``` 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 ``` ``` `# Efficiency` 2020-02-05 16:48:54 +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 ``` ``` `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!` ``` ``` `* 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`