Re: rules of fixed-point arithmetic

ChrisQ <blackhole@xxxxxxxxxxx> writes:

Anthony Williams wrote:
Andrew Reilly <andrew-newspost@xxxxxxxxxxxxxxxxxxxxx> writes:

Yes, division of fixed point numbers is a pain, since, as you point
out, you have to deal with results that may not fit neatly into the
range of your data. Whenever possible, the answer is to just not
divide. When division is essential, you have to deal with it.

Having recently had to code some fixed point stuff (including
division) for an embedded platform, I can confirm that division is
indeed a real pain.

Anthony

For most embedded work, the general rule is to avoid anything to do
with the math lib, because of the code size impications and
expense.

Yes. Unfortunately the hardware was fixed, and we wanted to use a
math-heavy algorithm in order to improve on the prior
not-so-math-heavy-but-not-as-good algorithm.

Scaled integer is the usual route, arranging the data to suit
the range of expected values and to enable use of shift ^2 multiply /
divide to keep everything fast. The range of expected values is
usually quite well defined as are the accuracy
requirements. Everything else just becomes an error. What was the
problem with divide ?. Many modern cpus have integer divide
instructions, or you could even use one of the old bit shift divide
algorithms. Quite fast on a modern cpu, methinks.

If you look at the code to go with the DDJ article, you'll see that I
used a good old bit shift algorithm. It's not overly complicated, just
a pain compared to addition. It gets harder if the fixed point value
needs to have more bits than any of the available integer types, as
then you've got multi-word shifts and comparisons to handle too.

I looked at your ddj article btw and wonder why you used cordic,
rather than table lookup, perhaps with simple correction factors /
simple interpolation to improve the accuracy if needed ?. A 16 bit
lookup table is only 32 Kbytes for one quadrant, with reflection and
sign to get the others.

A lookup table with interpolation would have been another option. I
can't remember why we didn't use that, but CORDIC seemed better than
other algorithmic methods.

Anthony
--
Anthony Williams | Just Software Solutions Ltd
Custom Software Development | http://www.justsoftwaresolutions.co.uk
Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL
.

Relevant Pages

  • Re: [PATCH] tcp_cubic: use 32 bit math
    ... having a slow divide instruction or no divide at all. ... so we use a shift offset to lookup the value. ... static inline int fls ...
    (Linux-Kernel)
  • A Parity Cracking Implementation
    ... As a rule always,always bit state the algorithm. ... A bit shift to the right of the whole block and ... unsigned char block; ...
    (sci.crypt)
  • shift vs multiply (was Re: strings)
    ... and a compiler can use the shift anyway on any typical modern CPU.) ... y is the divisor -- works out to the following, ... All of this is only a win if the divide takes ... more cycles than the four instructions above. ...
    (comp.lang.c)
  • Re: no lcm in standard library?
    ... which are comparable to the AMD K6 architecture, branch misprediction ... mispredict penalties tilt the algorithm choice in favor of Euclid's ... This implements the binary GCD algorithm which removes the branch ... that it approximates the divide as a 1-bit accurate divide, ...
    (comp.lang.c)
  • Re: C++ more efficient than C?
    ... don't disagree about how much one can shift by. ... compiler. ... Such things force me to use the following algorithm for the ... For the mdiv division (which truncates towards minus infinite I ...
    (comp.programming)