Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I see very few non-floating point computing libraries/packages around. Given the various inaccuracies of floating point representation, the question arises why there aren't at least some fields where this increased accuracy might be worth the intricacies of working with fixed-point.
Are there any MAJOR difficulties in using, say, a fixed point eigenvalue solver? How slow/fast, inaccurate/accurate would they be?
The use of fixed point arithmetic can be appropriate under certain circumstances. Generally for scientific computing (at least in the sense that most people think of it) it is not appropriate due to the need for expressing the large dynamic ranges encountered. You mention eigenvalue problems as an example, but very often in science, one is interested in the smallest eigenvalues of a matrix (say, in computing the ground state of a quantum system). The accuracy of small eigenvalues will generally be quite deteriorated relative to large eigenvalues if you use fixed point. If your matrix contains entries which vary by large ratios, the small eigenvalues might be completely unexpressable in the working precision. This is a problem with the representation of numbers; these arguments hold regardless of how you do the intermediate computations. You could possibly work out a scaling to apply to the computed results, but now you've just invented floating point. It is easy to construct matrices whose elements are well behaved, but whose eigenvalues are exceedingly poorly behaved (like Wilkinson matrices, or even matrices with entirely integer entries). These examples are not as pathological as they might seem, and many problems at the cutting edge of science involve very poorly behaved matrices, so using fixed point in this context is a Bad Idea(TM).
You might argue that you know the magnitude of the results and you want to not waste bits on the exponent, so let's talk about the intermediates. Using fixed point will generally exacerbate the effects of catastrophic cancellations and roundoff unless you really go through great pains to work in higher precision. The performance penalty would be huge, and I would conjecture that using a floating point representation with the same mantissa bit width would be faster and more accurate.
One area where fixed point can shine is in certain areas of geometric computing. Especially if you need exact arithmetic or know the dynamic range of all the numbers beforehand, fixed point lets you take advantage of all of the bits in your representation. For example, suppose you wanted to compute the intersection of two lines, and somehow the endpoints of the two lines are normalized to sit in the unit square. In this case, the intersection point can be represented with more bits of precision than using an equivalent floating point number (which will waste bits on the exponent). Now, it is almost certainly the case that the intermediate numbers required in this calculation need to be computed to higher precision, or at least done very carefully (like when dividing the product of two numbers by another number, you need to be very careful about it). In this respect, fixed point is advantageous more from the representation standpoint rather than from a computational standpoint, and I would go so far as to say this is generally true when you can establish definite upper and lower bounds on the dynamic range of your algorithm outputs. This happens rarely.
I used to think that floating point representations were crude or inaccurate (why waste bits on an exponent?!). But over time I've come to realize that it really is one of the best possible representations for real numbers. Things in nature show up on log scales, so real data ends up spanning a large range of exponents. Also to achieve the highest possible relative accuracy requires working on log scales, making the tracking of an exponent more natural. The only other contender for a "natural" representation is symmetric level index. However, addition and subtraction are much slower in that representation, and it lacks the hardware support of IEEE 754. A tremendous amount of thought was put into the floating point standards, by a pillar of numerical linear algebra. I would think he knows what the "right" representation of numbers is.
As an example of why exact arithmetic/fixed point arithmetic is so rarely used, consider this:
In the finite element method, as in almost every other method in use in scientific computing, we arrive at linear or nonlinear systems that are only approximations to the real world. For example, in the FEM, the linear system to solve is only an approximation to the original partial differential equation (which may, itself, only be an approximation of the real world). So why put enormous effort into solving something that is only an approximation?
Most of the algorithms we use today are iterative in nature: Newton's method, Conjugate Gradients, etc. We terminate these iterations whenever we are satisfied that the accuracy of the iterative approximate to the solution of the problem is sufficient. In other words, we terminate before we have the exact solution. As before, why use exact arithmetic for an iterative scheme when we know that we're only computing approximations?
float any time soon.
$\endgroup$
If you look at this library for correct rounding: CRlibm, you will see in the documentation that generally, algorithms must be proven accurate (with reasoned proofs). Why? The stability and speed of convergence of a result of a function does not have a "one-size-fits-all" answer. In short, there is "no free lunch" -- you have to work to prove your reasoning is correct. This is due to the behavior of the functions being modeled, not the underlying hardware (whether you use integer or floating point units, though yes, both have "gotchas", like overflow/underflow, denormal numbers, etc.) Even if the result you are looking for converges to an integer, the algorithm used to find the result is not necessarily very stable.
Eigen is a C++ library that has a variety of algorithms for solving matrices, each with different properties. This page contains a table which discusses speed vs. accuracy trade-offs for the various algorithms used for solving a matrix. I suspect the Eigen library can do what you want. :-)
For some nice examples of where high-precision arithmetic has been useful in mathematics, take a look at the book Mathematics by Experiment by Jonathan Borwein and David Bailey. There's also this sequel, which I haven't read.
