Re: Optimal code sequences for signed int div/rem by powers of 2 (Mark Tillotson)
Fri, 23 Apr 1993 11:03:40 GMT

          From comp.compilers

Related articles
Optimal code sequences for signed int div/rem by powers of 2 (1993-04-21)
Re: Optimal code sequences for signed int div/rem by powers of 2 (1993-04-23)
| List of all articles for this month |

Newsgroups: comp.arch,comp.compilers
From: (Mark Tillotson)
Keywords: arithmetic, optimize
Organization: Harlequin Limited, Cambridge, England
References: 93-04-079
Date: Fri, 23 Apr 1993 11:03:40 GMT (|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. 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.