Advertisements

Archive for March 2nd, 2009

Fixed Point Arithmetic: Percentages

Problem: increment or decrement a variable by a fixed percentage, without using floating-point arithmetic routines. This is the sort of problem that crops up in microcontroller projects, because there’s just not enough storage for the floating-point library stuff and your program at the same time.

Suppose you want to increment the variable BaseNum by 10%. Using floating point, that’s just

BaseNum = 1.1 * BaseNum;

In fixed point, it would look like

BaseNum = (BaseNum * 11) / 10;

Similarly, to increment by 5%, you’d use

BaseNum = (BaseNum * 105) / 100;

The general idea is that you scale the operation to eliminate the fractional part, then chop off the scaling to get the final answer. The parentheses are vital: the multiplication must precede the division.

The integer division operator truncates any fractional part, it does not round. This becomes a nasty gotcha if you’re expecting the final value to change.

For example, incrementing 15 by 10% would look like

15 ->  165 -> 16

But incrementing 15 by 5% goes like

15 -> 1575 -> 15

For obvious reasons, you should make sure the multiplication can’t overflow. If you’re incrementing by 5% (multiplying by 105), then an int BaseNum can’t exceed 312, which might come as a surprise. Casting the operands to long int would be prudent for many problems:

BaseNum = ((long int)BaseNum * 105) / 100;

Suppose you want to increment BaseNum several times in succession, with that number stored in Ticks. With floating point, you could use the pow() function

BaseNum = BaseNum * pow(1.1,Ticks);

In fixed point, the same thing seems like it ought to work

BaseNum = (BaseNum * pow(11,Ticks)) / pow(10,Ticks);

Unfortunately, that idea runs out of gas pretty quickly: pow(11,9) falls just outside the range of a long int, so even if BaseNum is, say, 2, you’re screwed. It’s even worse for smaller percentages, as pow(105,5) is about 13e9.

One solution, which works well for reasonable values of Ticks, is to iterate the process

for (Counter = Ticks; Counter; --Counter)
{
    BaseNum = ((long int)BaseNum * 11) / 10;
}

That won’t overflow in the middle. However, if the division truncates away the increment you were expecting, then the loop just whirs for a while and accomplishes exactly nothing.

That could come as a surprise if you were expecting, say, five 5% increments to add up to a 28% boost: pow(1.05,5) = 1.276, right?

Bottom line: when you use fixed-point arithmetic, always check the low end of the range for underflow and the high end for overflow.

Hint: store the numerator and demoninator of the fixed-point percentage fraction in variables. You can’t decrement by the same percentage by just swapping the numerator and denominator, but it might be close enough for human-in-the-loop knob twiddling adjustments.

Memo to Self: always check for underflow and overflow!

Advertisements

2 Comments