There are more exact numbers than you might know

There are lots of annoying problems a programmer can run into, when working with the inexact floating point numbers supported by common cpus. So the idea of using rational numbers

\frac{n}{d}

with arbitrary size integers n,d for floating point computation can be quite appealing. However, if you really try this in practice, you are likely to end up with unacceptable performance (for an example, see the post The Great Rational Explosion on this blog).
Another problem with the rationals is, that they don’t support lots of mathematical operations. For example, any prime will not have a rational square root and numbers like \pi and e are not rational.
This post is about the problem of the missing square roots. I will sketch how the rationals can be extended by some specific real numbers. The focus is on what can be done and not how it can be done.

The point of the following example is that we can extend the rational numbers by some new numbers such that we have the square root of 2 and are still able to perform the basic arithmetic operations, i.e. addition, subtraction, multiplication and division by non-zero numbers. And of course, we still want to have the absolute exactness of the rationals.
To achieve this goal, our new numbers can be represented as tuples (a,b) of rational numbers a,b. The idea is, that (a,b) stands for the real number

a+b\sqrt{2}

And now, a small miracle happens: If you have two of those new numbers then all of the basic arithmetic operations are again given as one of our new numbers! You can believe me or just check this for yourself now. So in total, we have extended the realm of exact calculation to real numbers which are of the form

a+b\sqrt{2}.

This is admittedly a bit lame, since we are still far away from calculating general square roots. But the miracle mentioned above is actually not so small and happens in way more generality: The real number \sqrt{2} that we added to the rationals is the solution of the polynomial equation

X^2=2 or equivalently X^2-2=0

and we can do the same thing with any irrational real number that is the solution of some polynomial equation

a_n X^n + a_{n-1} X^{n-1} + \dots + a_1 X^1 + a_0 = 0 or P(X)=0

(where a_n,\dots,a_0 are rational numbers).
For this general construction, the polynomial above has to be chosen such that n is as small as possible. Then the new numbers can be represented as tuples of length n. For the basic arithmetic operations, we think of a tuples (b_n,\dots,b_0) as the polynomial

b_n X^n+\dots b_1 X^1 + b_0

and define addition to be addition of those polynomials. To multiply two tuples, take the product of the polynomials and its remainder on division by P. You can check out how this recipie does the right thing in the example with P=X^2-2. To avoid confusion, let us put the polynomial defining in which extension of the rationals we are into the number. So know, a number is a tuple

(P,b_n,\dots,b_0).

In particular, there are extensions that contain a square root of an arbitrary rational. But if we look at, say, \sqrt{2} and \sqrt{3} we will get two extensions. So we have \sqrt{2} and \sqrt{3} but we can’t do anything that involves both of them. Or in other words, if we have two numbers, (P,b_n,\dots,b_0) and (Q,c_m,\dots,c_0) we don’t know how to perform basic arithmetic unless n=m and P=Q.

Here is an easy way to fix this: If we take a step back, we can realize that everything we did above doesn’t need specific features of the rational numbers. The basic arithmetic operations are enough. So we can apply the construction of new numbers including some root to an extension of the rationals. For the problem mentioned above, that would give us tuples of the form

(X^2-3, (X^2-2, a, b), (X^2-2, c, d))

– now with four rational numbers a,b,c,d.
The corresponding general pattern for an extension (of some extension …) is:

(P, a_0,\dots, a_n)

Where the numbers a_i are from some fixed extension and P is a polynomial with coefficients from this fixed extension. We also have to make sure, that P has a property called irreducible. It means that P has at least degree 1 and there is no pair of polynomials Q,R with lesser degree (and coefficients in the extension) such that their product P\cdot R is equal to P. If this is not the case, weird things will happen.
Note that if we keep extending our numbers on demand, we can now get square roots of everything, in fact, this even works for square roots of negative numbers. But there are some unmentioned problems, if we want to mix numbers from different towers of extensions. On the other hand, there are also lots of unmentioned possibilites: These construction are pretty general and they can also be applied to finite fields or some extension of the rationals which contains a trancendent element like \pi. But I will stop here since my goal of showing some exact representations of numbers that surprised myself once, is reached.

If you want to learn more about the mathematical background, this pdf might help. There is also a way to join two extensions to one of the form we discussed here, the key is this nice theorem: Primitive Element Theorem. There are lots of nice mathematical facts in this area. My former Algebra working group in Karlsruhe, in particular Fabian Ruoff, kindly reminded me of some of them over lunch, when I was discussing the topics of this post.
Then, there are of course implementations. Here is a class in the cgal library for square roots.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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