When the calculator lies
Tonight's idea
Take \(x = \tfrac13\) and apply the rule \(x \to 10x - 3\). You get \(\tfrac{10}{3} - 3 = \tfrac13\). Apply it again and you get \(\tfrac13\) again, for ever. A rule applied over and over like this is called a recurrence.
Now try it on a calculator. It cannot hold \(\tfrac13\). It holds something like 0.33333333, which is too small by a tiny error. Say the stored number is \(\tfrac13 + e\). The rule turns it into \(10\left(\tfrac13 + e\right) - 3 = \tfrac13 + 10e\).
Each exact step of \(x \to 10x - 3\) multiplies the error by exactly 10. After \(n\) steps an error \(e\) has become \(10^n e\).
So an error in the eighth decimal place reaches the first decimal place in seven steps. Every step is done correctly, yet the answer is nonsense. The calculator is not broken. The recurrence is unstable: it magnifies whatever error it is given.
Some recurrences shrink errors instead, and they forgive a rounded start. Others, called chaotic, magnify errors at an uneven rate. Weather behaves like that, which limits how far ahead any computer can forecast.
Watch one: an eight-digit calculator
Here is a simple model of a calculator: it keeps eight digits after the decimal point and drops the rest. Real machines differ in the details. Type \(1 \div 3\) and it stores 0.33333333. The true value is \(0.3333333333\ldots\), so the stored number is too small by \(0.0000000033\ldots\), about \(3.3 \times 10^{-9}\).
Multiplying by 10 slides every digit one place left. The calculator has no ninth 3 to bring in, so each step loses a 3.
| Step | 0 | 1 | 2 | 3 | … | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| \(x\) | 0.33333333 | 0.3333333 | 0.333333 | 0.33333 | … | 0.33 | 0.3 | 0 | −3 | −33 |
At step 7 it shows 0.3, wrong by \(0.0333\ldots\), which is \(10^7\) times the starting error. At step 8 it shows 0, and from then on it runs away: \(-3, -33, -333, \ldots\) The exact answer is still \(\tfrac13\).
A computer works in binary and keeps about 16 significant digits, so it lasts about twice as long. Python on our computer printed 0.3333333333333333 at step 0, 0.3333330372738601 at step 10, 0.3037273860099958 at step 15 and −2.6272613990004174 at step 17.
Results depend on the machine. The rule \(x \to 11x - 1\) holds 0.1 fixed, because \(1.1 - 1 = 0.1\). A calculator that works in decimal stores 0.1 exactly and never drifts. Binary cannot store 0.1 exactly, and on our computer the same rule had drifted to 4.18 by step 17.
Your turn
- Start at \(x = 0.34\) and apply \(x \to 10x - 3\) four times, exactly, by hand. (a) Write down the four results. (b) Subtract \(\tfrac13 = 0.3333\ldots\) from the start and from each result. What happens to the error at each step? (c) Some programs store fractions exactly, as a pair of whole numbers. What would such a program show after 100 steps starting from \(\tfrac13\)?
- Now run the rule backwards: \(x \to \dfrac{x + 3}{10}\). (a) Start from the wild guess \(x = 5\) and compute four steps. (b) Put \(x = \tfrac13 + e\) into the rule and simplify. What happens to the error? (c) Starting from 5, how many steps until \(x\) is within 0.000001 of \(\tfrac13\)?
- The rule \(x \to 4x(1 - x)\) is chaotic. The table follows two starts, 0.3 and 0.301. Each entry was computed without rounding along the way, then rounded to three decimal places.
(a) Check the two step 1 entries yourself. (b) At which step do the two rows first disagree in the first decimal place? (c) Find the gap between the rows at steps 0, 5 and 10. Compare with a gap that doubles at every step. (d) Does the gap grow at every step? Look at steps 8 and 9.Step 0 1 2 3 4 5 6 7 8 9 10 from 0.3 0.300 0.840 0.538 0.994 0.022 0.088 0.321 0.872 0.448 0.989 0.043 from 0.301 0.301 0.842 0.533 0.996 0.018 0.069 0.258 0.765 0.719 0.808 0.620 - Here is a made-up model of a weather forecast. Today's temperature is known to within 1 °C. The error in the forecast doubles every 2 days, and the forecast is useless once the error reaches 16 °C. (a) On which day does the forecast become useless? (b) Better instruments cut today's error to 0.25 °C. How many extra days does that buy? (c) How many times smaller than 1 °C must today's error be for the forecast to stay useful until day 22? (d) Why can a forecast for three weeks ahead not be precise?
Stretch: Fibonacci run backwards
The number \(g = 0.6180339887\ldots\) satisfies \(g^2 = 1 - g\), so \(g^{n+1} = g^{n-1} - g^n\): each power of \(g\) is the one two back minus the one before it. Start with 1 and the rounded value 0.618 and carry on by subtraction alone, exactly: \(1,\ 0.618,\ 0.382,\ 0.236, \ldots\) up to the entry for \(g^{14}\). The true powers are all positive and keep shrinking. Where does your list go wrong? Then call the starting error \(e\), follow it through the rule, and say which famous numbers appear.
Answers
- (a) \(0.4,\ 1,\ 7,\ 67\). (b) The errors are \(0.00666\ldots\) at the start, then \(0.0666\ldots,\ 0.666\ldots,\ 6.666\ldots,\ 66.666\ldots\) Each step multiplies the error by exactly 10, as the callout says. Starting too big sends you off upwards; starting too small sends you off downwards. (c) It shows \(\tfrac13\) at every step, because \(\tfrac{10}{3} - \tfrac93 = \tfrac13\) with no rounding at all. Exact arithmetic like this is one way computers help mathematicians. The price is that exact fractions can grow very long in other problems.
- (a) \(0.8,\ 0.38,\ 0.338,\ 0.3338\). (b) \(\dfrac{\tfrac13 + e + 3}{10} = \dfrac{\tfrac{10}{3} + e}{10} = \tfrac13 + \dfrac{e}{10}\). Each step divides the error by 10, so any start is pulled towards \(\tfrac13\). Running an unstable rule backwards made it stable. (c) The starting error is \(5 - \tfrac13 = 4.666\ldots\) After 6 steps it is \(0.0000046\ldots\), still too big. After 7 steps it is \(0.00000046\ldots\), so 7 steps.
- (a) \(4 \times 0.3 \times 0.7 = 0.84\) and \(4 \times 0.301 \times 0.699 = 0.841596\), which rounds to 0.842. (b) At step 6: 0.321 against 0.258. (c) The gaps are 0.001, then \(0.088 - 0.069 = 0.019\), then \(0.620 - 0.043 = 0.577\). Doubling every step would give 0.001, 0.032 and 1.024. So the gap grows roughly as fast as doubling, a little slower here. (d) No. The gap is \(0.719 - 0.448 = 0.271\) at step 8 and \(0.989 - 0.808 = 0.181\) at step 9. Chaos magnifies errors on average, not at a steady rate. Both rows stay between 0 and 1, so the gap cannot pass 1. By step 10 the second row tells you almost nothing about the first.
- (a) The error runs 1, 2, 4, 8, 16 °C on days 0, 2, 4, 6, 8. Useless on day 8. (b) From 0.25 °C it takes two more doublings to reach 1 °C, so 4 extra days: useless on day 12. (c) Day 22 is 14 days after day 8, which is 7 more doublings, so the error must be \(2^7 = 128\) times smaller, about 0.008 °C. (d) Each extra 2 days costs instruments twice as good, everywhere at once. In this model three weeks needs every reading good to about 0.008 °C, and the demand doubles again for every 2 days after that. The numbers here are invented and real weather is far more complicated, but real forecasts do magnify small errors. In 1961 Edward Lorenz restarted a computer weather model from 0.506 instead of 0.506127 and watched the two runs drift completely apart.
Stretch. The list runs \(1,\ 0.618,\ 0.382,\ 0.236,\ 0.146,\ 0.090,\ 0.056,\ 0.034,\ 0.022,\ 0.012,\ 0.010,\ 0.002,\ 0.008,\ -0.006,\ 0.014\). The entry for \(g^{12}\) is bigger than the one before it, and the entry for \(g^{13}\) is negative. The true values are \(g^{12} = 0.0031\) and \(g^{13} = 0.0019\). Errors: the first two are 0 and \(e\), where \(e = 0.618 - g \approx -0.000034\). Errors obey the same subtraction rule, so they run \(0,\ e,\ -e,\ 2e,\ -3e,\ 5e,\ -8e, \ldots\) Those are the Fibonacci numbers with alternating signs, because \(F_{n-1} = F_{n+1} - F_n\) is the Fibonacci rule read backwards. At \(g^{13}\) the error is \(233e \approx -0.0079\), bigger in size than the true value. The true powers shrink by a factor of about 0.618 each step while the error grows by about 1.618, so the error must win in the end.