Possible floating point error?

[TerryRitchie]

I have a routine that tracks multiple FPS rates within a master FPS rate. I noticed with certain values that it fails. My son actually created the routine for me a few years back. I showed him what was going on and we tracked it to a floating point error.

For example. The result of x should be 1 but instead the value .9999999 is given:

f = 2 / 454
x = 227 * f

(2 is the target FPS, 454 is the global FPS, 227 is the current global frame number)

I've already created a work around for this. My son's code is too precise for what I need. He's tracking the exact moment the frame changes, whereas I simply need to know the alternate frame number within the master FPS. His code:

Fraction = TargetFPS / GlobalFPS
x = CurrentGlobalFrameNumber * Fraction
IF INT(x) <> INT(x - Fraction) THEN ... (report that a frame change happened)

All I simply need is INT(x) for my purposes but the possibility of a floating point error may still exist in QB64. Am I correct in assuming this?

[Jack]

what happens if you do this instead?

Code: (Select All)

x = CurrentGlobalFrameNumber*TargetFPS/GlobalFPS

or

Code: (Select All)

x = CurrentGlobalFrameNumber*TargetFPS\GlobalFPS

TerryRitchie, binary floating point is inherently inaccurate

[JRace]

(@Jack beat me to it and said it more concisely.)

Steve has mentioned in previous posts how some numbers cannot be represented exactly in binary floating point, and that seems to be the case here.

That tiny error is not a bug, it's just because of the difference between our expectations and the way floats are represented internally.

That's why financial institutions prefer decimal math to binary.  If every $100 transfer is recorded as $99.99999, then those bank execs are going to have headaches.

In everyday use little errors like that can either cancel out over time or add up to something more noticeable.

(I seem to recall that in olden time some MS Basics would ever so slightly round floats before printing them to hide those ugly inaccuracies.)


Interesting.
f = 2 / 454
x = 227 * f
yields .9999999

while
x = (2 / 454) * 227
yields 1.

[DSMan195276]

For example. The result of x should be 1 but instead the value .9999999 is given:

f = 2 / 454
x = 227 * f

That's not a bug, that's just how floating point works. The number is stored in scientific notation with about 7 to 8 digits of precision (23 binary digits). If you take a look at the value you calculated in base 2, it's a repeating number of some kind, so it's impossible to store the exact value with only 23 binary digits. The fractional part gets cut off and you get a number close to the actual value of `2 / 454` but not the exact number. Once that has happened you end up with results like `.9999999` because your `f` is not exactly `1 / 227` when you multiply it by `227`.

Jack's suggestion is a good one and might avoid all the error. The evaluation order matters with floating point because if you do the multiplication first you avoid using the `1 / 227` value, instead you do `227 * 2` which is easily stored as an exact number in the 23 binary digits of precision.

[SMcNeill]

The problem with floating point is just the nature of the beast.  You're *always* going to have degrees of imperfections in floating point math.

Let me illustrate why, using base-10, standard math.  

Let's take two numbers and divide them together, to make a decimal value.  For illustration, I choose 1 and 3.

1 / 3 = 0.33333333... to however many digits of precision you want to go through.  SINGLE holds about 8 digits, DOUBLE 12, FLOAT 16 (or something like that).

So we take a SINGLE for 1 / 3...  the answer is 0.333333333 -- 8 digits of precision.

Now, let's take those 8 digits and multiply by 3: 0.33333333 * 3 = 0.99999999

It's not 1.   That loss of precision has now generated a basic Floating Point Imperfection for us.

And, at this point, you see some programs which try to be smart and round up the answer.  They basically say, "Hey!  0.99999999 is our max precision estimate for 1, so the answer is 1."

And then 0.33333333 * 3 = 1, and the world is good and everything makes sense!!

.....

At least it does until someone does math for the exact value 0.11111111 * 9.  They get 0.99999999, which we declared as "Meh, close enough to 1, so we call it 1," which is wrong.  

---

The basic root of the problem is we have no way to perfectly represent all fractions in decimal form.  

1/3 is impossible to represent perfectly in base-10.  

1/10 is impossible to represent perfectly in base-2 (binary).  

There's some simple rule to this, but I'm not certain I'm remembering it perfectly.  I think it's along the line of "ALL factors of the fractional denominator must be factors of the base, for perfect representation."

1/3, for example, fails in base-10 as 3 is not a factor of 10.
1/2, works in base 10, as 2 *is* a factor of 10.
1/4 works as 4 is just (2 * 2) and 2 is a factor of 10.
1/7 fails, as 7 is not a factor in 10.

[SMcNeill]

To highlight what I'm talking about above, let's do some really simple division and convert fractions to decimals:

1 / 1  =  1
1 / 2  =  .5
1 / 3  =  .3333333
1 / 4  =  .25
1 / 5  =  .2
1 / 6  =  .1666667
1 / 7  =  .1428571
1 / 8  =  .125
1 / 9  =  .1111111
1 / 10  =  .1
1 / 11  =  9.090909E-02
1 / 12  =  8.333334E-02
1 / 13  =  7.692308E-02
1 / 14  =  7.142857E-02
1 / 15  =  6.666667E-02
1 / 16  =  .0625
1 / 17  =  5.882353E-02
1 / 18  =  5.555556E-02
1 / 19  =  5.263158E-02
1 / 20  =  .05

Now, if we look at the factors of the denominators above, we see this:

1 / (1)
1 / (2)
1 / (3)
1 / (2 * 2)
1 / (5)
1 / (2 * 3)
1 / (7)
1 / (2 * 2 * 2)
1 / (3 * 3)
1 / (2 * 5)

Now, since this is base-10 math, the factors of base-10 would be (1 * 2 * 5)....

As long as our denominator ONLY has those factors (1, 2, or 5) in it, we can have PERFECT DECIMAL REPRESENTATION for our fraction.  1 / 20 *is* 0.05 -- perfectly!  No imperfections.  No rounding.  No "close enough", or repeating digits, or irrational never-ending numbers.  The demonimators of 20 are (1 * 2 * 2* 5), and those denominators match our base, so we can perfectly represent that value in decimal form.

---

And with that said, binary values (which is how a computer tends to store things), follows that *EXACT* same rule!

Base-2's factors are ....  (1 * 2).   

1 * 2... and that's it!!

So the *only* numbers which we can represent perfectly in binary are going have a denominator which factors to a power of 2.

1 / 2 -- yep!  WE can represent it perfectly in binary! 
1 / 4 -- yep!  We can represent it perfectly in binary!
1 / 6 -- nope...  6 is (2 * 3).  3 is NOT a factor of 2.  This is going to be an imperfect fraction and WILL leading to floating point errors over time.
1 / 8 -- yep!  We can represent it perfectly in binary!
1 / 10 -- nope...  10 is (2 * 5).  5 is NOT a factor of 2.  This is going to be an imperfect fraction.

.
.
.

Which means the only real frsctions we can represent perfectly and not have any sort of math issues with, in binary are all powers of 2.

Halves.  (1/2)
Fourths. (1/4, 2/4, 3/4)
Eighths. (1/8, 2/8, 3/8, 4/8, 5/8, 6/8, 7/8)
Sixteenths.
Thirthy-seconds.

Anything else is going to *always* be an imperfect representation and will, over time, add up to give floating point errors.

(Which is why if precision is important to your program, you might consider counting by 1/8 or 1/16, rather than by 1/10.)

---

And for those of the "Show Me" variety of people, let's take a look at how 1 / 6 performs...  I predicted above that it'd glitch over time as it's an "imperfect representation" in base-2.   Try this and see for yourself:

Code: (Select All)

i = 1 / 6



For y = 0 To 9

    For x = 1 To 60

        a = a + i

        Print 60 * y + x, a

    Next

    Print "See any problem with the math yet?"

    Sleep

Next

[TerryRitchie]

Thanks for the insights everyone. Sorry to have reported this as a possible bug. And yes, this is interesting:

Interesting.
f = 2 / 454
x = 227 * f
yields .9999999

while
x = (2 / 454) * 227
yields 1.

Knowing this perhaps I can rework the code to report the exact time of change again if ever needed.

[FellippeHeitor]

Mandatory link repost: https://0.30000000000000004.com/

[TerryRitchie]

Mandatory link repost: https://0.30000000000000004.com/

I see I'm in good company then, LOL. Thanks for the link Fellippe, very interesting and informative.