Multiplying Two Binary Numbers

Rick LyonsMarch 16, 20117 comments

I just encountered what I think is an interesting technique for multiplying two integer numbers. Perhaps some of the readers here will also find it interesting.

Here's the technique: assume we want to multiply 18 times 17. We start by writing 18 and 17, side-by-side in column A and column B, as shown at the top of Figure 1. Next we divide the 18 at the top of column A by two, retaining only the integer part of the division, and double the 17 at the top of column B. The results of those two operations are the 9 and the 34 in the second row of Figure 1.

We continue in a similar manner by dividing the 9 in the second row of column A by two, retaining only the integer part of the division, and double the 34 in the second row of column B. Those results are the 4 and the 68 in the third of Figure 1. We continue these operations until the bottom number in column A is unity.

Figure 1

The next step is to cross out all the numbers in column B whose associated column A numbers are even. We show that in Figure 2. The final step is to sum all the remaining (uncrossed) numbers in column B. That is, 34 + 272 = 306, which is the desired product of our original 18 and 17 numbers.

Figure 2

The reason this scheme works is because when we divide the number in column (A) by two and examine the result to see if it's odd or even, those two operations are the same as right-shifting the binary version of the number in column (A) and determining if the least significant bit is a one or a zero. Repeating this process identifies the locations of all the ones within the binary version of the (A) number.

This multiplication requires only compares, binary shifts, and accumulations. According to Sir Thomas L. Heath, this multiplication method was known to the ancient Egyptians, but in modern times it is called the "Russian peasant's" method [1]. In practice, to minimize the computational workload, it's smart to put the smallest of our two original integers in column A and the largest integer in column B. (I wonder if there are any simple microcontrollers, with no built-in multiply capabilities, that have architectures enabling efficient implementation of this technique.)

Here's a snippet of Matlab code implementing this multiplication technique:

%  Filename: Binary_Multiply_Russian.m
  %
  %  Models the "Russian peasant's" method of multiplying 
  %  two integer numbers ("x" times "y").
  %
  %   [Lyons, 2011]
  
  clear, clc
  
  x = 18;
  y = 17;    
          
  % Initialize for multiplication (smallest number goes in Reg. "A")
      if x <= y
          A = x;, B = y; % "x" is the the smallest number
        else 
          A = y;, B = x; % "y" is the the smallest number
      end
      Accum = 0;
      
  % Determine how many times to go through the "Loop"
      if A ~= 2*floor(A/2)
          Loop_End = ceil(log2(A));     % A is odd 
        elseif log2(A) == floor(log2(A)),
          Loop_End = ceil(log2(A)) + 1; % A is even and a power of two
        else Loop_End = ceil(log2(A));    % A is even non-power of two
      end
      
  % Start the processing
  for Loop = 1:Loop_End 
      % Is LSB of "A" = 1? (Is "A" an odd number?)
      if A ~= 2*floor(A/2)
         Accum = Accum + B;
      else, end 
  
      %Check if integer "A" is equal to one
      if A ~= 1
          % A not equal to one, shift "A" right and "B" left 
          A = floor(A/2);
          B = 2*B;
        else, 
          % A is equal to 1, product result is in "Accum"
      end
  end  % End looping
  
  % Display result
      disp(' ' ), disp(' ')
      disp([num2str(x),' times ',num2str(y),' equals ',num2str(Accum)])

Reference
[1] Sir Thomas L. Heath, "A Manual of Greek Mathematics", New York, Courier Dover Publications Inc., p. 29, 2003.

Rick Lyons


Previous post by Rick Lyons:
   "Neat" Rectangular to Polar Conversion Algorithm
Next post by Rick Lyons:
   Do Multirate Systems Have Transfer Functions?

Comments:

[ - ]
Comment by WabekeMarch 21, 2011
Interesting way to think about binary multiplication. This is one of the cases where matlab makes things look more difficult than it really is. Its real elegance from a DSP point of view come from the fact that in binary multiply and divide by 2 are simple bit shifts. The complicated log logic also doesn't really add value and can become a simple while loop. A VHDL implementation can just use a constant number of loop iterations based on the width of A. Writing it out as bit operations it becomes: accum = 0; A = 18; B = 17; while (A > 0) if (bitand(A,1)) % odd, therefor add to accumulator accum = accum + B end % end if A = bitshift(A, -1); B = bitshift(B, 1); end % while loop
[ - ]
Comment by hariharan.gkMarch 20, 2011
really interesting !!!
[ - ]
Comment by michaelthompsonMarch 22, 2011
Rick, I thought this was novel when I first read the description, but after more thought, I think it is exactly how multiplies are performed in microprocessors. Based on state of LSB of first register, sum second register with an accumulator. Shift first register right and second register left. Cycle through all bits of the first register. What am I missing that would make this method novel?
[ - ]
Comment by cfeltonMarch 23, 2011
I don't think the article claimed it to be "novel" only interesting. But I do think you are correct. The above method essentially does a binary multiply without explicitly converting the base10 numbers to base2. In binary the multiplication is easy because the intermediate results are either 0 or whatever is left in the multiplicand (a * 1 = a). And we left shift the multiplicand to get the correct power and right shift the multiplier to get the next LSB (or vise-versa). By doing the the divide by 2, binary operations are taking place and looking at the least significant digit (even or odd, which is also the lsb in binary) another binary operation is taking place. I guess the trick is more useful for humans and finding shortcuts to do the arithmetic. Personally, I think these little tricks (insights) are great. I recall in one of Fenyman's books he talked about how he and another colleague were always competing to find methods to do arithmetic in their heads. They were inventing (re-inventing) little methods like this. Most hardware multiplies in microcontrollers or microprocessor are not done this way because it would require N clock cycles, were N = max_nbits(multiplicand, multiplier). Processors without hardware multipliers, I guess, don't have any instructions to assist in the multiplication. You would have to use "shifts", "adds" and "ands" or "compare" to do the multiply and it would take N passes of the loop (which seems like a lot). There must be faster software versions for a multiply, something that exploits base? properties instead of base2 properties?
[ - ]
Comment by Leo2011April 12, 2011
Cool!
[ - ]
Comment by priyank1512July 15, 2011
wow great i heard about this tech 1st time......... thank u sir..
[ - ]
Comment by arun32July 29, 2014
Isn't this the same multiplication algorithm that is taught in schools. It is looking interesting since in binary you either multiply by 1 (partial product is same as multiplicand, shifted appropriately ) or by 0 (in which case you don't multiply at all). The even terms correspond to zero , and so you just have to add only the odd terms.



http://en.wikipedia.org/wiki/Multiplication_ALU

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.

Sign up

I agree with the terms of use and privacy policy.

Subscribe to occasional newsletter. VERY easy to unsubscribe.
or Sign in