Fixed point math question

Hello,

If I have an signed 32-bit number, X,  and divide it by ...say
32768...I could implement that as a right-shift

X >> 15

But that seems like bad fixed point math. If we define

E1 = X >> 15
E2 = (-X) >> 15

where X is a positive integer then E1 - E2 is not zero for all X.

However, for true division:

E1 = X / 32768
E2 = -X / 32768

E1-E2 is 0 for all X

So my question is: Is it possible to implement division by Z (where
Z=2^n) as a right-shift operation so that it yields the same result as
a true division would yield?

Correction:


But that seems like bad fixed point math. If we define

E1 = X >> 15
E2 = (-X) >> 15

where X is a positive integer then abs(E1) - abs(E2) is not zero for
all X.

However, for true division:

E1 = X / 32768
E2 = -X / 32768

abs(E1)-abs(E2) is 0 for all X

So my question is: Is it possible to implement division by Z (where
Z=2^n) as a right-shift operation so that it yields the same result
as
a true division would yield?

On 7/15/12 7:40 PM, Mauritz Jameson wrote:
> Hello,
>
> If I have an signed 32-bit number, X,  and divide it by ...say
> 32768...I could implement that as a right-shift
>
> X>>  15
>
> But that seems like bad fixed point math. If we define
>
> E1 = X>>  15
> E2 = (-X)>>  15
>
> where X is a positive integer then E1 - E2 is not zero for all X.

you mean E1 + E2, right?

>
> However, for true division:
>
> E1 = X / 32768
> E2 = -X / 32768
>
> E1-E2 is 0 for all X

you mean E1 + E2.

>
> So my question is: Is it possible to implement division by Z (where
> Z=2^n) as a right-shift operation so that it yields the same result as
> a true division would yield?


"true division" keeps its fractional part.

both your "true division" and the right-shift division do something more 
than divide.  they quantize.  but the right-shift quantization always 
rounds down, even if the number is negative.  if both a number and its 
negative round down, adding them together might get you something less 
than zero.  your "true division" evidently rounds toward zero.

have you tried

   E1  =   X >> 15
   E2  = -(X >> 15)
?

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

>have you tried
>   E1  =   X >> 15
>   E2  = -(X >> 15)
>?

Yes, but I'm looking for a general way of right-shifting a number
(without knowing the sign of X) so that the result
of the shift operation produces the same result as with a true
division; i.e.

rightShift(X,N) must equal X/(2^N)

where rightShift is the right-shift operation

The reason why I posted this question is that I am working on a fixed-
point implementation of an
IIR filter and I'm wondering if it's safe to use shift operations in
that context?

My guess is that it's not a good idea to use right-shifts if right-
shifting x by N bits produces another
result (in absolute terms) than right-shifting -x by N.

robert bristow-johnson <rbj@audioimagination.com> wrote:
> On 7/15/12 7:40 PM, Mauritz Jameson wrote:

>> If I have an signed 32-bit number, X,  and divide it by ...say
>> 32768...I could implement that as a right-shift

>> X>>  15

>> But that seems like bad fixed point math. If we define

What do you mean by "fixed point math"?

>> E1 = X>>  15
>> E2 = (-X)>>  15

>> where X is a positive integer then E1 - E2 is not zero for all X.

> you mean E1 + E2, right?

>> However, for true division:

What do you mean by true division?

>> E1 = X / 32768
>> E2 = -X / 32768

>> E1-E2 is 0 for all X

> you mean E1 + E2.

>> So my question is: Is it possible to implement division by Z (where
>> Z=2^n) as a right-shift operation so that it yields the same result as
>> a true division would yield?

I believe they are different for the right shift of twos complement
signed integers and the common, but not only, implementation of
signed divide.

> "true division" keeps its fractional part.

> both your "true division" and the right-shift division do something 
> more than divide.  they quantize.  but the right-shift quantization 
> always rounds down, even if the number is negative.  if both a number 
> and its negative round down, adding them together might get you 
> something less than zero.  your "true division" evidently rounds 
> toward zero.

For some time C allowed either as the result of signed division.

C did require that (i/j)*j+i%j == i, that is, that divide and
remainder (modulo) be consistent. It might be that newer C
standards only allow for one type of signed divide.

An arithmetic shift on a sign magnitude and, I believe, ones
complement machines, give different results from twos complement.

The early Fortran machines (IBM 704 and such) used sign magnitude,
and I believe that is where the Fortran requirement for divide
came from. Then, to satisfy Fortran, later machines kept that,
but it has to be part of the definition of signed divide.
Neither is "more correct" than the other.

A side effect of your "true division" is that -1 modulo 2 
is -1 (modulo 2 or more, that is) which is not always wanted.

Anyway, to satisfy Fortran users, most machines give the result
you call "true division."

-- glen

Mauritz Jameson <mjames2393@gmail.com> wrote:
> The reason why I posted this question is that I am working on a 
> fixed-point implementation of an IIR filter and I'm wondering 
> if it's safe to use shift operations in that context?

> My guess is that it's not a good idea to use right-shifts if right-
> shifting x by N bits produces another result (in absolute terms) 
> than right-shifting -x by N.

I believe you need to take that into account when designing
the filter, but I wouldn't be surprised if the shift result
was more correct for the IIR filter case.

One way to get around this it to add a constant (so everything
is positive) divide, and then subtract a (smaller) constant.
(That makes divide like shift, not shift like divide.)

-- glen

Mauritz Jameson <mjames2393@gmail.com> wrote: 
> The reason why I posted this question is that I am working on a 

> fixed-point implementation of an IIR filter and I'm wondering 

> if it's safe to use shift operations in that context? 

> My guess is that it's not a good idea to use right-shifts if right- 
> shifting x by N bits produces another result (in absolute terms) 
> than right-shifting -x by N. 

It all depends on what the compiler will do with it.  Just Google search "right shift to divide in C++" and you'll get a ton of hits on it.  Or, search compiler related topics; eg:


http://en.wikipedia.org/wiki/Arithmetic_shift#Non-equivalence_of_arithmetic_right_shift_and_division

http://stackoverflow.com/questions/6357038/is-multiplication-and-division-using-shift-operators-in-c-actually-faster

Most compilers will do an x<<2 or x>>2 as a multiply or divide by two, but you need to know when (if) it doesn't.

Kevin McGee

On 7/15/12 8:35 PM, Mauritz Jameson wrote:
>
> Yes, but I'm looking for a general way of right-shifting a number
> (without knowing the sign of X) so that the result
> of the shift operation produces the same result as with a true
> division; i.e.
>
> rightShift(X,N) must equal X/(2^N)
>
> where rightShift is the right-shift operation
>
>
>
> The reason why I posted this question is that I am working on a fixed-
> point implementation of an
> IIR filter and I'm wondering if it's safe to use shift operations in
> that context?
>
> My guess is that it's not a good idea to use right-shifts if right-
> shifting x by N bits produces another
> result (in absolute terms) than right-shifting -x by N.

it turns out that rounding-toward-zero is worse than always rounding 
down.  at least it brings in a zero-crossing non-linearity.

try this:


long X, save_my_bits;
short E1;

save_my_bits = 0;

for(;;) {   /* infinite loop */

     /* figure out X however you intend to */

     X += save_my_bits;
     E1 = X >> 15;
     save_my_bits =  X & 0x00007FFF;

     }

that'll take care of your rounding problem for the most part.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

"Mauritz Jameson" <mjames2393@gmail.com> wrote in message 
news:0fb66aa2-1d09-4982-8abe-cb0b395dc082@w6g2000yqg.googlegroups.com...
> Hello,
>
> If I have an signed 32-bit number, X,  and divide it by ...say
> 32768...I could implement that as a right-shift
>
> X >> 15
>
> But that seems like bad fixed point math. If we define
>
> E1 = X >> 15
> E2 = (-X) >> 15
>
> where X is a positive integer then E1 - E2 is not zero for all X.
> So my question is: Is it possible to implement division by Z (where
> Z=2^n) as a right-shift operation so that it yields the same result as
> a true division would yield?

1. Before doing the right shift by 15, add +16384 to the input. The result 
would be rounded to the nearest for both positive and negative numbers. This 
solves your problem and it would be more accurate then division. However 
that could make for worse IIR limit cycle behavior.

2. By C/C++ standard, result of right shift of a signed value is 
implementation dependent. Although all compilers that I know do the right 
shift of signed value as arithmetic shift, this is something to keep in 
mind.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com