Russian Multiplication.

[Steve Hutchesson]

Something that I had heard of some time ago was a non standard way of
performing multiplication that was called Russian multiplication. I
found the following article on a web site so I coded it and it works fine.
The size limit is DWORD range which is normal with DWORD size parameters.

On computer I think there are other way to do this operation that are faster
but it is an interesting technique and I would like to see more of these
techniques if I can find them.

I wonder if any of the members know anything about Russian maths ?

Regards,

[email protected]

The article
~~~~~~~~~~~
  
===========================================================================
  
What is Russian multiplication?
  
Russian or Peasant multiplication is multiplication by repeated doubling. 
Example: to multiply 17 by 13 you double the 17 and halve the 13, and add
the doubles that correspond to an odd number in the other column. 
  
                                    17 * 13
                    doubled and halved:
                                    34 * 6
                    doubled and halved:
                                    68 * 3
                    doubled and halved:
                                    136 * 1
  
     221 = 17 x 13 - adding up the numbers in the first column that
     correspond to an odd number in the second (17+68+136)
  
It's a handy way of writing long multiplication in binary.
  
===========================================================================
  
The code to perform the multiplication.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            LOCAL num1 as DWORD
            LOCAL num2 as DWORD
            LOCAL tst1 as DWORD
            LOCAL tst2 as DWORD
            LOCAL rslt as DWORD
  
          ' -------------------------------------
          ' the two numbers to multiply together
          ' -------------------------------------
            num1 = 99999
            num2 = 42111
  
            tst1 = num1
            tst2 = num2
  
            rslt = 0
  
            ! mov ecx, num1
            ! mov edx, num2
            ! xor ebx, ebx          ; ebx is for results
          nxt0:
            ! test edx, 1           ; test if EDX is even
            ! jz nxt1
            ! add ebx, ecx          ; add 1st number to result
          nxt1:
            ! add ecx, ecx          ; double
            ! shr edx, 1            ; half
            ! cmp edx, 1            ; test EDX for 1
            ! jne nxt0              ; loop if not
          nxt2:
            ! add ebx, ecx
  
            ! mov rslt, ebx
  
            MessageBox hWin,str$(rslt),str$(tst1*tst2), _
                       %MB_OK or %MB_ICONINFORMATION

------------------

[Bob Houle]

I had no trouble compiling the source with PB/DLL 6.0


Just:
#INCLUDE "win32api.inc"
then
Adjust the MessageBox parameter 'hWin' to '0' (zero).

Regards,
--Bob

------------------

[Aldo Cavini]

Steve,

It's a handy way of writing long multiplication in binary

I didn't know this is a Russian multiplication. I effectively use something like this (more or less, invented from scratch by myself many years ago) to perform multiplications inside 8-bit microcontrollers which have not a built-in multiplication (they only have adds and shifts).

To double or halve a number in binary, it is enough to shift the bit pattern left or right 1 bit. Having a given multiplicand and multiplier, perform the following: check for the least significand bit in the multiplier; if 1, add the multiplicand to the result. Shift the multiplicand left 1 bit, and the multiplier 1 bit right. Repeat the whole process the number of bits you need.

If you consider it, this method is the exact translation from the decimal multiplication we learn at school to a binary multiplication. It is funny to see how the binary algorythms are so easyer to implement than decimal ones. For instance, assume we have to perform a division. To find a result bit, it is enough to check the dividend against the divisor; if the dividend is greater or equal, the result bit is 1, otherwise is 0! No need to perform multiplications or further checks.

Another interesting algorythm is to extract the square root: I don't remember exactly how it works (somewhere I have a printed article on it), but the whole method is simplified because each result bit can be only 0 or 1.

I wonder if any of the members know anything about Russian maths ?

Well, I also would like to know something more about Russian maths!



------------------