jaw@eos.UUCP (James A. Woods) (03/31/88)
On July 16, 1986, Science magazine printed a teaser about a new technique to speed integer division. This was based on work by Ernest Brickell and Charles Leiserson, motivated by the need for fast division in RSA crypto work. The blurb mentioned that a systolic array chip was being built to make division fully speed-competitive with multiplication (i.e. in realtime ala the iterative array multiplier). Further details would be made coincident with journal publication and patent application. What happened -- is this something that has gone commercial?
baum@apple.UUCP (Allen J. Baum) (04/09/88)
-------- [] >In article <475@eos.UUCP> jaw@eos.UUCP (James A. Woods) writes: >On July 16, 1986, Science magazine printed a teaser about >a new technique to speed integer division. This was based on work >by Ernest Brickell and Charles Leiserson, motivated by the >need for fast division in RSA crypto work. >... >What happened -- is this something that has gone commercial? I have a paper by Purdy&Purdy at Texas A&M from IEEE Transactions on Computers, May 1987 "Integer Division in Linear Time with Bounded Fan-in. This is not the Bellcore algorithm/paper, but may be similar. It uses lots of carry-save adders, and a single carry-propogate adder, to perform the divide. Line them all up, and voila,a systolic array. It makes the observation that, if B divides A (remainder=0), and B is odd, then divide can be performed with carry-save adders, since you can just look at the LSB of A, and if its odd you subtract, and if it isn't, the you don't (this proceeds LSB->MSB, unlike most divides). Then, they proceed to show how to find the remainder of A/B using 3 CSA's/bit, with a CPA at the end for correction. Subtract the remainder from A, and your initial conditions are satisfied (you have to do something special if B is even, like only look at the least-significant non-zero bit instead of the LSB).Put it all together, and you have a systolic array with 4 CSA stages/bit. It may be that this could be optimized even further. -- {decwrl,hplabs,ihnp4}!voder!apple!baum (408)973-3385