Mail Archives: djgpp/1999/09/23/19:49:52
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
- Raw text -