# 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](rpm_ca65.s) and [merlin32](rpm_m32.s) 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](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 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](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 * Multiplication is associative * Multiplication is commutative * https://en.wikipedia.org/wiki/Order_of_operations