CODEWITHSUNDEEP
algorithmpseudocodediscrete-mathematics
Vento
Vento

Reputation: 23

Finding the cubes of numbers from 0.1 to 10, what's the problem in this algorithm?

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!

Upvotes: 2

Views: 185

Answers (2)

Patrick87
Patrick87

Reputation: 28312

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

Upvotes: 4

Dialecticus
Dialecticus

Reputation: 16759

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

Upvotes: 2

Related Questions