Can coordinates of constructable points be represented exactly?

Question

I'd like to write a program that lets users draw points, lines, and circles as though with a straightedge and compass. Then I want to be able to answer the question, "are these three points collinear?" To answer correctly, I need to avoid rounding error when calculating the points.

Is this possible? How can I represent the points in memory?

(I looked into some unusual numeric libraries, but I didn't find anything that claimed to offer both exact arithmetic and exact comparisons that are guaranteed to terminate.)

Answer 1

Yes.

I highly recommend Introduction to constructions, which is a good basic guide.

Basically you need to be able to compute with constructible numbers - numbers that are either rational, or of the form a + b sqrt(c) where a,b,c were previously created (see page 6 on that PDF). This could be done with algebraic data type (e.g. data C = Rational Integer Integer | Root C C C in Haskell, where Root a b c = a + b sqrt(c)). However, I don't know how to perform tests with that representation.

Two possible approaches are:

• Constructible numbers are a subset of algebraic numbers, so you can use algebraic numbers. All algebraic numbers can be represented using polynomials of whose they are roots. The operations are computable, so if you represent a number a with polynomial p and b with polynomial q (p(a) = q(b) = 0), then it is possible to find a polynomial r such that r(a+b) = 0. This is done in some CASes like Mathematica, example. See also: Computional algebraic number theory - chapter 4

• Use Tarski's test and represent numbers. It is slow (doubly exponential or so), but works :) Example: to represent sqrt(2), use the formula x^2 - 2 && x > 0. You can write equations for lines there, check if points are colinear etc. See A suite of logic programs, including Tarski's test

If you turn to computable numbers, then equality, colinearity etc. get undecidable.

Answer 2

I think the only way this would be possible is if you used a symbolic representation, as opposed to trying to represent coordinate values directly -- so you would have to avoid trying to coerce values like sqrt(2) into some numerical format. You will be dealing with irrational numbers that are not finitely representable in binary, decimal, or any other positional notation.