3

I'm currently doing a practice assignment for my Discrete Structures class, and the assignment is the following:

"The algorithm below represents an attempt to print out a table of cubes of numbers from 0.1 to 10 in steps of 0.1. Explain the problem that might arise if the algorithm is implemented on a computer: 

x = 0.0
Repeat
    x = x + 0.1
    x_cubed = x^3
    Output x, x_cubed
    until x = 10.0

This is pseudocode, so I don't think that the error is about syntax. I rewrote the code in java and ran it. If I put (x != 10.0) as a condition, the program never stops, because for some reason 0.2 + 0.1 results in 0.30000000000000004, which makes it so that x never becomes precisely 10.0. However, I don't know if this is the problem that the professor is looking for, as it might be an Eclipse or Java problem.

Can somebody give me a hand with this exercise? Thank you!

user1234SI.
  • 1,812
  • 1
  • 8
  • 22
Vento
  • 33
  • 3
  • 7
    Does this answer your question? [Is floating point math broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) – OH GOD SPIDERS Feb 04 '20 at 10:12
  • 2
    "I don't know if this is the problem that the professor is looking for" - yes, I'd guess that is it, at least when x is a floating point type (as opposed to a decimal type as some languages have) – Rup Feb 04 '20 at 10:14
  • *x never becomes precisely 10.0*. IMHO this is **the** problem to find in this algo. The test should look like `abs(x - 10.0) < epsilon)` with `epsilon` being a small number (typically 10E-6 or smaller) – Serge Ballesta Feb 04 '20 at 10:16
  • 1
    @SergeBallesta way to complicated for this simple case, `x >= 10.0` will do. – Gyro Gearless Feb 04 '20 at 10:19
  • @GyroGearless: `abs(x - val) < epsilon` is the most common idiom to test for pseudo equalitity in the floating point world. That is the reason why I suggested it to OP. BTW `x >=10.0` needs a second test, because is could stop at 10.0 + epsilon or 11.0 - epsilon... – Serge Ballesta Feb 04 '20 at 10:24
  • *it might be an Eclipse or Java problem* - it is not, but even if it is, Eclipse or Java are things you might use to implement the algorithm "on a computer", so it would still be a correct answer (and the question's wording implies the correct answer is unique). – kaya3 Feb 04 '20 at 12:58

2 Answers2

4

Dialecticus has it right: comparing computed floats for equality is dangerous. Due to some numbers not being perfectly representable in base-two (e.g., 0.1), these will only ever be approximately correct.

You can use integers as he suggests, but I'd make one further adjustment: rather than computing x[n+1] = x[n] + dx, consider computing x[n+1] = dx * i[n+1]. In other words, don't use repeated addition (which may accumulate large errors over time); instead, calculate the value of x de novo at each iteration from the integer being iterated and the floating-point step (0.1 in this case). This will not accumulate errors over time in the same way. I encourage you to try this by comparing the millionth value obtained by repeated addition vs direct multiplication at each step.

EDIT: I had a free minute so I decided to do this test myself.

<html>
 <head>
  <title>
   Floating Point Test
  </title>
 </head>
 <body>
  <input type="button" id="btnRun" value="Run" onclick="run();" />
  <br/>
  <textarea id="txtOutput" rows=20 cols=50></textarea>
  <script language="javascript">
    function run() {
        var add = 0.0;
        var mul = 0.0;
        var i = 0;
        var dx = 0.1;
        var lastPower = 1;
        var output = "";
        for (i = 0; i < 1000000000; i++) {
            add = add + dx;
            mul = dx * (i + 1);
            if (i + 1 >= lastPower) {
                output += "i=" + i + ", add=" + add + ", mul=" + mul + "\n";
                lastPower *= 10;
            }
        }
        document.getElementById("txtOutput").value = output;
    }
  </script> 
 </body>
</html>

The output looks like this:

i=0, add=0.1, mul=0.1
i=9, add=0.9999999999999999, mul=1
i=99, add=9.99999999999998, mul=10
i=999, add=99.9999999999986, mul=100
i=9999, add=1000.0000000001588, mul=1000
i=99999, add=10000.000000018848, mul=10000
i=999999, add=100000.00000133288, mul=100000
i=9999999, add=999999.9998389754, mul=1000000
i=99999999, add=9999999.98112945, mul=10000000
i=999999999, add=99999998.74541782, mul=100000000
Patrick87
  • 27,682
  • 3
  • 38
  • 73
2

Problem is that most of the time comparing a float for equality (until x = 10.0) will not work as one would expect. In your specific case one solution would be to use an integer for the loop, and another float when needed.

int i = 0
float x = 0.0
Repeat
    i = i + 1
    x = x + 0.1
    x_cubed = x^3
    Output x, x_cubed
    until i = 100
Dialecticus
  • 16,400
  • 7
  • 43
  • 103