# Re: Integer division

## glen herrmannsfeldt <gah@ugcs.caltech.edu>Thu, 30 Dec 2010 10:03:46 +0000 (UTC)

From comp.compilers

Related articles
Integer division drizzle76@gmail.com (dz) (2010-12-27)
Re: Integer division derek@_NOSPAM_knosof.co.uk (Derek M. Jones) (2010-12-29)
Re: Integer division gah@ugcs.caltech.edu (glen herrmannsfeldt) (2010-12-30)
Re: Integer division robin51@dodo.com.au (robin) (2011-01-03)
| List of all articles for this month |

 From: glen herrmannsfeldt Newsgroups: comp.compilers Date: Thu, 30 Dec 2010 10:03:46 +0000 (UTC) Organization: A noiseless patient Spider References: 10-12-050 Keywords: arithmetic Posted-Date: 30 Dec 2010 10:58:53 EST

dz <drizzle76@gmail.com> wrote:

> I am looking for references on how to support general 32 bit
> integer division (not just invariants) on hardware without dedicated
> integer-division support and 64 bit floating point support.

Well, there is always the shift/subtract loop generating
one bit at a time. Either the restoring or non-restoring
division algorithm should be easy to find. Many processors without
hardware divide have instruction to make this easier, such as
rotate and rotate through carry.

> However
> there is 32 bit floating point support and dedicated hardware to
> support 32 bit math functions such as logarithm and exponential. Can
> someone please point me to references. I realize this question has
> been asked before but they seemed to pertain to invariant
> denominators. And invariant perhaps refers to constants...

> [I'd look in Knuth's "Seminumerical Algorithms" where he explains it all.
> -John]

That is the reference I would have given, too. The more usual problem
is, given an N bit divide instruction, and N bit multiply, and, and
subtract, do a 2N bit divide. Using the 32 bit floating point
hardware, you should be able to do a 20 or so bit divide, then use the
algorithms in Knuth to extend that to 32 bits.

For constants, you can usually find the appropriate N bit constant
such that when multiplied generating a 2N bit product, the appropriate
quotient appears in the high half of the product. Many compilers will
do this for division by constants. That doesn't help so much when the
divisor is variable.

-- glen

Post a followup to this message