Thu, 30 Dec 2010 10:03:46 +0000 (UTC)

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) |

From: | glen herrmannsfeldt <gah@ugcs.caltech.edu> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.