Daniel Vogel wrote:
Okay… One last time: For two integers (a) and (b) in the range of 0 to (2**n-1) :
((a+1)(b))>>n seems to be a closer approximation of (ab)/(2**n-1) than (a*b)>>n .
Proof? (I doubt it) If e.g. a == 0 you run into serious trouble! I guess
you wanted something like (ab+1) which is non optimal too. (ab) >> n
is what you want. You can’t get around the fact that you deal with
integers of fixed accuracy without making assumptions you don’t want to
make.
With my track record today, I may very well be wrong,
but let me give you some proof by example. Let me go
ahead and prove the extremes, and if you can find a
counter example, I’ll crawl back under my rock. For
an example let’s say 8 bit numbers… so the extremes
will be 0 and 255. Two extremes for two variables
gives us 4 cases… (I’m not saying proof by example
is proof, just that I haven’t seen evidence to the
contrary).
(for n=8)
Desired result: Current Approximation: Suggested approximation:
(ab)/(2**n-1) (ab)/(2n) (error) ((a+1)*b)/(2n) (error)
=============== ====================== ========================
Case 1: a=0 ; b=0
00/255 = 0 00/256 = 0 ( 0 ) 1*0/256 = 0 ( 0 )
Case 2: a=255 ; b=0
2550/255 = 0 2550/256 = 0 ( 0 ) 256*0/256 = 0 ( 0 )
Case 3: a=0 ; b=255 (remember truncation) vvv
0255/255 = 0 0255/256 = 0 ( 0 ) 1*255/256 = 0 ( 0 )
Case 4: a=255; b=255
255255/255 = 255 255255/256 = 254 ( 1 ) 256*255/256 = 255 ( 0 )
Remember this is just an example using the
extremes… I’d like to know if you can
find examples where this works badly…
I mentioned below that it does rounding
rather weird… As always, suggestions
are welcome…
In fact when evaluated in a rounding-down fashion which is typical of integer math, this
Truncation is what happens if you shift - with negative numbers e.g. this is
rounding up
I said quite explicitly we’re dealing with POSITIVE
numbers between 0 and (2**n-1)… Come to think
of it, 0 isn’t positive… I meant non-negative…
approximation exibhits a “nearest-neighbor” behavior on the low end of the scale.
No.
Yup… Your right here… realized it about 5 minutes
after I posted: The true behavior is closer to rounding
up on the low end of the scale, rounding to nearest
neighbor in the middle, and rounding down at the top
of the scale. Still I think a rounding error is better
behavior than an outright wrong answer.
Best regards,
-Loren> On Wed, Jul 26, 2000 at 10:52:04AM -0700, Loren Osborn wrote: