Handbook of Floating-Point Arithmetic
Floating-point arithmetic is the most widely used way of implementing real-number arithmetic on modern computers. However, making such an arithmetic reliable and portable, yet fast, is a very difficult task. As a result, floating-point arithmetic is far from being exploited to its full potential. This handbook aims to provide a complete overview of modern floating-point arithmetic. So that the techniques presented can be put directly into practice in actual coding or design, they are illustrated, whenever possible, by a corresponding program. The handbook is designed for programmers of numerical applications, compiler designers, programmers of floating-point algorithms, designers of arithmetic operators, and more generally, students and researchers in numerical analysis who wish to better understand a tool used in their daily work and research.
Stats for nerds
7recommend
11mentions
10people
2015–2026years
73% recommend27% neutral
Mentions per year
What Hacker News says
- EDIT: I see that libbf implements faithful rounding of operations. Nice. TIL.
See also: Jean-Michel Muller's books: "Handbook of Floating Point Arithmetic," and "Elementary Functions."
- I have done my PhD on measuring floating-point error in large numerical simulations. In my experience, most of the time, if 64-bit floating points are not enough, then trying to increase precision further is unlikely to help much (there are exceptions).
In general, using a well-placed compensated (or exact) sum/dot product algorithm will solve most of your problems at a low cost. Nowadays, most people are familiar with Kahan summation (and related tricks like sorting numbers), but they do not know that it does not help much (often less than 128-bit floating points) and that the state of the art for those algorithms has moved quite a bit since. Nowadays, you can ensure that your sum/BLAS operation produces a result within one ulp of the exact result!
I highly recommend perusing the Handbook of Floating-Point Arithmetic (the Accurate Algorithm online page also seems fine [0]) to get an idea of what can be done. Implementations of these ideas can be found in most languages used for numerical computation (a quick Google search gave me options for C++/Python [1], Rust [2], etc.).
[0]: https://accurate-algorithms.readthedocs.io/en/latest/index.h...
- I recommend the "Handbook of Floating-point Arithmetic" if this piques interest. I think it's freely available on HAL.
- The main issue with floating point number is that it doesn't act like a ring (https://en.wikipedia.org/wiki/Ring_(mathematics)) because of rounding errors. For example the equality x*(y*z) = (x*y)*z doesn't hold because each multiplication introduce small rounding errors.
And this kind of equations are required for the exponentiation-by-squaring method (consider for example how x**5 is computed: x**5 = (((x*x)*x)*x)*x) using a naive exponentiation approach, but also x**5 = x*(x*x)*(x*x) = x*(x*x)**2 using the exponentiation-by-squaring method).
Integer operations and matrix operations are both rings, so the exponentiation-by-squaring approach works. For floating points, it doesn't give an exact result, but could still be used in practice to get an approximate result.
The pow function doesn't use this approach however, because both arguments of the pow function are floating points numbers, and can thus compute things like pow(5, 0.5) = sqrt(5), or even 534.2**12.7. The exponentiation-by-squaring approach works only when the exponent is an integer, so we need other solutions.
How exactly the pow function (or other math function like exp, log, cos, ...) are computed is a vast research subject in itself, but if you are interested, the Handbook of Floating-Point Arithmetic (https://perso.ens-lyon.fr/jean-michel.muller/Handbook.html) is both a good introduction to the domain (and the problems associated with the finite precision of floating point number), and provides a lot of techniques to work around or minimize the rounding errors that happens when manipulating floating point numbers.
- A good reference is the Handbook of Floating-Point Arithmetic. If you can be more specific about what is it that's not clear, I'll give more specific "proof". Even though you're being a bit "sealion"-y.
> It's ridiculous to post a dismissal without even watching the full video.
The video is jarring to watch. It's well-produced, engaging, etc.; but also pretentious and overconfident. It seems to be chock-full with irrelevant "developments". So it's not reasonable to expect me to watch it end-to-end.
- I don't know much about numpy.signal package, but there are other python packages that have good implementation for generating polynomial approximation. Among them are pythonsollya (a Python wrapper for Sollya), and SageMath.
Other than that, some of the overview references about Remez algorithm (should be a bit closer to your taste) that I like are:
- J.M. Muller et. al., "Handbook of Floating-Point Arithmetic", section 10.3.2 (and follow references in that section).
- N. Brisebarre and S. Chevillard, "Efficient polynomial L-approximations," 18th IEEE Symposium on Computer Arithmetic (ARITH '07), which is implemented in Sollya tool: https://www.sollya.org/sollya-2.0/help.php?name=fpminimax
Related
The art of multiprocessor programming
27 recommend · 64
The algorithm design manual
195 recommend · 321
Introduction to Algorithms
274 recommend · 880
Mathematics for Computer Science
37 recommend · 70
Introduction to the theory of computation
66 recommend · 96
A Programmer's Introduction to Mathematics
24 recommend · 44
2017–2026
