Compiling fixed-point multiplications

With reference to the article by H. T. Gladwin [1], (Comm.) it should be noted that the technique described is a limited subset of techniques known for many years, particularly to programmers for machines lacking an integer multiply instruction, CDC 6000 PPU's for example. It is easier to present and implement more generally applicable techniques, such as full decomposition into “runs” of 0's and 1's to yield representation as: ∑Li=0(2m(i) - 2n(i)) which may be further compressed by replacing such terms as -2m+1 + 2m by -2m. In decomposing numbers from the right on a CDC 6000 in particular, special techniques are possible [2]. Finally, Gladwin failed to credit the CDC RUN compilers, in use for over six years on the very machines he discussed, for doing a large number of constant multiplies by shifts and adds (subroutine SHM in overlay RUN1).

View this article in the ACM Digital Library.