Infinite precision

Starting point

In 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 test

float 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
end do 

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.
This 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 fraction.

Fraction

A fraction is just a numerator divided by a denominator.

Pseudo-C code for dealing with fractions.

typedef struct _SDDA
{
  sint32 Val;
  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
} SDDA;

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;
  }
  else

  {
    pDDA->Val += pDDA->IncrInt;
  }
}


The new test becomes:
SDDA d;
SDDA_Init(&d, 3, 6, 7);
do 10000 times
  SDDA_Inc(&d);
   // Do something with integral part of value (d.Val)
end do 

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.

Conclusion

If 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