Binary point math in C (PIC micro)

[aiq25]

I'm working on a project writing software for a PIC16 micro. For one of the functions I need to calculate a floating-point value based on a sensor input.

Since it's an 8-bit microcontroller I'm being asked to use binary point math (which I never used before). After doing some research I found few articles that explains binary point but really doesn't go into the details of using it to solve equations.

The equation is a quadratic formula with couple of coefficient in the 5th decimal place. Does anyone have any good tutorial suggestions?

Basically, I have something like this:
y = x + 0.0000125*k^2 - 0.045*k^ + 0.5

Where "x" is a floating-point value from 0 to 150 and "k" is my value which can be from 0 to 500 in increments of 10. “y” can be from 0 to a 100 and is 10-bits.

Any help is appreciated! Thanks.

[Howardlong]

Not sure what is meant by binary point math, do you mean fixed point?

Is this high speed and/or real time?

[aiq25]

Not sure what is meant by binary point math, do you mean fixed point?

Is this high speed and/or real time?

Yes I think I mean fixed point (http://www-inst.eecs.berkeley.edu/~cs61c/sp06/handout/fixedpt.html -- something like this). Sorry not sure about the terminology because I'm new to this. I always used 16-bit micro's and floating point.

System is in real time, 1ms refresh rate, although this can be in seconds, not a fast system.

[Kalvin]

Sometimes lookup-table(s) with pre-calculated results can ease the pain and speed up the computation.

[Andreas]

Hello,

in this special case you could also use a pre-calculated table with 51 entries (16 bit ea).

with best regards

Andreas

[Kalvin]

A piece-wise interpolated lookup-table may take somewhat less space.

Edit: Andreas was faster

[aiq25]

Hmmm... Look up table is interesting but I think the table will be ver large. I have two variables, one is 10-bit and the other 8-bit so that's a lot or combination.

[Andreas]

The table of course only for the "k" term.
the y-term is only a simple 16 bit add
(normalized by whatever factor you need).

with best regards

Andreas

[Rerouter]

What they are refering to is take "y = x +" this you calculate each time, ideally you would make them both fixed point, but a float add is not as expensive as calculating the rest,

For k you can precomute each value and then save that to a table

[rstofer]

That equation just says y=x + (some constant) where the quadratic terms don't involve x.  That seems a little odd but it's your equation.  Precompute a table for the constant terms and just do the addition at run time.  You can use some external method of building the table as long as the floating point representation is correct at run time.  Do the lookup then do the floating point add.

That floating point value for 'x' came from somewhere.  It would be an odd sensor that actually generated IEEE floating point as an output.  The point is, you probably already have the floating point library linked into your code so you might as well just do a floating point add.

Assuming the equation is correct and that the higher order terms don't involve x, I would probably compute the lookup table at startup using the floating point library that is already being linked.

The assumptions are:  'k' is truly a constant, never to be changed and 'x' doesn't get involved in the correction factors.

[T3sl4co1l]

k only needs six bits, because it takes 51 values (0 to 500 in steps of 10, inclusive?), which fits nicely into a 64-count field.

Probably round it up to 8 bits, because why bother packing bits.

Does x have to be floating?  What does it come from?

So, divide k by 10, and multiply everything else accordingly.

That's the first step.

Tim

[BrianHG]

Just so you know, if you don't care about processing speed, in PIC C, even the 8 bit MCU varieties, if you define x, and/or y, and any other variable as a float, they will be a 32 bit floats and just let the compiler do the work on any mathematical equation or function you like.

Do not trouble yourself with such details unless you really need super processing speed, or need to save every ounce of program space which the compiler would generate code to compute the floating point functions.

Just pretend you 8 bit PIC is a 32 bit floating point CPU and program away.  Let the compiler work out all the finer details in the background such is the purpose of a high level language like C instead of programming the PIC in assembly.

You may also mix variable types, like making Y and int (16 bit integer), x a float or double, k a char (8 bit integer).  The compiler will work things out.

[aiq25]

Thanks for all the tips. I don't think I was clear enough, both "x" and "k" are variables (they change over time). "x" and "k" are sensor information. Based on this information I need to calculate "y".

[Howardlong]

Thanks for all the tips. I don't think I was clear enough, both "x" and "k" are variables (they change over time). "x" and "k" are sensor information. Based on this information I need to calculate "y".

In your OP, k can only have values 0 to 500 in increments of 10, then as mentioned by another poster, that leaves the equation to the RHS of the "y = x +" with only 51 values, which could be precomputed and stored ahead of time, leaving you only with an addition to perform.

Is there a particular reason to switch between fixed and floating point? That square root is going to be the slowest part whether you're in fixed or floating point. A perfect reason to pre-calculate a LUT.

[aiq25]

In your OP, k can only have values 0 to 500 in increments of 10, then as mentioned by another poster, that leaves the equation to the RHS of the "y = x +" with only 51 values, which could be precomputed and stored ahead of time, leaving you only with an addition to perform.

Is there a particular reason to switch between fixed and floating point? That square root is going to be the slowest part whether you're in fixed or floating point. A perfect reason to pre-calculate a LUT.

I forgot about the values of "k".  Now it makes sense.

I prefer to use floating point but that's not the procedure used for the project I'm working on (the other team members only use fixed point math).

[rstofer]

Have you actually verified that equation?  At a minimum, I would put it in a spreadsheet and iterate over min/max values of sensor data and values 'k'.

You stated that the output 'y' would range from 0 - 100 but if the sensor reading is 150, y is never less than 149.674 at k=90 and for the same k and a sensor input of 0, y=-0.326.

Assuming (always a bad idea) that my code is correct, I get the values in the attachment:

One of the things you will deal with is a loss of precision.  You have a value of .125*10^-4 and a value of 10^2 so this takes about 6 digits to represent yet your output is only 4 digits.  In any event, fixed point is simply lining up the decimal points and doing the math.  Floating point differs only in the idea that the value is shifted left as far as possible and the exponent manipulated to account for the shift.  By shifting, floating point retains as much precision as possible.  Fixed point just loses the precision when it runs out of range.

[rstofer]

Once you determine a fixed point notation and the appropriate algorithms, it would be worthwhile to check the precision against a floating point solution.  Any loss of precision will be easy to spot.

[rstofer]

Mathworks (Matlab) has a Fixed Point Designer tool that might be interesting:

https://www.mathworks.com/products/fixed-point-designer.html

[SebG]

The formula can be simplified.  Since k is multiple of 10 and k^2 will be multiple of 100 so the constant .00000125 can me be multiplied by 100 which is 0.00125 and k should be in multiples of 1.  Then .00125 can be factored into 2^(-3) / 100.  So the 2^(-3) can be easily accomplished by shifting the k^2 result to the right 3 times (since bit shift to the right is essentially divide by 2). so the 0.0000125*k^2 term can be accomplished as follows: ensure k is multiple of 1 (not 10) then multiply it by itself (not a processor intensive operation), then bit shift it right 3 times, then divide by 100 (8-bit value). 

The other part would be 0.45*k.  By scaling k it would be an 8-bit value what also makes the code smaller/faster. If you want to represent 0.45 using a 8-bit fraction then you can approximate it as b'01110011' which would equal to .44921875 so all you need to do for that term is multiply 0x73 * k then the 16-bit result would be interpreted as 8-upper-bits as the integer and 8-lower-bits as the fraction.

[SebG]

furthermore division by 100 can be approximated by multiplication by .010009765625 which is b'0000 0010 1001' so multiply a value by 0x29 and then the whole 16 bit value should be bit shifted 4 bits to the right that is the upper 4 bits are the integer and the lower 12 bits as the fraction.

[SebG]

This way you can create one function that multiplies two 8-bit values and gives you a 16-bit result which you would use 3 times: k*k, the multiplication by 0x73 and by 0x29. The rest would be addition and bit shifting.

[bson]

Floating point isn't that different from fixed-point, and fixed-point isn't much benefit when the value can't fit in a register.  With a 16, 32, or 64 bit GPR file there are benefits, but an 8-bitter like a PIC that uses static storage for locals with non-reentrant code generation, not so much.  Two 16-bit fixed points (e.g. Q1.15) are multiplied by keeping the high 16 bits of the result.  Two 16.8 floating points are multiplied the same way, plus the two 8-bit exponents are added.  The difference is trivial when 24-bit values are managed as 8-bit bytes statically anyway.  Especially on PIC which can trivially add two memory locations/"registers" with minimal fuss.  (No fetching it relative to the SP or, sign extending to 32 bits, etc.)  The main difference is with floating point the compiler knows what's going on and can decompose and optimize based on intent, which may not be clear from rolling your own fixed-point.  In addition it will leverage a runtime and library that has been optimized and will use the proper hardware multiply and other bits and pieces available.  The compiler can loop unroll and move around normalization for instance (like the removal of leading zeros, adding them to the exponent).  If it were me I'd start implementing it in floating point and see if that's fast enough.  At some point you know it does the right thing, and if that's not fast enough you now have a baseline to beat and functionally A-B test against.  (Hmm, not working?  Is it my fixed-point DIY hack or the algorithm?  To test: recompile, enabling the floating point version and check.)

[NorthGuy]

Two 16-bit fixed points (e.g. Q1.15) are multiplied by keeping the high 16 bits of the result.  Two 16.8 floating points are multiplied the same way, plus the two 8-bit exponents are added.  The difference is trivial when 24-bit values are managed as 8-bit bytes statically anyway.

Also add the extra efforts to normalize the result. Because of the normalization, you cannot just take the highest 16 bits of the result, you need to figure out which 16-bits to take, then you need to shift the desired 16 bits into the place.

Also, you should extend your comparison to addition and subtraction. You cannot disregard them, can you?

[nuno]

Generically speaking, you need to pick an integer unit (1), that can represent your smallest value. Let's call it Unit. It could be 1000 if you wanted to be able to represent numbers as small as 0.001, or even better, 1024 (a power of 2).

Then you need a way to convert a real number to fixed point. That is done by multiplying it by your fixed point Unit and round it to the nearest integer.

Then you need to know how to add, which is just add.

Then you need to know how to multiply. Assuming both of the operands are in fixed point (multiplied by Unit and rounded to nearest integer), if you just multiply them you'll get the "real" number multiplied by Unit^2; so you need to divide by Unit after multiplication.

Then you need to know how to divide. Again assuming both operands are in fixed point, if you just divide them you'll loose the Unit scaling, since Unit/Unit = 1. So you need to multiply the 1st operand by Unit (beware: you get a large number here) and then divide by the 2nd.

Then you may need to convert a fixed point to real: you float divide it by Unit.
Or to round it to integer: you add sign(value)*Unit/2 then integer divide by Unit.

These are the basics. There are caveats about errors (dividing and rounding introduce errors), but I'll leave you a tip: when dividing, always add 0.5 of the 2nd operand to the 1st and then divide, because integer division always rounds down and not to the nearest integer (11 div 4 = 2 but real result is 2.75, so nearest integer is 3 and not 2). Not "fixing" this division "error" will be visible in your applications.
You should also try to optimize the expressions, reduce operations and rearrange them such that divisions are done last - always keeping an eye on the number of bits you need to represent your intermediate results. Sometimes you don't need to convert one of the operands to fixed point, such as when doing a multiply if you have 1 operand in fixed point and the other you know is an integer.

If you sit down and simulate the operations with some cases, you'll see it's obvious how calculations need to be done.


p.s. Please fix the topic's subject so that eases search

[NorthGuy]

Generically speaking, you need to pick an integer unit (1), that can represent your smallest value. Let's call it Unit. It could be 1000 if you wanted to be able to represent numbers as small as 0.001, or even better, 1024 (a power of 2).

To add to this. This doesn't have to be an abstract unit. For example, instead of volts, you can use millivolts. Then you do all your calculations in millivolts.

[aiq25]

Thanks for all the replies guys. I was spacing out and didn't think through the equation and the fixed point math conversion.

I have this working now.