Be Rational About Numerical Analysis

Bold assertions follow, leading to a question...

Numerical computation for scientific purposes is generally done with floating-point numbers, for instance IeeeSevenFiftyFour numbers. That standard includes some useful, but odd, items, such as -0, -Infinity, and "NotaNumber". Sometimes, loose use of language leads to these numbers being called "reals", in distinction from "integers". But they are nothing like the real numbers!

In fact, all the numbers that can be represented with IEEE 754 are rational. Which is what you'd expect if they are values used in scientific or engineering calculations, ultimately derived from measurement (see PiIsNotIrrational), but we carry on pretending that these floating-point numbers are approximations to real numbers. Why?

Now these floating point numbers have some problems. For one thing, it's more work than you'd think to decide if any two examples of them should be considered equal or not. This leads to one set of techniques in NumericalAnalysis. Also, unlike the real numbers, floating point numbers aren't dense, which leads to another bunch of techniques in numerical analysis.

But all the numbers we deal with in practical problems are rational. So why not use rational numbers to do the calculations? Historically, this has been too expensive: one advantage of floating point numbers is that we can build hardware to manipulate them such that we pay the cost of having to handle their deficiencies in return for having a good idea of how long operations will take, and having them happen fast.

Now I have a picture in my mind of a talk that RichardGabriel gave, where he's mentioning the damage done to computing in general by the driver behind most computing research these days being the question of making physicists' lives easy. Another point he made was that you wouldn't try to build a word processor using a constraint system, because it would be way too slow. Except maybe you would when "one of these [waves new Apple laptop in the air] is worth two Cray-2s".

Processing power is now so cheap, why shouldn't we think of doing all our numerical computation with exact rationals, such as the ones in the SchemeLanguage numeric stack? Then the inaccuracies of our measurements could be handled separately from the inaccuracies inherent in the floating point representation of them. Might that not make our computational lives easier, even if we had to give up (perhaps only temporarily) on well-defined time and space bounds? Maybe some people already are.

Some people do use Lisp and such for scientific programming, but I get the impression that they're using BigNums, rather than explicit ratios like the rational type in the R^5RS. Anyone know?

Rationals are part of the Common Lisp numerical tower. Unlike scheme, the full numeric tower is required.

We carry on pretending that floating-point numbers are approximations to reals for the simple reason that that is what they are. Using all rational numbers instead of only a limited group does not obviate the need for rounding, since the square root of 2 is still not rational. Given that we have to round anyway, it is useless to continue with "arbitrary-precision" arithmetic, since we do not have arbitrary precision anyway. Because of the way rational numbers work, we cannot in general expect the size of numerator and denominator to remain bounded. Rather, they grow without bound. Computations that require a bounded amount of storage for a finite (but well-defined) precision will require an unbounded amount of storage, for no increase in precision at all. This is not a "constants factor" deal; it is a fundamental change in the complexity of the algorithm.

The fact that the rationals are dense in R unfortunately only weakens their case. Any representable set X that is dense in a compact interval must have the properties that the subset of X in which all representations require more than n bytes, is also dense. If we start in a subset of X in which we can represent the elements with less than n bytes, we cannot expect to remain there after computations. Rather, the blow-up described earlier for rationals will in general happen for any such X that is dense in R.

Floating-point numbers are more-or-less equally spaced with respect to their logarithm, which is a desirable property from physical considerations.

What does that last sentence mean?

I think it means that there are roughly as many floating points numbers available near to 1.0E0 as there are near 1.0E2, 1.0E-2, 1.0E100, 1.0E-100 and so on.

YouArentGonnaNeedIt

There are some serious misconceptions about numerical analysis presented here. While many (incompetent) programmers dealing with numerical tasks may treat floating point numbers as 'reals' and forget about the details, this is not how numerical analysis is done in general.

The point made above about arbitrary precision is a good one. Some other relevant points, in no particular order:

Processing power is not as cheap as you think - there are many numerical simulation problems for which any foreseeable increase in computational power will be more than welcome. Processing power is not cheap in these contexts, and doesn't nearly begin to be enough (fluid dynamics, climate models, etc.)

"Real world" problems rarely involve exact calculations anyway. If you are dealing with measured data, you have error. Sometimes, the easiest way to deal with this properly is to provide error bounds which are delineated by real-valued functions (which of course are themselves approximated).

This is a reiteration, but an important one: The "bold assertions" above seem to me to imply that people use floating point as approximate reals, and leave it at that. If *you* do this, you are demonstrating that you do not understand floating point, numerical analysis, or both. The fact that some people don't understand the tools they are using is not a valid criticism of the tools.

The PiIsNotIrrational page is broken. There may be a good idea hidden in there somewhere, but it isn't coming through clearly, and too many fundamentally different things are being mixed up on that page to make it easy to find.

"All the numbers we deal with in practice are rational" is misleading. It is more important that many/most of the numbers we deal with in practice are *approximate*.

To clarify, "all numbers we deal with are exact" is important when dealing with numbers. Contrast with "all values we deal with are approximate". If the "number" is really derived from some measured value, then of course the precision is limited by the accuracy of the measurement. Floating point to an appropriate level of precision does a super job of handling these kinds of values.

Ok, that last sentence was a bit ambiguous, but your clarification doesn't fix the problem. The fact that you can represent an inaccurate value with a precise number does not magically make that number accurate. The point was that in dealing with real world data it often of primary importance to provide decent error bounds. The particular representation for an inaccurate value is not that important.

On the other hand, if you want to do actual numerical analysis, then floating point is not a good choice. The idea that people can equivocate between "numbers" and "values" is valid and it is important to know the difference.

Have you studied any numerical analysis? What do you think *is* a good choice? Are you honestly proposing calculating values that range over many (say 10) orders of magnitude with one system of rational approximations? Do you suggest a fixednum approach that just doesn't happen to fit in CPU registers, or some sort of dynamically growing data type? Have you calculated the costs involved in these?

You have a rather strong assertion here that 'floating point is not a good choice for numerical analysis.'. Clearly a large number of numerical analysts disagree with you, but leaving that for now, can you demonstrate firstly *why* floating point is a bad choice, given that it is used by someone competent to do so, and secondly describe any system of your choice that is *demonstrably* superior for the tasks in numerical analysis. I see a lot of assertions on these pages, but little evidence to back them up...

LazyEvaluation would seem to be superior to floating point for numerical analysis involving commonly used, difficult to represent expressions. Using symbols like pi, e, ln(2) etc for example beats using 3.1416E0, 2.718E0 and 6.9315E-1 regardless of how much precision is specified by the floating point representation.

Now that is an entirely different kettle of fish, and belongs to symbolic computation, not numeric analysis. If you are evangalizing mixed symbolic/numeric computations, sure --- they have their place. Hardly a new idea though, and doesn't address the original contention.

The better choice for numerical analysis is various forms of IntervalArithmetic?. While this uses a fairly typical floating point representation (sign-mantissa-exponent) underneath, each approximate number is represented by two floating point values: a maximum bound and a minimum bound. This gives the properties actually desired in much numerical analysis, tracking the error range explicitly and carrying it through all computations properly. Surprisingly, there seem to be no hardware units dedicated to interval arithmetic; implementing it on top of IEEE arithmetic is actually rather a pain.

There are problems with interval arithmetic also. Do you really think that the NA community would not have embraced this if it were significantly beneficial (wrt floating point)?

[Specifically, interval arithmetic is just another tool among many, and one that is indeed heavily used -- but not a panacea. Further, it has been implemented in hardware, just not in the CPUs that are shipped in units of millions/billions. There's been insufficient demand, else e.g. Intel would tack it onto the side somehow. And part of the reason for the insufficient demand is that it's not a panacea.]

CategoryMath