[XviD-devel] Hadamard Transform

[Kim Minh Kaplan]

Christoph Lampert writes:

> Of _course_ there are lots of cases when it fails to calculate 2*b 
> when trying to keep precision. But "mathematically" the risk to overflow
> at 2*b isn't higher than at a+b. 

This is "mathematically" wrong although for this practical purpose you
are right.

But if A and B were bits we'd get

A	B	2*B overflows?	A+B overflows?
--      --      --------------  --------------
0       0
0       1
1       0       yes
1       1       yes             yes
                --------------  --------------
                two times (50%) one time (25%)

More generally speaking suppose you work with integers A and B members
of [0...2N[.

When calculating 2 * B you get an overflow whenever B is a member of
[N...2N[.  That is the probability that it overflows is 1/2 i.e. it
overflows 50% of the time.

When calculating A + B you get an overflow whenever 2N <= A + B,
i.e. 2N - B <= A, that is whenever A is a member of [B...2N[.  That is
for any given B, there are 2N - B values of A that overflow.  Off
course B can take any values between 0 and 2N - 1, so there are
0 + ... + (2N - 1) = N(2N - 1) pairs (A, B) that cause an overflow.  And
the probability of an overflow is (2N - 1) / 4N = 1/2 - 1 / 4N.

So "mathematically" the risk of overflow between the two operations
amounts to 1 / 4N which quickly closes 0: for 8 bits integers the
difference is only 0.2% and for 16 bits integers 0.0007%.

Kim Minh.

PS: I have not done any real studies in mathematics so you'd better
double check what I say...