Multiplying Two Binary Numbers

• 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

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.

Sign in