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 (a*b)/(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 (a*b+1) which is non optimal too. (a*b) >> 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:

(a*b)/(2**n-1) (a*b)/(2**n) (error) ((a+1)*b)/(2**n) (error)

=============== ====================== ========================

Case 1: a=0 ; b=0

0*0/255 = 0 0*0/256 = 0 ( 0 ) 1*0/256 = 0 ( 0 )

Case 2: a=255 ; b=0

255*0/255 = 0 255*0/256 = 0 ( 0 ) 256*0/256 = 0 ( 0 )

Case 3: a=0 ; b=255 (remember truncation) vvv

0*255/255 = 0 0*255/256 = 0 ( 0 ) 1*255/256 = 0 ( 0 )

Case 4: a=255; b=255

255*255/255 = 255 255*255/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: