[sdiy] Best book /resource for fixed point math??

[Jim Credland]

I've done a fair bit on micro controllers for speed.  You end up doing a lot of shifting right. T take an example a bit like Charlie's.  In base 10:

2.0 * 3.1 = 6.2

However there's no decimal place in the microcontroller, so it sees: 

20 * 31 = 620. 

So you then have to do divide by 10 (or shift right one in base 10): 

(20 * 31) >> 1 = 62

Insert our imaginary decimal place:

(2.0 * 3.1) >> 1 = 6.2 

See?  Okay, only you are working in binary.  Let's do it with unsigned 4 binary places fixed point: 

0010.0000 (2.0)
0011.0010 (< ah this is actually 3.125 or 3 and 2/16 ... you can't get closer to .1 with this format number). 

Don't forget the binary point is in your imagination .. the computer has no idea: 

0010000 * 00110010 = 11001000000 (note that it overflowed badly which you need to allow for).

Shift right 4 ...

0110 0100 0000 >> 4 = 01100100

And re-insert our imaginary point: 

0110.0100

Which is, in human decimal numbers:
0110 = 6
0100 = 4 (sixteenths) or a quarter...

Answer = 6.25

Does that help?



Here's a function I call a lot: 

inline uint16_t unsignedInterpolate(uint16_t a, uint16_t b, uint16_t position) {
    uint32_t r1;
    uint16_t r2;

    /* consider a line from 0,a to 1,b.
     * a point along that line at 'position', which is a binary number with
     * a fixed point and a number of bits after the binary point
     * (defined as XY_TABLE_FRAC_BITS)
     * can be calcuated as y = gx + a.  Where g is the gradient calcuated as
     *   g = b - a.
     * Our point is at
     *   y=position*(b-a)+a.
     *
     * Which is the same as the previous code, but rearranged.  It now has only
     * one multiply, and one divide/shift right.  Shame about having to
     * cast to long int and back again.
     */

    r1 = (uint32_t) position * (b-a);
    r2 = (r1 >> XY_TABLE_FRAC_BITS) + a;
    return r2;

}


It's also quite handy to let integers just overflow in loops ... 

http://blog.credland.net/ has a few more examples I think.


On 12 Sep 2013, at 18:10, charlie wallace wrote:

> its always a tough thing to answer as best, since everyone has
> different ways of learning, but here goes.
> 
> we use fixed point a lot in games programming so the google with fixed
> point tutorial game development will bring you across a while bunch of
> them, they tend to be less heavy on the mathematical notation, if you
> want it from a more maths approach look up fixed point DSP tutorials.
> 
> there is a book called essential mathematics for game
> programmers/developers and they have a website with a fixed point
> powerpoint too that gives a good intro.
> 
> the basics of fixed point is basically just 12.34 * 56.78 more or less
> becomes 1234*5678 the different types are usually setup for different
> levels of precision, you rob peter to pay paul basically. you'll see
> 16.16, 8.24, 8.8, etc as basic types, and these simply are how many
> bits am i allocating to the whole , and how many to the fractional
> part. so 16.16 is 16 bits for an integer, and 16 for the fractional
> value. there are caveats that will be explained in most tutorials.
> 
> once you look for performance in fixed point, you can then go beyond
> that and stop looking at base 10 math, use powers of 2 etc, normalise
> things into ranges that make sense for 0..1023 instead of 0..1 or 0 to
> 1000, but that is for another day.
> 
> 
> On Thu, Sep 12, 2013 at 7:56 AM, Dan Snazelle <subjectivity at hotmail.com> wrote:
>> In a few different wavetable synth programs (for avr) that I have been studying, I keep finding references to  fixed point math
>> 
>> Variables like
>> 
>> Q16n16
>> Q0n31
>> Q1n15 etc
>> And functions for seperating the "fractional part" of a number, etc.
>> 
>> 
>> Im wondering which book , video, etc
>> Might be best for really coming to terms with understanding fixed point/floating point so that I can understand programs and so my own programs can improve.
>> 
>> I know it would be useful as I have read that the AVR can use  the help with math it can get (just like me)
>> 
>> Thanks!
>> _______________________________________________
>> Synth-diy mailing list
>> Synth-diy at dropmix.xs4all.nl
>> http://dropmix.xs4all.nl/mailman/listinfo/synth-diy
> _______________________________________________
> Synth-diy mailing list
> Synth-diy at dropmix.xs4all.nl
> http://dropmix.xs4all.nl/mailman/listinfo/synth-diy