After spending a long time with the x86 architecture and now looking at the
Intel Itanium, I have become quite curious about the issue of division and
square-root in FP hardware. I have been programming for over 20 years and
also have training in VLSI design (albeit over a decade ago ). So that
said, can anyone here give a "ball-park figures" answer to the following
questions:

(a) If one were to throw silicon at a problem and create a IEEE compliant FP
hardware divider (I believe they are called cell array dividers, though
there may be other kinds) that is as fast (or not far off) as a multiplier
of the same number of bits, roughtly how much extra silicon would it consume
compared to the multiplier? 2x? 3x? 10x? Soccer pitch?

(b) If one were to instead turn that on its head and use the same amount of
silicon (or thereabouts) and tolerate some multi-clock implementation,
roughly how many clock tics would be needed?

(c), (d) - the same questions for SQRT.

(e), (f) - the same questions for REMAINDER

NB: For (a), (c) and (e) I mean an implementation having no software, not
even microcode, just a pure VLSI logic circuit. Is that even possible for
SQRT and REMAINDER or would the amount of logic be just stupidly high for
those, as I suspect?

In article <gw6Qe.438$B4.175@newsfe5-win.ntli.net>,

(a) If one were to throw silicon at a problem and create a IEEE compliant
FP
hardware divider (I believe they are called cell array dividers, though
there may be other kinds) that is as fast (or not far off) as a multiplier
of the same number of bits, roughtly how much extra silicon would it
consume
compared to the multiplier? 2x? 3x? 10x? Soccer pitch? :)

Entirely dependent on how fast you want it relative to the multiply.

R.P. Brent wrote a paper on precisely this about
20 years back, and it is WELL worth looking up.

In article <gw6Qe.438$B4.175@newsfe5-win.ntli.net>,
Martin Howe <martinhowe@myprivacy.ca> wrote:

(e), (f) - the same questions for REMAINDER

Ditto.

NB: For (a), (c) and (e) I mean an implementation having no software, not
even microcode, just a pure VLSI logic circuit. Is that even possible for
SQRT and REMAINDER or would the amount of logic be just stupidly high for
those, as I suspect?

Nope. SQRT is as near as dammit equivalent in complexity, and REMAINDER
is only a little more complex.

"Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote in message
news:des0i1$sgb$1@gemini.csx.cam.ac.uk...

(a) If one were to throw silicon at a problem and create a IEEE compliant
FP
hardware divider (I believe they are called cell array dividers, though
there may be other kinds) that is as fast (or not far off) as a multiplier
of the same number of bits, roughtly how much extra silicon would it
consume
compared to the multiplier? 2x? 3x? 10x? Soccer pitch? :)

Entirely dependent on how fast you want it relative to the multiply.

Let's say no more than 25% slower.

R.P. Brent wrote a paper on precisely this about
20 years back, and it is WELL worth looking up.

Thanks, do you have the exact title and date (so I can google it in the hope
somebody might have it online)?

R.P. Brent wrote a paper on precisely this about
20 years back, and it is WELL worth looking up.


Thanks, do you have the exact title and date (so I can google it in the hope
somebody might have it online)?

Martin Howe wrote:

...

R.P. Brent wrote a paper on precisely this about
20 years back, and it is WELL worth looking up.


Thanks, do you have the exact title and date (so I can google it in the hope
somebody might have it online)?

Perhaps this is the doc you want:

R.P. Brent, and H.T. Kung, "The Area-Time Complexity of Binary
Multiplication", Journal of the ACM, Vol. 28, No. 3, July 1981, pp. 521-534.

After spending a long time with the x86 architecture and now looking at the
Intel Itanium, I have become quite curious about the issue of division and
square-root in FP hardware. I have been programming for over 20 years and
also have training in VLSI design (albeit over a decade ago ). So that
said, can anyone here give a "ball-park figures" answer to the following
questions:

(a) If one were to throw silicon at a problem and create a IEEE compliant FP
hardware divider (I believe they are called cell array dividers, though
there may be other kinds) that is as fast (or not far off) as a multiplier
of the same number of bits, roughtly how much extra silicon would it consume
compared to the multiplier? 2x? 3x? 10x? Soccer pitch?

On Mon, 29 Aug 2005 04:13:42 GMT, mk<kal*@dspia.*comdelete> wrote:

On Sun, 28 Aug 2005 15:17:45 -0400, Jeff Kenton
jeffrey.kenton@comcast.net> wrote:

Martin Howe wrote:

...

R.P. Brent wrote a paper on precisely this about
20 years back, and it is WELL worth looking up.


Thanks, do you have the exact title and date (so I can google it in the
hope
somebody might have it online)?

Perhaps this is the doc you want:

R.P. Brent, and H.T. Kung, "The Area-Time Complexity of Binary
Multiplication", Journal of the ACM, Vol. 28, No. 3, July 1981, pp.
521-534.

which is available at http://cr.yp.to/2005-590/brent.pdf in case
anyone missed it.

on another note, here is a worthwhile place to look for most things
arithmetic:
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pubsall.html

The 360/91 uses the multiply logic to do divide, does multiply in
three cycles, short divide in 12, and long divide in 18.
(I think those are right, but I didn't look them up.)

That would seem to indicate that six times the hardware and pipelining
should be enough to do it.

As I say, take a decent software Newton-Raphson, map its operations
to plausible hardware primitives, and then wonder what they hell they
have done to do worse. Last-bit accurate division is nasty, but not
all THAT nasty. And, not merely is the factor not all that large,
the operation is partially pipelinable in all cases, and wholly so
in the faster ones!

(a) If one were to throw silicon at a problem and create a IEEE compliant FP
hardware divider (I believe they are called cell array dividers, though
there may be other kinds) that is as fast (or not far off) as a multiplier
of the same number of bits, roughtly how much extra silicon would it consume
compared to the multiplier? 2x? 3x? 10x? Soccer pitch?