Method and apparatus for efficient calculation of an approximate square of a fixed-precision number

Abstract

A bit position, M, that determines the accuracy and efficiency of the approximation is selected from an N bit binary number. The multiplicand is generated by removing the Mth bit from the binary number, shifting the bits of lower order than the Mth bit up on position, then filling the lowest order bit with a zero. The multiplier is generated by removing the Mth bit, and all lower order bits from the binary number. Booth's algorithm is then used to multiply the multiplicand and the multiplier except that the Mth bit is used instead of an assumed zero during the first step of the multiplication. In hardware, a partial Booth-encoded multiplier is used to produce and approximate square of a binary number. For an N bit number, and a selected bit in the Mth position, the partial Booth-encoded multiplier has N columns, and N−M rows and N−M booth encoders. The inputs to the columns are wired so that the multiplicand has the Mth bit from the binary number removed and the bits of lower order than the Mth bit up are shifted up position, the lowest order bit being filled with a zero. The inputs to the Booth encoders are the N−M highest order bits of the binary number. The Mth bit of the binary number is input to the first Booth encoder instead of an assumed zero.