Fri, 23 Apr 1993 11:03:40 GMT

Related articles |
---|

Optimal code sequences for signed int div/rem by powers of 2 S_JUFFA@IRAV1.ira.uka.de (1993-04-21) |

Re: Optimal code sequences for signed int div/rem by powers of 2 markt@harlqn.co.uk (1993-04-23) |

Newsgroups: | comp.arch,comp.compilers |

From: | markt@harlqn.co.uk (Mark Tillotson) |

Keywords: | arithmetic, optimize |

Organization: | Harlequin Limited, Cambridge, England |

References: | 93-04-079 |

Date: | Fri, 23 Apr 1993 11:03:40 GMT |

S_JUFFA@IRAV1.ira.uka.de (|S| Norbert Juffa) wrote:

*> Therefore, people are looking for alternatives to using division. Fast*

*> alternatives are especially feasible if the divisor is known at compile*

*> time (e.g. multiplication by reciprocal of divisor). Quite a few posts in*

*> the recent discussion were involved with speeding up division by powers of*

*> two known at compile time. This is really easy when dealing with unsigned*

*> integers (-> shift right), but requires some correction steps for signed*

*> integers.*

I think you are perhaps unjustifiably forcing a definition of signed

integer division at us that is neither mathematically elegant nor what

people usually want (if they *ever* want signed integer division). Many

languages cop out of actually defining a semantics for signed integer

division anyway!

I think we all agree that integer division and modulo are related thus:

(a / b) * b + (a MOD b) == a

This by itself is under-constrained, but the simplest most elegant way to

constrain it is to limit the values of (a MOD b) to a contiguous range of

b distinct values (usually 0 .. b-1)

To do otherwise makes correctness proofs more complex, makes it easier to

introduce bugs. I see it as a failing in a language to constrain the

semantics to disallow this definition. If you feel strongly that

a/b == -(-a/b) then you are automatically saying that

(a+nb) MOD b /= a MOD b

which is very counter-intuitive to me!!

M. Tillotson Harlequin Ltd.

markt@uk.co.harlqn Barrington Hall,

+44 223 872522 Barrington, Cambridge CB2 5RG

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.