This Is Why There Are So Many Ties In Swimming

From the excellent article “This Is Why There Are So Many Ties In Swimming“, ties in swimming are allowed by the sport’s governing body because of the inevitability of roundoff error.

In 1972, Sweden’s Gunnar Larsson beat American Tim McKee in the 400m individual medley by 0.002 seconds. That finish led the governing body to eliminate timing by a significant digit. But why?

In a 50 meter Olympic pool, at the current men’s world record 50m pace, a thousandth-of-a-second constitutes 2.39 millimeters of travel. FINA pool dimension regulations allow a tolerance of 3 centimeters in each lane, more than ten times that amount. Could you time swimmers to a thousandth-of-a-second? Sure, but you couldn’t guarantee the winning swimmer didn’t have a thousandth-of-a-second-shorter course to swim. (Attempting to construct a concrete pool to any tighter a tolerance is nearly impossible; the effective length of a pool can change depending on the ambient temperature, the water temperature, and even whether or not there are people in the pool itself.)

Combinatorics and Jason’s Deli (Part 3)

Jason’s Deli is one of my family’s favorite places for an inexpensive meal. Recently, I saw the following placard at our table advertising their salad bar:

fb_img_1470352586255.jpg

The small print says “Math performed by actual rocket scientist”; let’s see how the rocket scientist actually did this calculation.

In yesterday’s post, I showed that the rocket scientist correctly calculated

\displaystyle {49 \choose 5} = 1,906,884.

To impress upon customers just how large this number is, the advertisers imagine eating a different salad every day until all 1,906,884 possibilities had been exhausted. Since there are 365 days in a year, apparently the rocket scientist divided:

\displaystyle \frac{1,906,884}{365} = 5,224.3397...

Unfortunately, there’s a small problem: the rocket scientist forgot about leap years! Ignoring for now the adjustments of the Gregorian calendar (years divisible by 1000 but not 4000 aren’t leap years — so that 2000 was a leap year but 2100 won’t be), we should divide not by 365 but by 365.25:

\displaystyle \frac{1,906,884}{365} = 5,220.7638...

Over a span of 5,220 years, there might be 3 or 4 extra leap days in the above calculation (depending on when someone starts eating the salads), not enough to throw off the above calculation by too much. So the correct answer, rounded to the nearest integer, really should have been 5,221 years.

All this to say, ignoring leap years caused the rocket scientist to give an answer that was off by 3.

Calculator Errors: When Close Isn’t Close Enough (Index)

I’m using the Twelve Days of Christmas (and perhaps a few extra days besides) to do something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on how I remind students about Taylor series. I often use this series in a class like Differential Equations, when Taylor series are needed but my class has simply forgotten about what a Taylor series is and why it’s important.

Part 1: Propagation of small numerical errors.

Part 2: A tragedy during the 1991 Gulf War that was a direct result of calculator rounding.

 

 

 

 

Calculator errors: When close isn’t close enough (Part 2)

In the previous post, I gave a simple classroom demonstration to illustrate that some calculators only approximate an infinite decimal expansion with a terminating decimal expansion, and hence truncation errors can propagate. This example addresses the common student question, “What’s the big deal if I round off to a few decimal places?”

TItrunc1

(For what it’s worth, I’m aware that some current high-end calculators are miniature computer algebra systems and can formally handle an answer of \displaystyle \frac{1}{3} instead of its decimal expansion.)

Students may complain that the above exercise is artificial and unlikely to occur in real life. I would suggest following up with a real-world, non-artificial, and tragic example of an accident that happened in large part due to truncation error. This incident occurred during the first Gulf War in 1991 (perhaps ancient history to today’s students). I’m going to quote directly from the website http://www.ima.umn.edu/~arnold/disasters/patriot.html, published by Dr. Douglas Arnold at the University of Minnesota. Perhaps students don’t need to master the details of this explanation (a binary expansion as opposed to a decimal expansion might be a little abstract), but I think that this example illustrates truncation error vividly.

On February 25, 1991, during the Gulf War, an American Patriot Missile battery in Dharan, Saudi Arabia, failed to track and intercept an incoming Iraqi Scud missile. The Scud struck an American Army barracks, killing 28 soldiers and injuring around 100 other people. Patriot missile A report of the General Accounting office, GAO/IMTEC-92-26, entitled Patriot Missile Defense: Software Problem Led to System Failure at Dhahran, Saudi Arabia reported on the cause of the failure.

It turns out that the cause was an inaccurate calculation of the time since boot due to computer arithmetic errors. Specifically, the time in tenths of second as measured by the system’s internal clock was multiplied by 1/10 to produce the time in seconds. This calculation was performed using a 24 bit fixed point register. In particular, the value 1/10, which has a non-terminating binary expansion, was chopped at 24 bits after the radix point. The small chopping error, when multiplied by the large number giving the time in tenths of a second, led to a significant error.

Indeed, the Patriot battery had been up around 100 hours, and an easy calculation shows that the resulting time error due to the magnified chopping error was about 0.34 seconds.

The number 1/10 equals

\displaystyle \frac{1}{2^4} + \frac{1}{2^5} +\frac{1}{2^8} + \frac{1}{2^9} + \frac{1}{2^{12}} + \frac{1}{2^{13}} + \dots

In other words, the binary expansion of 1/10 is

0.0001100110011001100110011001100....

Now the 24 bit register in the Patriot stored instead

0.00011001100110011001100

introducing an error of

0.0000000000000000000000011001100... binary,

or about 0.000000095 decimal. Multiplying by the number of tenths of a second in 100 hours gives

0.000000095 \times 100 \times 60 \times 60 \times 10=0.34.

A Scud travels at about 1,676 meters per second, and so travels more than half a kilometer in this time. This was far enough that the incoming Scud was outside the “range gate” that the Patriot tracked.

Ironically, the fact that the bad time calculation had been improved in some parts of the code, but not all, contributed to the problem, since it meant that the inaccuracies did not cancel.

The following paragraph is excerpted from the GAO report.

The range gate’s prediction of where the Scud will next appear is a function of the Scud’s known velocity and the time of the last radar detection. Velocity is a real number that can be expressed as a whole number and a decimal (e.g., 3750.2563…miles per hour). Time is kept continuously by the system’s internal clock in tenths of seconds but is expressed as an integer or whole number (e.g., 32, 33, 34…). The longer the system has been running, the larger the number representing time. To predict where the Scud will next appear, both time and velocity must be expressed as real numbers. Because of the way the Patriot computer performs its calculations and the fact that its registers are only 24 bits long, the conversion of time from an integer to a real number cannot be any more precise than 24 bits. This conversion results in a loss of precision causing a less accurate time calculation. The effect of this inaccuracy on the range gate’s calculation is directly proportional to the target’s velocity and the length of the the system has been running. Consequently, performing the conversion after the Patriot has been running continuously for extended periods causes the range gate to shift away from the center of the target, making it less likely that the target, in this case a Scud, will be successfully intercepted.

green line

A quick note of clarification. To verify the binary expansion of 1/10, we use the formula for an infinite geometric series.

S = \displaystyle \left(\frac{1}{2^4} + \frac{1}{2^5}\right) +\left(\frac{1}{2^8} + \frac{1}{2^9}\right) + \left(\frac{1}{2^{12}} + \frac{1}{2^{13}}\right) + \dots

S = \displaystyle \frac{3}{2^5} + \frac{3}{2^9} + \frac{3}{2^{13}} + \dots

S = \displaystyle \frac{\displaystyle \frac{3}{2^5}}{\quad \displaystyle 1 - \frac{1}{2^4} \quad}

S = \displaystyle \frac{\displaystyle \frac{3}{32}}{\quad \displaystyle \frac{15}{16} \quad}

S = \displaystyle \frac{3}{32} \times \frac{16}{15}

S = \displaystyle \frac{1}{10}

OK, that verifies the answer. Still, a curious student may wonder how one earth one could directly convert 1/10 into binary without knowing the above series ahead of time. I will address this question in a future post.

Calculator errors: When close isn’t close enough (Part 1)

Far too often, students settle for a numerical approximation of a solution that can be found exactly. To give an extreme example, I have met quite intelligent college students who were convinced that \displaystyle \frac{1}{3} was literally equal to 0.3.

That’s an extreme example of something that nearly all students do — round off a complicated answer to a fixed number of decimal places. In trigonometry, many students will compute \sin \left( \cos^{-1} 0.3 \right) by plugging into a calculator and reporting the first three to six decimal places, like 0.95394. This is especially disappointing when there are accessible techniques for getting the exact answer (in this case, \displaystyle \frac{\sqrt{91}}{10}) without using a calculator at all.

pictsqrt9110

TIsqrt9110

Unfortunately, even maintaining eight, nine, or ten decimal places of accuracy may not be good enough, as errors tend to propagate as a calculation continues. I’m sure every math teacher has an example where the correct answer was exactly $\displaystyle\frac{3}{2}$ but students returned an answer of 1.4927 or 1.5031 because of roundoff errors.

Students may ask, “What’s the big deal if I round off to five decimal places?” Here’s a simple example — which can be quickly demonstrated in a classroom — of how such truncation errors can propagate. I’m going to generate a recursive sequence. I will start with \displaystyle \frac{1}{3}. Then I will alternate multiplying by 1000 and then subtracting 333. More mathematically,

 a_1 = \displaystyle \frac{1}{3}

a_{2n} = 1000 a_{2n-1}

a_{2n+1} = a_{2n} - 333 if n > 0

Here’s what happens exactly:

1000 \times \displaystyle \frac{1}{3} = \displaystyle \frac{1000}{3} = \displaystyle 333\frac{1}{3} = 333.\overline{3}

\displaystyle 333\frac{1}{3} - 333 = \displaystyle \frac{1}{3} = 0.\overline{3}

So, repeating these two steps, the sequence alternates between \displaystyle \frac{1}{3} and \displaystyle 333\frac{1}{3}.

But looks what happens if I calculate the first twelve terms of this sequence on a calculator.

TItrunc1

Notice that by the time I reach a_{11}, the terms of the sequence are negative, which is clearly incorrect.

So what happened?

This is a natural by-product of the finite storage of a calculator. The calculator doesn’t store infinitely many digits of $\displaystyle \frac{1}{3}$ in memory because a calculator doesn’t possess an infinite amount of memory. Instead, what gets stored is something like the terminating decimal 0.33333333333333, with about fourteen 3s. (Of course, only the first ten digits are actually displayed.)

So multiplying by 1000 and then subtracting 333 produces a new and different terminating decimal with three less 3s. Do this enough times, and you end up with negative numbers.