Track: Computers and Computing

Abstract

Robertson’s algorithm [Rob55] is a two’s complement shift-and-add binary multiplication algorithm. The study started as an undergraduate thesis, which was on binary multipliers. The study took the traditional approach of pen and paper, taking arbitrary binary values to observe how the algorithm works. While doing so, a certain trend was noticed when applying numbers into Robertson’s algorithm, that it can be reduced. Certain changes to the algorithm were devised, with which the steps may be reduced by up to 50%. The first change is to skip over the addition of zeros and shift by the required number of zeros as soon as they are detected in the string; the second is to skip over the addition of ones on the detection of a string of ones, shifting by the required number of ones, and later compensating with corrective shift. The first change is universal, but the second is limited to multiplicand values of 2^x, thus being helpful in applications such as FFT, 1 hot mux, and signal processing.