Path: utzoo!mnetor!uunet!husc6!bloom-beacon!tut.cis.ohio-state.edu!mailrus!ames!claris!apple!baum
From: baum@apple.UUCP (Allen J. Baum)
Newsgroups: comp.arch
Subject: Re: The Bellcore divider
Message-ID: <7499@apple.UUCP>
Date: 8 Apr 88 19:34:50 GMT
References: <475@eos.UUCP>
Reply-To: baum@apple.UUCP (Allen Baum)
Organization: Apple Computer, Inc.
Lines: 31

--------
[]
>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