4 ms·

A follow up to this classic article could be titled "What every language designer should know about humans." :) Floats are among the least user-friendly ways to

A follow up to this classic article could be titled "What every language designer should know about humans." :) Floats are among the least user-friendly ways to do decimal arithmetic. They aren't even that fast anymore given the resurgence of fixed point arithmetic in hpc. Imo, in 2020 we should have had mainstream languages in which (2^(1/2))^2 == 2. It's not rocket science. :) Float truncation is a little like an OS silently converting a user's flac collection to mp3 because it was running low on disk space.

rectang 6y ago
What primitive numerical type should languages have instead? Can you show us some sample code illustrating how this type would be used for tasks where floats are typically deployed today?
- bjourne 6y ago
  The natural type for numbers is expression trees. That's roughly what dl frameworks like TensorFlow and PyTorch does and allows for things like automatic differentiation and distributed computation. For any expression, the runtime is allowed to reduce it only if it can prove that the reduction is value preserving. For example 3/1 => 3, (1/3)*3 => 1, (e^(ln(x)/2))^2 => x and 10/14 => 5/7. But 5/7 cannot be reduced further. The primitive numerical type that should be used instead of floating point is the rational. Rationals have their own problems (no numeric type is perfect) but their problems are much easier to manage than float's.
  - rectang 6y ago
    Thanks! Let me follow up by exploring a specific use case: scoring in a Lucene-style search engine, where arbitrarily complex queries repeatedly scale a floating point "score" value which measures document relevancy against a query. Sometimes documents which ought to produce equal scores against a given query (if scoring were evaluated using real number math) do not produce equal scores in practice because of floating point limitations such as not supporting associativity or commutativity. Let's assume we are willing to sacrifice performance for correctness to address this issue. 1) If scores were tracked as expression trees, could this problem be eliminated entirely? If so, I'd hazard a guess that while you'd eventually run into edge case issues such as needing arbitrarily large integers, in practice the CPU cost to track scores as expression trees rather than floats would be increased by a roughly constant factor. 2) If scores were tracked using a rational instead of a float, could the problem of tied scores be eliminated? I suspect that the answer to that is no, because you will quckly run up against integer precision limitations in the numerator/denominator of the rational type.
    - bjourne 6y ago
      1) Hard for me to say since I don't know the formula of the scoring system you're talking about. But in general, if the problem goes away when doing the calculation on paper it would also go away when using symbolic math since the methods are identical. An expression is a tree. A tree can grow arbitrarily large and therefore an expression can grow arbitrarily large. It's a problem in theory but not in practice. You can try for yourself in SymPy. It is very hard to come up with an expressions so complicated that they become difficult for the system to handle. 2) No. Assuming you are using tf-idf for scoring, your calculation involves numbers with infinite decimal expansions that cannot be expressed as rationals. However, you get arbitrarily precise by using very large integers in the numerator and denominator. That is in contrast with floats whose precision is fixed at either 32 or 64 bit.
  - augustt 6y ago
    Many "serious" numerical computations using rationals will quickly have the numerator and/or denominator explode to the point where BigInts are needed, at which point you could just be using a BigFloat.
  - jcranmer 6y ago
    > The primitive numerical type that should be used instead of floating point is the rational. Rationals have their own problems (no numeric type is perfect) but their problems are much easier to manage than float's. Rationals are not algebraic types; you don't support exponentials, radicals, or logarithms. A lot of numerical algorithms require algebraic operations on real numbers to compute their results--for example, computing eigenvalues, or numerical approaches to root finding. If you're going to argue for using symbolic notation, well, closed-form solutions cannot exist for several of the kinds of problems we want to solve. Another issue is that rationals are fundamentally more expensive to compute than floating point; normalization of rationals requires computing a gcd (not really parallelizable on a bit level, and so can't be done in 1 cycle), while a floating point requires count-leading-0 (which is). As a case in point, the easiest way to find a solution to a rational linear programming problem is to... solve it in floating-point to find a basis, and then adjust that basis using rational arithmetic (usually finding that the floating-point basis was indeed optimal!). Trying to start with rational arithmetic makes it slower by a factor of ~10000×.
    - bjourne 6y ago
      What do you mean by algebraic types? If you mean algebraic number then yes, it is true that rationals cannot express all algebraic numbers such as the square root of prime numbers. But neither can floats! In fact, floats are limited to either 2^32 or 2^64 numbers (give or take a few) but rationals can express as many numbers as you have bits of memory in your system. I.e the number of numbers rationals can express is in practice infinite. Neither does floats support transcendental functions. Those functions are implemented using Taylor series approximation and the same technique could be used for implementing rational transcendental functions. To boot, you'd get much higher precision. Yes, rationals with arbitrary precision are more expensive to compute with than precision-limited floats. But who cares? It is not the 80s anymore.
      - jcranmer 6y ago
        > Yes, rationals with arbitrary precision are more expensive to compute with than precision-limited floats. But who cares? It is not the 80s anymore. The people who care are the people who now either have to buy 10000× the computing power or solve only 1/10000× the largest problem size to solve their needs, usually without meaningfully improving their results. Put another way, using rationals would turn your 2020-era computer into a 1980-era computer in terms of performance on your linear algebra benchmarks.
ChrisLomont 6y ago
> Imo, in 2020 we should have had mainstream languages in which (2^(1/2))^2 == 2 Such things are either incredibly inefficient or mathematically unsound. And there's plenty of provable impossible computational things involved. Start at the tablemaker's dilemma, then learn the difficulty of deciding if some basic expression is actually zero, and so on. There's a massive literature on doing such computations, and many, many impossibility theorems. There is no getting around some seemingly simple problems require arbitrarily large computational resources to resolve - floating point picks the very useful path of doing approximations in predictable time over attempting exact answers in unbounded time and space.
- bjourne 6y ago
  "Such things" are the foundation of symbolic math libraries, deep learning libraries, most optimizing compilers and Wolfram Alpha. I.e it is not true that they would be incredibly inefficient or mathematically unsound. I don't understand your point about the Tablemaker's dilemma because it is a dilemma only if precision is fixed. With the correct numeric type (rationals) precision is not fixed.
  - ChrisLomont 6y ago
    Let's unpack: > With the correct numeric type (rationals) precision is not fixed. Almost no problems can be represented exactly by rationals. Even the sqrt(2) you started with is not rational. And rationals are unusable for almost any type of work, because they grow exponentially (in time and space) for most problems. For example, if you tried to compute a simple mandelbrot set with rationals, you'd need more bytes than there are subatomic particles in the universe (~10^80). Proof: Mandelbrot takes a complex number c = x + i y, which you want to represent as a rational, and iterates z <- z^2 + c. Squaring doubles the number of digits for each of the numerator and denominator, so each iteration requires ~2 times the storage of the previous iteration. Thus you'll need over 2^300 bytes for 300 iterations, which is > 10^90. A common mandelbrot uses over 1000 iterations. So you see rationals are computationally unusable for even simple tasks. > symbolic math libraries These can be arbitrarily slow and use arbitrarily large memory for simple problems - which I stated above when I said "Such things are either incredibly inefficient or mathematically unsound." For example simple converging infinite sums that don't have closed forms known to your tools would never evaluate - the only solution is some fixed, finite representation if you want to use the value in later computations. The same thing for integrals, root finding, pdes, and thousands of other problems. > deep learning libraries Deep learning libraries have led to a reduction in precision specifically for the reasons I mentioned: lower memory requirements and higher speed. Hardware vendors from Intel to NVidia to AMD to ARM have introduced lower precision math, including the new bfloat16 (and some have a bfloat8) for these reasons. I think this is the opposite of what you claimed, but supports my claim. Care to show me where deep learning libraries do perfect symbolic computation in the process of deep learning? I'm aware people try to train them to do symbolic computation, but the libraries themselves aren't using the types of reductions you posted. > most optimizing compilers Most compilers would reduce sqrt(2) * sqrt(2) to 2? List them. (Heck - list one!) It's simply not true (as can be checked trivially for all common C++ compilers on godbolt). I've seen none, despite following optimizing compiler theory and practice for decades. >Wolfram Alpha Redundant with the symbolic stuff above - and I've used Mathematica since v1.0 in 1987 quite extensively. It most certainly is slower doing anything symbolically that can be done numerically, and there are lots of problems it cannot do symbolically without puking, but those same problems run instantly when approximated with floating point. There's ample pages listing things symbolic engines get wrong or cannot do, but that can be done elsewhere. >I don't understand your point about the Tablemaker's dilemma because it is a dilemma only if precision is fixed ???? The dilemma is not about fixed precision. The problem is correctly rounding a function as if it had an infinite expansion first. For some functions this means arbitrarily large computations. Ahead of time mankind does not know how many digits are needed for many common uses. So the problem is not about fixed precision - it's about possibly unbounded computation, which is vastly different. For example, no one has a bound on the number of digits needed to compute correctly rounded a^b for any two floating point values a and b. And there exist computable numbers for which the rounded value can never be computed with any amount of digits [3]. So it's not about fixed precision. It's far more subtle. If you're willing to run unbounded in time and space computations, then you can more and more precise answers, but at every point you still don't know if you've escaped the Tablemaker's dilemma. This is the point. Here's a guy I've followed for decades, one of many researchers on the topic [1]. Note that his "hard to round cases" in 2013 took 1576 years of computer time to determine how many digits are needed for double precision values for some elementary functions, precisely because this is not the trivial problem you think it is. Here's a 2016 paper doing some work on GPUs [2]: " For example, the Nesterenko and Waldschmidt [1996] bound for the exponential in double precision states that 7,290,678 bits of intermediate precision suffice to provide a correctly rounded result." To get 64 bits of accuracy, correctly rounded, you need 1 megabyte and an incredible amount of computation. My point exactly. And these bounds tend to increase exponentially, not linearly, soon pushing such issues beyond currently computable (which is also why there are still research papers being published on getting results for 64 bit doubles in various ways and for various elementary functions). Again you have the choice I presented: you either accept unbounded in time and space behavior, or you fix time and space to make things usable with approximations. Floating-point is an incredibly good solution to making numerics as good as possible under fixed space and time requirements. [1] https://www.vinc17.net/research/index.en.html https://www.vinc17.net/research/index.en.html [2] https://dl.acm.org/doi/pdf/10.1145/2935746 https://dl.acm.org/doi/pdf/10.1145/2935746 [3] https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma
rwallace 6y ago
> resurgence of fixed point arithmetic in hpc Where is fixed point arithmetic resurging in HPC? Serious question; I haven't heard about this, but if it's happening in places I haven't heard about, I would be interested in looking at them.
- bjourne 6y ago
  Google is using fixed point arithmetic in their TPU clusters. See https://link.springer.com/chapter/10.1007/978-3-319-67952-5_4 https://link.springer.com/chapter/10.1007/978-3-319-67952-5_...

rectang 6y ago

What primitive numerical type should languages have instead? Can you show us some sample code illustrating how this type would be used for tasks where floats are typically deployed today?

bjourne 6y ago
The natural type for numbers is expression trees. That's roughly what dl frameworks like TensorFlow and PyTorch does and allows for things like automatic differentiation and distributed computation. For any expression, the runtime is allowed to reduce it only if it can prove that the reduction is value preserving. For example 3/1 => 3, (1/3)*3 => 1, (e^(ln(x)/2))^2 => x and 10/14 => 5/7. But 5/7 cannot be reduced further. The primitive numerical type that should be used instead of floating point is the rational. Rationals have their own problems (no numeric type is perfect) but their problems are much easier to manage than float's.
- rectang 6y ago
  Thanks! Let me follow up by exploring a specific use case: scoring in a Lucene-style search engine, where arbitrarily complex queries repeatedly scale a floating point "score" value which measures document relevancy against a query. Sometimes documents which ought to produce equal scores against a given query (if scoring were evaluated using real number math) do not produce equal scores in practice because of floating point limitations such as not supporting associativity or commutativity. Let's assume we are willing to sacrifice performance for correctness to address this issue. 1) If scores were tracked as expression trees, could this problem be eliminated entirely? If so, I'd hazard a guess that while you'd eventually run into edge case issues such as needing arbitrarily large integers, in practice the CPU cost to track scores as expression trees rather than floats would be increased by a roughly constant factor. 2) If scores were tracked using a rational instead of a float, could the problem of tied scores be eliminated? I suspect that the answer to that is no, because you will quckly run up against integer precision limitations in the numerator/denominator of the rational type.
  - bjourne 6y ago
    1) Hard for me to say since I don't know the formula of the scoring system you're talking about. But in general, if the problem goes away when doing the calculation on paper it would also go away when using symbolic math since the methods are identical. An expression is a tree. A tree can grow arbitrarily large and therefore an expression can grow arbitrarily large. It's a problem in theory but not in practice. You can try for yourself in SymPy. It is very hard to come up with an expressions so complicated that they become difficult for the system to handle. 2) No. Assuming you are using tf-idf for scoring, your calculation involves numbers with infinite decimal expansions that cannot be expressed as rationals. However, you get arbitrarily precise by using very large integers in the numerator and denominator. That is in contrast with floats whose precision is fixed at either 32 or 64 bit.
- augustt 6y ago
  Many "serious" numerical computations using rationals will quickly have the numerator and/or denominator explode to the point where BigInts are needed, at which point you could just be using a BigFloat.
- jcranmer 6y ago
  > The primitive numerical type that should be used instead of floating point is the rational. Rationals have their own problems (no numeric type is perfect) but their problems are much easier to manage than float's. Rationals are not algebraic types; you don't support exponentials, radicals, or logarithms. A lot of numerical algorithms require algebraic operations on real numbers to compute their results--for example, computing eigenvalues, or numerical approaches to root finding. If you're going to argue for using symbolic notation, well, closed-form solutions cannot exist for several of the kinds of problems we want to solve. Another issue is that rationals are fundamentally more expensive to compute than floating point; normalization of rationals requires computing a gcd (not really parallelizable on a bit level, and so can't be done in 1 cycle), while a floating point requires count-leading-0 (which is). As a case in point, the easiest way to find a solution to a rational linear programming problem is to... solve it in floating-point to find a basis, and then adjust that basis using rational arithmetic (usually finding that the floating-point basis was indeed optimal!). Trying to start with rational arithmetic makes it slower by a factor of ~10000×.
  - bjourne 6y ago
    What do you mean by algebraic types? If you mean algebraic number then yes, it is true that rationals cannot express all algebraic numbers such as the square root of prime numbers. But neither can floats! In fact, floats are limited to either 2^32 or 2^64 numbers (give or take a few) but rationals can express as many numbers as you have bits of memory in your system. I.e the number of numbers rationals can express is in practice infinite. Neither does floats support transcendental functions. Those functions are implemented using Taylor series approximation and the same technique could be used for implementing rational transcendental functions. To boot, you'd get much higher precision. Yes, rationals with arbitrary precision are more expensive to compute with than precision-limited floats. But who cares? It is not the 80s anymore.
    - jcranmer 6y ago
      > Yes, rationals with arbitrary precision are more expensive to compute with than precision-limited floats. But who cares? It is not the 80s anymore. The people who care are the people who now either have to buy 10000× the computing power or solve only 1/10000× the largest problem size to solve their needs, usually without meaningfully improving their results. Put another way, using rationals would turn your 2020-era computer into a 1980-era computer in terms of performance on your linear algebra benchmarks.

ChrisLomont 6y ago

> Imo, in 2020 we should have had mainstream languages in which (2^(1/2))^2 == 2 Such things are either incredibly inefficient or mathematically unsound. And there's plenty of provable impossible computational things involved. Start at the tablemaker's dilemma, then learn the difficulty of deciding if some basic expression is actually zero, and so on. There's a massive literature on doing such computations, and many, many impossibility theorems. There is no getting around some seemingly simple problems require arbitrarily large computational resources to resolve - floating point picks the very useful path of doing approximations in predictable time over attempting exact answers in unbounded time and space.

bjourne 6y ago
"Such things" are the foundation of symbolic math libraries, deep learning libraries, most optimizing compilers and Wolfram Alpha. I.e it is not true that they would be incredibly inefficient or mathematically unsound. I don't understand your point about the Tablemaker's dilemma because it is a dilemma only if precision is fixed. With the correct numeric type (rationals) precision is not fixed.
- ChrisLomont 6y ago
  Let's unpack: > With the correct numeric type (rationals) precision is not fixed. Almost no problems can be represented exactly by rationals. Even the sqrt(2) you started with is not rational. And rationals are unusable for almost any type of work, because they grow exponentially (in time and space) for most problems. For example, if you tried to compute a simple mandelbrot set with rationals, you'd need more bytes than there are subatomic particles in the universe (~10^80). Proof: Mandelbrot takes a complex number c = x + i y, which you want to represent as a rational, and iterates z <- z^2 + c. Squaring doubles the number of digits for each of the numerator and denominator, so each iteration requires ~2 times the storage of the previous iteration. Thus you'll need over 2^300 bytes for 300 iterations, which is > 10^90. A common mandelbrot uses over 1000 iterations. So you see rationals are computationally unusable for even simple tasks. > symbolic math libraries These can be arbitrarily slow and use arbitrarily large memory for simple problems - which I stated above when I said "Such things are either incredibly inefficient or mathematically unsound." For example simple converging infinite sums that don't have closed forms known to your tools would never evaluate - the only solution is some fixed, finite representation if you want to use the value in later computations. The same thing for integrals, root finding, pdes, and thousands of other problems. > deep learning libraries Deep learning libraries have led to a reduction in precision specifically for the reasons I mentioned: lower memory requirements and higher speed. Hardware vendors from Intel to NVidia to AMD to ARM have introduced lower precision math, including the new bfloat16 (and some have a bfloat8) for these reasons. I think this is the opposite of what you claimed, but supports my claim. Care to show me where deep learning libraries do perfect symbolic computation in the process of deep learning? I'm aware people try to train them to do symbolic computation, but the libraries themselves aren't using the types of reductions you posted. > most optimizing compilers Most compilers would reduce sqrt(2) * sqrt(2) to 2? List them. (Heck - list one!) It's simply not true (as can be checked trivially for all common C++ compilers on godbolt). I've seen none, despite following optimizing compiler theory and practice for decades. >Wolfram Alpha Redundant with the symbolic stuff above - and I've used Mathematica since v1.0 in 1987 quite extensively. It most certainly is slower doing anything symbolically that can be done numerically, and there are lots of problems it cannot do symbolically without puking, but those same problems run instantly when approximated with floating point. There's ample pages listing things symbolic engines get wrong or cannot do, but that can be done elsewhere. >I don't understand your point about the Tablemaker's dilemma because it is a dilemma only if precision is fixed ???? The dilemma is not about fixed precision. The problem is correctly rounding a function as if it had an infinite expansion first. For some functions this means arbitrarily large computations. Ahead of time mankind does not know how many digits are needed for many common uses. So the problem is not about fixed precision - it's about possibly unbounded computation, which is vastly different. For example, no one has a bound on the number of digits needed to compute correctly rounded a^b for any two floating point values a and b. And there exist computable numbers for which the rounded value can never be computed with any amount of digits [3]. So it's not about fixed precision. It's far more subtle. If you're willing to run unbounded in time and space computations, then you can more and more precise answers, but at every point you still don't know if you've escaped the Tablemaker's dilemma. This is the point. Here's a guy I've followed for decades, one of many researchers on the topic [1]. Note that his "hard to round cases" in 2013 took 1576 years of computer time to determine how many digits are needed for double precision values for some elementary functions, precisely because this is not the trivial problem you think it is. Here's a 2016 paper doing some work on GPUs [2]: " For example, the Nesterenko and Waldschmidt [1996] bound for the exponential in double precision states that 7,290,678 bits of intermediate precision suffice to provide a correctly rounded result." To get 64 bits of accuracy, correctly rounded, you need 1 megabyte and an incredible amount of computation. My point exactly. And these bounds tend to increase exponentially, not linearly, soon pushing such issues beyond currently computable (which is also why there are still research papers being published on getting results for 64 bit doubles in various ways and for various elementary functions). Again you have the choice I presented: you either accept unbounded in time and space behavior, or you fix time and space to make things usable with approximations. Floating-point is an incredibly good solution to making numerics as good as possible under fixed space and time requirements. [1] https://www.vinc17.net/research/index.en.html https://www.vinc17.net/research/index.en.html [2] https://dl.acm.org/doi/pdf/10.1145/2935746 https://dl.acm.org/doi/pdf/10.1145/2935746 [3] https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma https://en.wikipedia.org/wiki/Rounding#Table-maker's_dilemma

rwallace 6y ago

> resurgence of fixed point arithmetic in hpc Where is fixed point arithmetic resurging in HPC? Serious question; I haven't heard about this, but if it's happening in places I haven't heard about, I would be interested in looking at them.

bjourne 6y ago
Google is using fixed point arithmetic in their TPU clusters. See https://link.springer.com/chapter/10.1007/978-3-319-67952-5_4 https://link.springer.com/chapter/10.1007/978-3-319-67952-5_...