From: "Oliver Roese" <oroese AT edina DOT xnc DOT com>
Newsgroups: comp.os.msdos.djgpp
References: <37e37095 AT news DOT xenologics DOT com> <7scukd$rm6$1 AT antares DOT lu DOT erisoft DOT se>
Subject: Re: gcc optimizes divisons!
Date: Thu, 23 Sep 1999 20:05:31 +0200
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 5.00.2314.1300
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
NNTP-Posting-Host: pm1-67.xnc.de
Message-ID: <37ea6cda@news.xenologics.com>
X-Trace: 23 Sep 1999 20:09:30 +0100, pm1-67.xnc.de
Organization: .XNC GmbH
Lines: 38
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com


Martin Stromberg <eplmst AT lu DOT erisoft DOT se> schrieb in im Newsbeitrag:
7scukd$rm6$1 AT antares DOT lu DOT erisoft DOT se...
(...)
>
> Well... Obviously(?) x/3 == 1431655766*x + (x<0?1:0) (mod 2^32)
> Or perhaps (mod 2^32) should be (mod 2^31)...
>
> It's very probably mathematically provable using rings and fields and
such.
>

The above equation cannot hold, since x/3 is fractional most of the
time.
Even if this was a mistake and you meant floor(x/3), the equation cannot
hold, since
floor(x/n) is a staircase function.
A better approach is as follows:
Let x,n,b > 0 and natural.
Then x/n = (x*(2^b/n))/2^b .
Hence a first guess would be to choose c:=floor(2^b/n) as a
approximation for 2^b/n and hope that floor(x/n) = floor(x*c/2^b) (i).
If one explore this, one find out, that it does not work, if x is
divisible by n.
The most natural fix for this, is to choose c:= floor(2^b/n)+1. Equation
(i) will then work if (but not only if) n*x < 2^b.
(Its better NOT to prove this here. Since i feel there is lack of
information on this topic on the net, i may decide to make some remarks
on it public available in the future.)
If you choose n:= 3, b:=33 you get
c:= floor(2^33/3)+1 = 2863311531 = 0xaaaa aaab
floor(x/3) = floor (x*c/2^33) (as in the posted code fragment)

Best Regards
Oliver Roese