Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site amdcad.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!ihnp4!amdcad!bcase
From: bcase@amdcad.UUCP (Brian case)
Newsgroups: net.arch
Subject: Re: Integer Division; interesting approach!
Message-ID: <9582@amdcad.UUCP>
Date: Sun, 16-Feb-86 15:36:49 EST
Article-I.D.: amdcad.9582
Posted: Sun Feb 16 15:36:49 1986
Date-Received: Mon, 17-Feb-86 06:11:10 EST
References: <9559@amdcad.UUCP>
Organization: AMDCAD, Sunnyvale, CA
Lines: 35
Keywords: Divide Shift Rounding
Summary: I don't like this as much as I though...

In article <9559@amdcad.UUCP>, bcase@amdcad.UUCP (Brian case) writes:
> Here is a direct quote from the "IBM RT Personal Computer Technology"
> handbook.  It occurs in M.E. Hopkins paper entitled "Compiling for
> the RT PC ROMP."
> 
> --Start quote
> One of the sadder sequences of code is to see a divide by two in a
> binary search or heap sort implemented with a divide rather than
> a shift instruction.  Even on high-performance machines, divide can
> take almost ten times a shift.  That is a big loss of performance in
> a loop that is likely to be very important.  This doesn't occur
> because compiler writers are unaware that a right shift can sometimes
> replace a divide by a power of two.  The problem is negative numbers
> as dividends.  (-1)/2 is 0 on 370.  -1 shifted right on bit is still
> -1.  The substitution of a shift for a divide only works for positive
> dividends.  For the PL.8 language we decided to implment a true twos
> complement divide subroutine using the Euclidean algorithm that rounds
> down rather than toward 0.  Thus replacing divides with shifts gives
> the same result.  In this case a low-level instruction set gave us a
> new view of source language semantics.  We simply implmented the
>                                         ------------------------
> divide subroutine that we wanted rather than accepting built-in
> --------------------------------
> semantics.
> --End quote

Well, I never thought I would be responding to my own posting, but
after thinking about this idea for a few milliseconds, I realized
that maybe this is not such a good idea from the point of view of
portability.  A better solution might be to have data types which
by their use allow the compiler to know that a right shift (and by
the way, logical right shift, not arithmetic, right?) can safely
replace a divide by a power of two.  Any comments?

    bcase