[XviD-devel] Hadamard Transform

[Christoph Lampert]

On Fri, 6 Sep 2002, Kim Minh Kaplan wrote:

> 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.

okay, I shouldn't write "mathematically" if I don't mean "mathematically". 

> 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%)


A       B       2*B overflows?  A+B overflows?       A-B underflows
--      --      --------------  --------------     ---------------
0       0                                            
0       1       yes(!)                                yes    
1       0       no(!)                                 
1       1       yes             yes                   
                --------------  --------------
                two times (50%) one time (25%)       one time (25%)
                                      \-------------------/
                                           together 50%


If (a+b) does not overflow, but (b+b) does, then b must be 
larger than a, so a-b is always negative and we couldn't have 
sticked to original precision anyway. 

If we start signed (e.g. 8 bit), it's essentially the same: 
2*b under- or overflows in 50% of cases (b<-64, b>=64), 
So there is no error if    -64<= b <= 63 , interval of width 128

a+b overflows if  ( b > 127-a),  underflows when (b < -128-a) 
a-b overflows if  ( b < a-127),  underflows when (b > a+128 )

So there is no error if   
     a>=0 and ( a-127 < b < 127-a)  [width 254-2a]
or 
     a< 0 and  (-a-128 < b < a+128)  [width 2a+256]

and when a ranges over the whole [-128,127], both intervals range 
from 0 to 254/256 and the average is a width of 128 again.

This is of course not a proof of anything... just wanted to mention that
I can do arithmetics, too ;-)

gruel

P.S. Too good I declared the Hadamard part "unrelated to XVID"...