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

with arbitrary size integers 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 and 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 of rational numbers . The idea is, that stands for the real number

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

.

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 that we added to the rationals is the solution of the polynomial equation

or equivalently

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

or

(where are rational numbers).

For this general construction, the polynomial above has to be chosen such that is as small as possible. Then the new numbers can be represented as tuples of length . For the basic arithmetic operations, we think of a tuples as the polynomial

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 . You can check out how this recipie does the right thing in the example with . 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

.

In particular, there are extensions that contain a square root of an arbitrary rational. But if we look at, say, and we will get two extensions. So we have and but we can’t do anything that involves both of them. Or in other words, if we have two numbers, and we don’t know how to perform basic arithmetic unless and .

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

– now with four rational numbers .

The corresponding general pattern for an extension (of some extension …) is:

Where the numbers are from some fixed extension and is a polynomial with coefficients *from this fixed extension*. We also have to make sure, that has a property called *irreducible*. It means that has at least degree 1 and there is no pair of polynomials with lesser degree (and coefficients in the extension) such that their product is equal to . 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 . 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.

Pingback: Getting started with exact arithmetic and F# | Schneide Blog