Announcement

Collapse
No announcement yet.

Russian Multiplication.

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Russian Multiplication.

    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]

    Code:
    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
    ------------------
    hutch at movsd dot com
    The MASM Forum

    www.masm32.com

  • #2
    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

    ------------------
    "It was too lonely at the top".

    Comment


    • #3
      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!



      ------------------
      Rgds, Aldo

      Comment

      Working...
      X