Theoretical Computer Science

# How are real numbers specified in computation?

This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real numbers are specified as input. E.g., when it's stated that LDT has certain polynomial lower bounds, how are the real numbers specified when they are treated as input?

## Solution

I disagree with your accepted answer by Kaveh. For linear programming and Nash equilibria, floating point may be acceptable. But floating point numbers and computational geometry mix very badly: the roundoff error invalidates the combinatorial assumptions of the algorithms, frequently causing them to crash. More specifically, a lot of computational geometry algorithms depend on primitive tests that check whether a given value is positive, negative, or zero. If that value is very close to zero and floating point roundoff causes it to have the wrong sign, bad things can happen.

Instead, inputs are often assumed to have integer coordinates, and intermediate results are often represented exactly, either as rational numbers with sufficiently high precision to avoid overflow or as algebraic numbers. Floating point approximations to these numbers may be used to speed up the computations, but only in situations where the numbers can be guaranteed to be far enough away from zero that the sign tests will give the right answers.

In most theoretical algorithms papers in computational geometry, this issue is sidestepped by assuming that the inputs are exact real numbers and that the primitives are exact tests of the signs of roots of low-degree polynomials in the input values. But if you are implementing geometric algorithms then this all becomes very important.

• +0 – @Kaveh: No. Geometric algorithms are designed to be correct, in the real RAM model, for arbitrary real input, not just for rational input. In particular, there are geometric algorithms that cannot be implemented exactly, because they use primitives that are trivial on the real RAM but for which no efficient algorithm is known for the (realistic) integer RAM. The best example is the sum of square roots problem: Given two sets $S$ and $T$ of positive integers, is $\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$? — Oct 10, 2010 at 07:28