Starting pointIn the explaination on how does the DDA works on wikipedia,
I always ask myself why and how does the integer implementation
works. I tried to decompose the code and in fact it was obvious. The
fraction is inside.
Simple testfloat value = 3.0f;
float inc = 6.0f / 7.0f; // It is equal to 0.857143
do 10000 times
value = value + inc;
// Do something with integral part of value
At the end of the loop value is 8573.664063.
The theorical ending value is 8574.428571
The difference is 0.764508, just for a couple of adds.
simple test show us that even if the float, double, real, or whatever
is your favourite floating point number, there are some precision
involved. IEEE floats are known to have an average of 3% of error. How
to do to have the exact result ? We will work with exactly known
FractionA fraction is just a numerator divided by a denominator.
Pseudo-C code for dealing with fractions.
typedef struct _SDDA
sint32 ValFrac; // Fractionnal part of Val (in the range [0,Denominator[ )
sint32 IncrInt; // Integer part of the increment
sint32 IncrFrac; // Fractionnal part of the increment (in the range [0,Denominator[ )
sint32 Denominator; // The denominator is the fractionnal part ratio
void SDDA_SetFraction(SDDA *pDDA, sint32 Numerator, sint32 Denominator)
pDDA->IncrInt = Numerator / Denominator;
pDDA->IncrFrac = Numerator - pDDA->IncrInt * Denominator;
pDDA->Denominator = Denominator;
if (pDDA->IncrFrac < 0) // For negative factional part of the increment
pDDA->IncrInt--; // Because this is a floor (floor(-26.73) == -27)
pDDA->IncrFrac += Denominator; // Complement to '1' (denominator) the fractional part
void SDDA_Init(SDDA *pDDA, sint32 Value, sint32 Numerator, sint32 Denominator)
pDDA->Val = Value;
pDDA->ValFrac = 0;
SDDA_SetFraction(pDDA, Numerator, Denominator);
void SDDA_Inc(SDDA *pDDA)
pDDA->ValFrac += pDDA->IncrFrac;
if (pDDA->ValFrac >= pDDA->Denominator)
pDDA->Val += pDDA->IncrInt + 1;
pDDA->ValFrac -= pDDA->Denominator;
pDDA->Val += pDDA->IncrInt;
The new test becomes:
SDDA_Init(&d, 3, 6, 7);
do 10000 times
// Do something with integral part of value (d.Val)
At the end of the execution we have
d.Val = 8574
d.ValFrac = 3
The denominator is 7 and 3/7= 0.428571
So the total float value is 8574.428571 which is perfectly the same as the theorical ending value.
ConclusionIf you have to iterate with float, just don't. It always lead to an error accumulation.
Try to think in term of fraction, this is the most accurate and performant on computer.
Back to matthPage