Re: Optimal code sequences for signed int div/rem by powers of 2

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

Return to the comp.compilers page.
Search the comp.compilers archives again.