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?


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.

Comments (5)

  • +0 – I had liked the part of Kaveh's answer where he suggested that there are alternate models of computation, as this seemed to be in line with what I had read in the paper I was looking at. That said, I didn't really know the answer...I've un-accepted Kaveh's answer for now. I had actually suspected that algebraic numbers might have something to do with it. Anyway, thank you for taking the time to weigh in on my question...I will think and read further before I accept an answer. — Oct 09, 2010 at 18:08  
  • +0 – I haven't said that it is a good model for CG, my point was that even when authors say the inputs are real numbers, they are not really real numbers. I agree with you that I shouldn't have included CG among the others. I have read a very small number of CG papers, is BSS model that well-established in theoretical CG papers? — Oct 09, 2010 at 18:43  
  • +1 – Pardon my ignorance, but what does BSS stand for? — Oct 09, 2010 at 18:48  
  • +1 – The BSS model is a theoretical model that assumes that arbitrary real numbers are available. What's done in CG involves actual implementations of a model that is generally restricted to algebraic numbers. Also the CG implementations are far from unit cost per operation. So they're not the same thing. See e.g. the LEDA real number model,… — Oct 09, 2010 at 21:02  
  • +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