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

On Sun, 15 Jul 2012 22:57:44 -0500, Vladimir Vassilevsky wrote:

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

At this late stage I couldn't tell you where and when I've been bitten by 
the right shift on negative numbers (Code Composter for the 2812?) -- but 
it's tripped me up.

So now I use

x = (x >= 0) ? (x >> n) : -((-x) >> n);

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

On 7/16/12 12:39 AM, Tim Wescott wrote:
> On Sun, 15 Jul 2012 22:57:44 -0500, Vladimir Vassilevsky wrote:
>
>> "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.

really?  i thought that right shift of signed values preserves the sign 
in any implementation.  it copies the sign bit and shifts that in on the 
left.  and the right shift of unsigned values shifts in a 0 on the left. 
  no?

now, signed division and the remainder operator (%), that's different. 
some implementations will have a remainder be non-negative, independent 
of the sign of divisor or dividend, but most will have the sign of the 
remainder the same as the quotient.  in any case, according to K&R

     N  =  D*(N/D) + N%D;

no matter who implements it and what the signs of N and D are.

>> Although all compilers that I know do the
>> right shift of signed value as arithmetic shift, this is something to
>> keep in mind.
>
> At this late stage I couldn't tell you where and when I've been bitten by
>  the right shift on negative numbers

right shift of negative or positive numbers should be straight forward. 
  any bit that fall off the edge are lost (unless you save them first).

> (Code Composter for the 2812?) -- but
> it's tripped me up.
>
> So now I use
>
> x = (x>= 0) ? (x>>  n) : -((-x)>>  n);

i dunno why you would want to do that.


-- 

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

Use the Arithmetic Shift Right instruction and not the Logical Shift Right

Vladimir Vassilevsky <nospam@nowhere.com> wrote:

(snip)

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

It is implementation dependent as C and C++ (and Fortran) allow
for sign magnitude, ones complement, or twos complement, and
the rounding depends on that. (Fortran allows for any base greater
than one, in all three forms.)

I believe that both sign magnitude and ones complement round
toward zero, where twos complement rounds down (toward negative
infinity) on shift.

I haven't checked recently, but C used to allow either (implementation
dependent) for divide. I believe that has changed, but I am not
sure, and if so, am not sure when.

-- glen

> However
> that could make for worse IIR limit cycle behavior.

That's exactly why I felt that it might be unsafe to use right-shifts.
And it's also what
I'm seeing with my current IIR implementation.

Thank you for confirming.

On Mon, 16 Jul 2012 01:01:07 -0400, robert bristow-johnson wrote:

> On 7/16/12 12:39 AM, Tim Wescott wrote:
>> On Sun, 15 Jul 2012 22:57:44 -0500, Vladimir Vassilevsky wrote:
>>
>>> "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.
> 
> really?  i thought that right shift of signed values preserves the sign
> in any implementation.  it copies the sign bit and shifts that in on the
> left.  and the right shift of unsigned values shifts in a 0 on the left.
>   no?

No.  The standard leaves it up to the compiler vendor, and sometimes 
(rarely, but it happens), you get a logical shift.

> now, signed division and the remainder operator (%), that's different.

<snip> 

> right shift of negative or positive numbers should be straight forward.
>   any bit that fall off the edge are lost (unless you save them first).

That happens in any shift.  It's when (-1 >> 1) = 32767 that you might 
get cranky (and yes, that is what happened to me).

>> (Code Composter for the 2812?) -- but it's tripped me up.
>>
>> So now I use
>>
>> x = (x>= 0) ? (x>>  n) : -((-x)>>  n);
> 
> i dunno why you would want to do that.

1: because you never turn a small negative number into a huge positive 
one.

2: because when you shift things down enough they always go to zero, 
instead of sticking at -1

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

On 07/16/2012 06:39 AM, Tim Wescott wrote:
[...]
> So now I use
> 
> x = (x >= 0) ? (x >> n) : -((-x) >> n);

This one I use too, but what about the performance?

I mean, there is a compare and a branch.
Unless the CPU supports fancy conditional execution
and/or native multiplexing instructions, it is relatively
slow (but maybe faster than a integer division).

bye,

-- 

piergiorgio

On Mon, 16 Jul 2012 23:08:43 +0200, Piergiorgio Sartor wrote:

> On 07/16/2012 06:39 AM, Tim Wescott wrote:
> [...]
>> So now I use
>> 
>> x = (x >= 0) ? (x >> n) : -((-x) >> n);
> 
> This one I use too, but what about the performance?
> 
> I mean, there is a compare and a branch.
> Unless the CPU supports fancy conditional execution and/or native
> multiplexing instructions, it is relatively slow (but maybe faster than
> a integer division).

It's certainly going to be faster on a lot of machines -- I don't know of 
any machines that do single-cycle integer divide, but quite a few that 
are set up to do that one efficiently.

It kind of depends on the processor.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

> So now I use 
> 
> x = (x >= 0) ? (x >> n) : -((-x) >> n); 


Shouldn't there be a check prior to that in case x is MIN_INT32 ? 

If x is MIN_INT32 the operation will result in a positive number.

On Tue, 17 Jul 2012 06:13:25 -0700, mjames2393 wrote:

>> So now I use
>> 
>> x = (x >= 0) ? (x >> n) : -((-x) >> n);
> 
> 
> Shouldn't there be a check prior to that in case x is MIN_INT32 ?
> 
> If x is MIN_INT32 the operation will result in a positive number.

Indeed there should be, or at least MIN_INT(whatever word width you're 
using).

I have a library I wrote (and tested) that takes that into account, so 
I'm not always blithely writing in stuff like the above line with it's 
subtle bug.

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

"Tim Wescott" <tim@seemywebsite.please> wrote in message 
news:_9KdndVzSrSFtJnNnZ2dnUVZ_vudnZ2d@web-ster.com...
>
> 2: because when you shift things down enough they always go to zero,
> instead of sticking at -1
>

Great Scott" I've been ASRing for 41 years and never realised that
ASR as integer division failed for the value of -1 !!!!!

On Tue, 17 Jul 2012 15:31:57 +0100, gareth wrote:

> "Tim Wescott" <tim@seemywebsite.please> wrote in message
> news:_9KdndVzSrSFtJnNnZ2dnUVZ_vudnZ2d@web-ster.com...
>>
>> 2: because when you shift things down enough they always go to zero,
>> instead of sticking at -1
>>
>>
> Great Scott" I've been ASRing for 41 years and never realised that ASR
> as integer division failed for the value of -1 !!!!!

Well, it all depends on how you define the word "fail", now doesn't it?

If successful integer division means "divide by two and always round 
down", then it works great, because -0.5, rounded down, is -1.

If it means "oh stop being a Clintonesque smartass, in integer-land, -1/2 
= 0 fercrissakes!" then yes, I suppose it fails.

-- 
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com

Tim Wescott <tim@seemywebsite.please> writes:

> On Mon, 16 Jul 2012 01:01:07 -0400, robert bristow-johnson wrote:
>
>> On 7/16/12 12:39 AM, Tim Wescott wrote:
>>> On Sun, 15 Jul 2012 22:57:44 -0500, Vladimir Vassilevsky wrote:
>>>
>>>> "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.
>> 
>> really?  i thought that right shift of signed values preserves the sign
>> in any implementation.  it copies the sign bit and shifts that in on the
>> left.  and the right shift of unsigned values shifts in a 0 on the left.
>>   no?
>
> No.  The standard leaves it up to the compiler vendor, 

Tim is right under C99:

  If E1 has a signed type and a negative value, the resulting value is
  implementation-defined.

-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

Randy Yates <yates@digitalsignallabs.com> wrote:

(snip, Tim wrote)
>> No.  The standard leaves it up to the compiler vendor, 

> Tim is right under C99:

>  If E1 has a signed type and a negative value, the resulting 
> value is implementation-defined.

Right, but partly to allow for sign magnitude or ones complement.
(I haven't followed C11, but as far as I know, all C standard
versions allow for them.)

Maybe also for systems that do logical shift even on signed values.

-- glen

"Tim Wescott" <tim@seemywebsite.com> wrote in message 
news:k7CdnbltuJZjLZjNnZ2dnUVZ_oOdnZ2d@web-ster.com...
> On Tue, 17 Jul 2012 15:31:57 +0100, gareth wrote:
>> "Tim Wescott" <tim@seemywebsite.please> wrote in message
>> news:_9KdndVzSrSFtJnNnZ2dnUVZ_vudnZ2d@web-ster.com...
>>> 2: because when you shift things down enough they always go to zero,
>>> instead of sticking at -1
>> Great Scott" I've been ASRing for 41 years and never realised that ASR
>> as integer division failed for the value of -1 !!!!!
> Well, it all depends on how you define the word "fail", now doesn't it?
> If successful integer division means "divide by two and always round
> down", then it works great, because -0.5, rounded down, is -1.
> If it means "oh stop being a Clintonesque smartass, in integer-land, -1/2
> = 0 fercrissakes!" then yes, I suppose it fails.

As x / 2 must equal - - x / 2 at all times, it is the latter case, but 
lacking
the childish outbursts.

In article <0fb66aa2-1d09-4982-8abe-cb0b395dc082@w6g2000yqg.googlegroups.com>,
Mauritz Jameson  <mjames2393@gmail.com> 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.
>
>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?

Assuming in the context of fixed point that we are dealing with
approximated numbers:

Answer 1:   Use arithmetic shift right instead of logical shift right.
   Intel ASR not LSR
Answer 2:   If you divide by 32000 expect to loose precision by
the truck load. If you expect division by 32768 to be fundamentally
different, you're insane. Think about it: you kill 15 significant
digits.

Groetjes Albert


--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

Mauritz Jameson <mjames2393@gmail.com> writes:

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

Mauritz,

I not sure about your context, but if X is a fixed-point number scaled
Qf (f some integer), then you can "divide" X by any power of two by
simply reinterpreting the scaling as Q(f - m), where m = log_2(M)
and M is the divisor.

This has the wonderful property that it loses absolutely no precision.
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com