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

## markt@harlqn.co.uk (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 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)
| List of all articles for this month |

 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