Rounding errors

Something has happened to calculators while I wasn’t using them. I am hoping somebody reading this will know more about it than I do.

The story begins with the number theory course I am teaching this year, and a link-up between continued fractions (which form a significant part of the course), Euclid’s algorithm, and the Pythagorean proof of the irrationality of √2.

We think of the division algorithm as operating on integers: if m and n are positive integers, then there exist a unique quotient q and remainder r, with 0≤r<n, such that m = nq+r. Euclid, however, worked with lengths rather than numbers; he showed that, if we were given a unit length and a length x, then we can (by taking the largest possible number of unit lengths away from x) work out the integer and fractional parts of x: x = ⌊x⌋+{x}, where {x} is the fractional part. Now if x is the rational number m/n, we have ⌊x⌋ = q and {x} = r/n, so that m/n = q+(r/n), as required.

Now, if r ≠ 0, we can write this equation as m/n = q+1/(n/r), and apply the division algorithm to n/r. Iterating this until we obtain a remainder of 0 is precisely Euclid’s algorithm for the greatest common divisor of m and n, but also it produces the continued fraction for the rational number m/n.

In a lecture at Queen Mary a few years ago, the historian David Fowler argued that the Pythagoreans may have proved the irrationality of √2 by these techniques (using common themes of Greek mathematics) rather than by the modern textbook method (using properties of integers somewhat foreign to the Greeks). The argument goes like this.

Let x = (S+D)/S, where S and D are the side and diagonal of a square. Since all squares are similar, the value of x is independent of the square we choose. In the diagram above, we have a smaller square with side s and diagonal d; and we see that S = s+d, and D = 2s+d. Some simple manipulation shows that (S+D)/S = 2+s/(s+d), or in other words,

x = 2+1/x.

So the Euclidean algorithm, which terminates when applied to any rational number, in Fowler’s words “spins its wheels” when applied to the quantity x, which is thus irrational. Of course, x = 1+√2.

Last week I set the class a question which began with finding the continued fraction for √45, and proceeded to find solutions to Pell’s equation x²−45y² = 1. The continued fraction begins with 6 (since ⌊√45⌋ = 6), and continues 1, 2, 2, 2, 1, 12 and then repeats with period 6. The repetition is guaranteed because the number we apply the algorithm to after the seventh step is identical to that after the first step (namely 1/(√45−6)).

One student did it on a calculator instead. He obtained the quotients 6, 1, 2, 2, 2, 1, 12, 6, 1, 2, 2, 2, 1, 10, and failing to notice that periodicity had failed, wrote down the answer which is actually correct. The mistake, of course, was caused by rounding errors in his calculator. So much, so expected.

I don’t any more have a calculator in my pocket, but I have one (a version of gcalc) on my computer at work and on my new laptop. To my amazement, they both gave the correct answer. Moreover, subtracting the “remainder” at the first stage from the “remainder” at the seventh yielded 0 (well, it yielded a number which the calculator displayed as 0, and which remained 0 even after multiplying by a very large power of 10).

My hypothesis is that these calculators can do exact calculations in quadratic number fields, and obtain the correct answer by the method I expected the students to use. Does anybody know whether this is right?

While I had the calculator on my laptop running, I noticed that it can do various other tricks, including:

• factorisation: it took a perceptible fraction of a second to find the factors of the fifth Fermat number, first computed by Euler;
• modular arithmetic: it calculated 2³⁴¹ mod 341 almost instantaneously;
• long integers: it gave all the digits of 100!, for example.