Mail Archives: djgpp/1999/09/24/00:01:29
Hallo!
(I think we can talk in german. If not mail me accordingly.)
Hans-Bernhard Broeker <broeker AT physik DOT rwth-aachen DOT de> 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 <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.
>
> 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<y<2^32)
>
> 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
- Raw text -