Not a member?

DSP Blogs > Rick Lyons > Multiplying Two Binary Numbers

Rick Lyons
Richard (Rick) Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is the author of "Understanding Digital Signal Processing 2/E" (Prentice-Hall, 2004), and Editor of, and contributor to, "Streamlining Digital Signal Processing, A Tricks of the Trade Guidebook" (IEEE Press/Wiley, 2007). He is also an Associate Editor for the IEEE Signal Processing Magazine.

Would you like to be notified by email when Rick Lyons publishes a new blog?

Pageviews: 855

Multiplying Two Binary Numbers

Posted by Rick Lyons on Mar 16 2011 under Tips and Tricks

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

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.

4.75

posted by Rick Lyons
Richard (Rick) Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is the author of "Understanding Digital Signal Processing 2/E" (Prentice-Hall, 2004), and Editor of, and contributor to, "Streamlining Digital Signal Processing, A Tricks of the Trade Guidebook" (IEEE Press/Wiley, 2007). He is also an Associate Editor for the IEEE Signal Processing Magazine.

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

Would you like to be notified by email when Rick Lyons publishes a new blog?

hariharan.gk
Said:
really interesting !!!
2 years ago
0
Sorry, you need javascript enabled to post any comments.
Wabeke
Said:
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
2 years ago
0
Sorry, you need javascript enabled to post any comments.
michaelthompson
Said:
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?
2 years ago
0
Sorry, you need javascript enabled to post any comments.
cfelton
Replied:
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?
2 years ago
0
Leo2011
Said:
Cool!
2 years ago
0