From: "Oliver Roese" Newsgroups: comp.os.msdos.djgpp References: <199909231908 DOT VAA19441 AT acp3bf DOT physik DOT rwth-aachen DOT de> Subject: Re: gcc optimizes divisons! Date: Fri, 24 Sep 1999 01:43:54 +0200 Lines: 96 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit 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-69.xnc.de Message-ID: <37eabba0@news.xenologics.com> X-Trace: 24 Sep 1999 01:45:36 +0100, pm1-69.xnc.de Organization: .XNC GmbH To: djgpp AT delorie DOT com DJ-Gateway: from newsgroup comp.os.msdos.djgpp Reply-To: djgpp AT delorie DOT com Hallo! (I think we can talk in german. If not mail me accordingly.) Hans-Bernhard Broeker schrieb in im Newsbeitrag: 199909231908 DOT VAA19441 AT acp3bf DOT physik DOT rwth-aachen DOT de... > In article <37ea6cda AT news DOT xenologics DOT com> you wrote: > > > Martin Stromberg 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. > > You haven't understood the trick at all, it seems. We're talking > *integer* division, here. No fractional numbers or anything. > > In C, arithmetics for unsigned integers is defined to 'wrap around' at > the upper end, i.e. evey calculation in unsigned ints is done 'modulo > UINT_MAX'. For gcc on i386, the same holds for signed integers, as > well, with some grain of salt added. For the sake of discussion, I'll > limit myself to the unsigned case. > Das stimmt einfach NICHT! Dein Grundfehler ist anscheinend, daß du zwei Operationen durcheinanderwirfst. x/c ist definiert als floor(x/c) für x>= 0, aber NICHT als x*(1/c) mod 2^32, wobei (1/c)*c = 1 mod 2^32. Um dieser falschen Vorstellung vorzubeugen, hatte ich den Hinweis darauf gegeben, daß floor(x/3) eine Treppenfunktion ist. > As you know, instead of dividing by x, you can equivalently multiply > by 1/x. The trick pulled by gcc is that it *precomputes* 1/x and and > multiplies by it, because integer division is dreadfully slow, > compared to both FP division and integer multiplication, on Pentium > class machines. > Ach nein! > The surprising thing to the mathematically unprepared eye, here, is > that 1/x is not smaller than 1, in this type of arithmetics. It's a > rather large number, for x=3. This follows from the definition of > 1/x: it's the number that, multiplied by x, gives 1. We're in 'modulo > 2^32' arithmetics, so essentially, you need to find a y that fulfills > > 3 * y = 1 (mod 2^32) > > or similarly > > 3*y = n * 2^32 + 1 (where 0 > So let's see, 3 times an number must be a multiple of 2^32, plus > 1. The left side cannot be bigger than 3*(2^32-1) = 3*2^32 - 3, > i.e. n cannot be 3 or larger. This leaves three choices for > n: 0, 1 and 2. > > Only one of these three numbers 0+1, 1*2^32+1, 2*2^32+1, if any, will > be divisible by 3. The one that is, according to the cited gcc trick, > is for n=1, where you get > > y=1431655766 > Ich weiß nicht wie Du auf diese Zahl gekommen bist, aber das Inverse zu 3 modulo 2^32 ist es jedenfalls nicht. > To summarize: in C, for 32 bit unsigned integers, > > a / 3 > > has exactly the same result as > > a * 143165766 > Das stimmt ja wohl schon für a=1 nicht. > Nice trick, gcc. > Lies doch bitte noch mal meinen Text genauer. Vielen DANK Oliver