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.

Squares

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 x2−45y2 = 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 2341 mod 341 almost instantaneously;
  • long integers: it gave all the digits of 100!, for example.
Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , . Bookmark the permalink.

5 Responses to Rounding errors

  1. javier says:

    I am not aware on the internals of gcalc but some likely things happening here are:
    * Your computer/operating system is 64bits, whereas hand calculators operate with smaller registers, thus the enhanced precision.
    * If gcalc is reasonably programmed, it will be making use of GMP or MPIR or any other equally advanced arbitrary precision libraries, so going even further than the default 64 bit. The fact you can compute all the digits of 100! suggests this is the case.
    * It is also possible that gcalc is internally using NTL or a similar number theory library, which actually operates with quotients of polynomial rings, hence exact arithmetic in number fields. But I have the feeling that if this was the case your factorization should have been faster: in my desktop using sage the factorization of F_5 takes 45 microseconds, factorization of F_7 is about a tenth of a second. So my guess here is arbitrary precision library.

    • I tried multiplying the difference between the first and seventh remainders for the square root of 45 by 10^100, and then by 10^100 again. It was still zero.

      • javier says:

        That is not necessarily a sign of neither exact arithmetic nor arbitrary precision, and could be due to rounding. Look at the following example in sage:

        sage: R = RealField(10)
        sage: n = R(sqrt(2))
        sage: n
        1.4
        sage: n^2
        2.0
        sage: (n^2 – 2)*10^100
        0.00

        Here, I am setting n to be the numerical value square root of n with 10 (binary) digits of precision (I’m intentionally crippling the precision to make my point). If the error is already rounded to zero, multiplying by a big number won’t make it come back.

        Anyhow, as I said I am not familiar with gcalc, I am aware there are libraries for exact arithmetic with number fields (such as NTL or FLINT) so it might well be the case that gcalc makes use of either of them

      • javier says:

        I forgot to mention, the error might be rounded to zero or not in different precisions: in the above example, the error shows up if the precision is 20 (binary) digits and becomes 0 again if set to 32 digits.

      • Javier: thanks very much for your comments! They reinforce my feeling that a mathematician should never trust the result of a computation with real numbers …

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s