> From: thospel@mail.dma.be (Ton Hospel)
>
> ...
> > (capacity - capacity/625 + 974)/1950
> ...
> > [Yes, the strange expression above really computes
> > (512*capacity+500000)/1000000 exactly.]
>
> Well, almost :-)
>
> (512*capacity+500000)/1000000
> (512*624*capacity)/624*1000000+1/2
> (512*624*capacity)/512*625*1950+1/2
> (624*capacity)/625*1950+1/2
> (capacity-capacity/625)/1950+975/1950
> (capacity-capacity/625+975)/1950
>
> so your formula is wrong by 1 a whopping 0.2% of the time :-)
> (By thinking of capacity as a dimensional value it was obvious your
> formula was wrong)
>
> Now why are you mistaken? Because you misunderstand
> the meaning of the `/' operator in C.
O, damn. I understand / in C very well, I had just completely ignored
the issue :-(
> For example, take capacity=20507. We find
> (512*capacity+500000)/1000000 = 10
> (capacity - capacity/625 + 974)/1950 = 10
> (capacity - capacity/625 + 975)/1950 = 11
> so replacing 974 by 975 is wrong.
>
> On the other hand, as I claimed,
> (capacity - capacity/625 + 974)/1950
> and
> (512*capacity+500000)/1000000
> give precisely the same answers for all values of capacity,
> when computed in a sufficiently large integral type.
> (Exercise: prove this!)
(512*capacity+500000)/1000000 = (capacity-capacity/625+975)/1950
Working out capacity/625 in integer math gives the right side a value that
is [0,1[ too high. Subtracting 1 from 975 to compensate gives a result that's
[1,0[ too high. But then the whole thing is divided by 1950 which rounds down
in integer math. This gets rid of the [1,0[ except if the 1 ever happens to make
the dividend a multiple of 1950, so if
624*capacity=625*975*(1+2*n)
The left side is even, the right side is odd, so that's impossible.
That should teach me to think before I post (Has been a bad week for
me. I made 3 different false bug reports this week :-) )
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Fri Apr 07 2000 - 21:00:15 EST