# 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