Time Steps and Binary Representation in Computer Simulations

TL;DR Using a time step whose decimal representation isn’t exactly representable in binary may lead to confusion over how much total time has elapsed in a computer simulation. It may be worth discussing in class, or worthy of an investigative or inquiry activity.

Sometimes, a problem comes up repeatedly over the years and every time I “discover” it I have to search for the resources I used last time to explain the problem. I’m writing this post mainly as a collection of thoughts and resources to which I can refer students when this issue inevitably arises again. The particular problem I describe here probably isn’t a huge one, and indeed I can’t recall any of my own students ever raising it. It’s something that I notice every semester when I’m introducing computation.

So here’s the problem. Say you want to simulate a physical system for a total duration of 1 s of time, and  you decide to use a time step of 1/10 of a second, 0.1 s. So you write a GlowScript program to carry out your simulation. Your code might look something like this example, presented in Trinket so you can experiment with the code.

 

Again, you want to simulate a physical system for a total duration of 1 s with a time step of 0.1 s, which means your simulation should perform ten loops. Now, look at the program’s output. The loop executed eleven, not ten, times, and the simulation apparently lasted for 1.1 s, which is not what you wanted to have happen. So, you decide to decrease the time step by, say, a factor of ten, making it 0.01 s. Modify the code in the Trinket above to reflect this change and run it to see what happens. You should see that the program now works as intended, with the loop executing one hundred times for a total of 1 s of elapsed simulated time. Feeling emboldened, you lengthen the total duration to 10 s. Again, modify the code and run it again to see what happens. This time you should find that the loop executes not one thousand times as expected, but one thousand one times and the simulation lasted for not 10 s, but 10.01 s. What’s going on here?

It seems that sometimes the choices of step size and total elapsed time give the results we expect and sometimes they don’t. This issue recently resurfaced on the GlowScript user forum hosted on Google Groups. As both Bruce Sherwood and Harlan Gilbert point out, the problem is that internally, floating point numbers can’t always be exactly represented in binary. Both Sherwood and Gilbert propose solutions.

One of Sherwood’s solutions is to modify the while loop’s criterion to account for the “fuzziness” of the internal representation of floating point numbers. Here’s a Trinket illustrating this solution.

 

Experiment with this solution to see if you find a combination of time step and total elapsed time that doesn’t match the obvious expectations.

Harlan Gilbert proposes a solution in which one uses time steps that are exactly represented in binary. Specifically, this means time steps that are reciprocal integer powers of two. Here’s a Trinket illustrating this solution.

 

Once again, experiment with different settings for the power of two in the line defining deltat. Students may be interested in seeing that, for example, 1/8 s (0.125 s) works as expected, but decreasing that value by a factor of ten to 1/80 s (0.0125 s) doesn’t!

If I were to discuss this issue in class (and I’m not saying we should bring it up unless or until a student “discovers” it), I think I would first tend to use Sherwood’s solution, simply because it allows for more traditional changes in step size without having to worry about integer powers of two. I also don’t know whether or not I would intentionally bring this issue up because I worry that it might be a distraction. On the other hand, it’s a real issue that students should know about and understand sooner or later.

As always, feedback is welcome.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.