Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

single cycle divider

2 views
Skip to first unread message

kauphy

unread,
Apr 4, 2003, 10:12:27 PM4/4/03
to
Hi,
does any one have any idea regarding "single cycle divider",without
using the lookup table for the inverse of numbers from 1 to 2^53....I
have
searched some conferences, and could find a paper where the division
is done in 5 cycles.Does any one know where i can get an algorithm or
something...which will implement the division operation in less number
of cycles.And for me the result of division need not be that accurate.
hoping to get a reply soon,
regards,
kauphy.

B. Joshua Rosen

unread,
Apr 4, 2003, 10:49:29 PM4/4/03
to

How long are the operands? For short operands you could use log
tables. For large floating point operands the fastest algorithm is
convergence division which requires a fast floating point multiplier. For
medium length numbers, 32 integers or single precision floating point,
you really can't do better than a two bit at time algorithm. The best
description of convergence division that I know of was in the Cray 1
manual, I think that you might be able to find a copy online.

Larry Doolittle

unread,
Apr 4, 2003, 10:59:39 PM4/4/03
to

How long is a cycle? All of the multi-cycle algorithms are
essentially pipelines, which can be unrolled. Delay won't
go down (much), throughput gets horrible, but you don't really
need the intervening clocks.

- Larry

Glen Herrmannsfeldt

unread,
Apr 13, 2003, 2:57:26 AM4/13/03
to

"B. Joshua Rosen" <bjr...@polybus.com> wrote in message
news:pan.2003.04.05.03....@polybus.com...

> On Fri, 04 Apr 2003 22:12:27 -0500, kauphy wrote:
>
> > Hi,
> > does any one have any idea regarding "single cycle divider",without
> > using the lookup table for the inverse of numbers from 1 to 2^53....I
> > have
> > searched some conferences, and could find a paper where the division is
> > done in 5 cycles.Does any one know where i can get an algorithm or
> > something...which will implement the division operation in less number
> > of cycles.And for me the result of division need not be that accurate.

> How long are the operands? For short operands you could use log


> tables. For large floating point operands the fastest algorithm is
> convergence division which requires a fast floating point multiplier. For
> medium length numbers, 32 integers or single precision floating point,
> you really can't do better than a two bit at time algorithm. The best
> description of convergence division that I know of was in the Cray 1
> manual, I think that you might be able to find a copy online.

I like the 360/91 algorithm a little better. It is actually a divide
instead of reciprocal, and is documented in about as many places. That is,
as an example in most books on pipelined processors. On the 360/91 it was
not unrolled, and I believe takes five cycles for single precision and six
for double.

-- glen


0 new messages