Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!cmcl2!beta!hc!ames!amdcad!tim
From: tim@amdcad.AMD.COM (Tim Olson)
Newsgroups: comp.arch
Subject: Re: Divides (Was RE: What should be in hardware but isn't)
Message-ID: <18501@amdcad.AMD.COM>
Date: Fri, 2-Oct-87 12:32:10 EDT
Article-I.D.: amdcad.18501
Posted: Fri Oct  2 12:32:10 1987
Date-Received: Tue, 6-Oct-87 04:28:03 EDT
References: <581@l.cc.purdue.edu> <18336@amdcad.AMD.COM>
Reply-To: tim@amdcad.UUCP (Tim Olson)
Organization: Advanced Micro Devices
Lines: 30

In article <1990@encore.UUCP> fay@encore.UUCP (Peter Fay) writes:
| In article <7481@steinmetz.steinmetz.UUCP> oconnor@sunray.UUCP (Dennis Oconnor) writes:
| ***  This is not really true. If you have a fast multiplier ( which is 
| ***  a good idea for many applications ) you can do division very much
| ***  quicker than one cycle per bit, relatively easily, especially for
| ***  long word lengths. In fact, you can do division in something like
|
| If the Newton-Raphson is not expensive in hardware, and is faster than
| one cycle per bit (~O(log2)), why not always design it into CPUs? (That is,
| into CPUs with wide words.)

Note that Dennis was talking about CPUs which already have a fast
(parallel) multiplier.  The *extra* expense of Newton-Raphson for this
is small, but the cost of the multiplier is large.  That is why it is
not always designed into CPUs (at least single-chip ones).

| $64 Question: Since NR-Iteration doesn't give accurate remainder, how do
| you produce one? Or do you skip remainders altogether?

Since you have a fast multiplier, remainder is just a multiply and a
subtract, once you have the quotient:

	a = (a/b)*b + a%b  --> a%b = a - (a/b)*b

	--> rem = dividend - quotient*divisor


	-- Tim Olson
	Advanced Micro Devices
	(tim@amdcad.amd.com)