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!allegra!amdcad!bcase
From: bcase@amdcad.UUCP (Brian case)
Newsgroups: net.arch
Subject: Integer Division; interesting approach!
Message-ID: <9559@amdcad.UUCP>
Date: Fri, 14-Feb-86 13:32:21 EST
Article-I.D.: amdcad.9559
Posted: Fri Feb 14 13:32:21 1986
Date-Received: Sat, 15-Feb-86 04:31:31 EST
Organization: AMDCAD, Sunnyvale, CA
Lines: 52
Keywords: Divide Shift Rounding

[Yes, I know this is getting boring, but I think this approach to
solving one of the problems is interesting enough to warrant wide
distribution.]

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

I have liked many things that Hopkins has had to say over the years
(even if his language and punctuation leave something to be desired),
and one of closing comments is typically insightful:

--Start quote
As the programming community moves toward languages that are more
powerful than C it becomes even more urgent to rely on basic constructs.
Only the simplest languages can be based on complex, high-level
messages.  Thousands of hieroglyphics are much less powerful than an
alphabet of twenty-odd characters.  Fast, primitive operations will
be required to efficiently implement the high level languages of the
future.
--End quote

Comparing complex instructions to hieroglyphics is what I like.

    bcase

P.S.  I have reprinted here without permission the above quotes.
Jeeze, I hope IBM doesn't come after me.  These comments and the
act of causing them to be distributed are mine only and are typically
irresponsible.  I'm really just a regular, OK kinda guy.  You know,
car payments, CD player, sky-high rent, low salary (huh! you vana tauk
low celery), nerd glasses, baggy jeans.  What good would it do to sue
me?