Multiplying Two Binary Numbers
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.
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.
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 . 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)])
 Sir Thomas L. Heath, "A Manual of Greek Mathematics", New York, Courier Dover Publications Inc., p. 29, 2003.
Previous post by Rick Lyons:
"Neat" Rectangular to Polar Conversion Algorithm
Next post by Rick Lyons:
Do Multirate Systems Have Transfer Functions?
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.