How are real numbers specified in computation?

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.

Solved by user95 (50,175 )
Oct 09, 2010 at 17:49