Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Right Shift for Multiply and Divide

IP.com Disclosure Number: IPCOM000073480D
Original Publication Date: 1970-Dec-01
Included in the Prior Art Database: 2005-Feb-22
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Sheperd, BJ: AUTHOR

Abstract

Where a low-cost hardware multiply (or divide) is desired, an iterative procedure involving left shifts and addition (or subtraction) is usually employed. An alternative approach is described which is implemented by means of right shifts rather than left shifts. The operations are called pseudo-multiplication and pseudo-division because the results obtained are not exact. The results are sufficiently exact, however, for certain kinds of applications including graphic manipulation. The right shift pseudo-multiply algorithm offers a particular advantage in that it requires no intermediate work registers. The algorithms presented here are for binary normalized positive numbers.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Right Shift for Multiply and Divide

Where a low-cost hardware multiply (or divide) is desired, an iterative procedure involving left shifts and addition (or subtraction) is usually employed. An alternative approach is described which is implemented by means of right shifts rather than left shifts. The operations are called pseudo-multiplication and pseudo-division because the results obtained are not exact. The results are sufficiently exact, however, for certain kinds of applications including graphic manipulation. The right shift pseudo-multiply algorithm offers a particular advantage in that it requires no intermediate work registers. The algorithms presented here are for binary normalized positive numbers.

The pseudo-multiplication algorithm employs successive shifts with additions occurring when the corresponding bit in the multiplier is a "one." The sum (the developing product) is right-shifted, rather than the multiplicand being left-shifted as in most iterative multiplication algorithms. The algorithms have been described for both circular and end-off right shifts.

Assume that ML and MR contain the most significant and least significant halves, respectively, of a two-byte binary normalized positive multiplicand. Suppose that register M contains a one-byte binary normalized positive multiplier. The algorithm will then produce the pseudo product in registers PL and PR. LSB and MSB denote the least significant and most significant bit positions of an indicated register. If the bits are numbered left to right, these are positions seven and zero for eight-bit byte, as shown in Table 1.

The pseudo-division algorithm assumes that a positive binary normalized divisor is located in registers DL and DR, with DL containing the more significant half. The two-byte dividend is assumed to be in registers NL (more significant half) and NR (less significant half). The one-byte quotient is returned in register Q, but the first bit may be either zero or one. That is, the binary point of the result lies after the most significant bit position of register Q. A single work register, W, is employed, but the algorithm never has to bac...