Usually, if you know enough about your algorithms to select an appropriate float alternative, you also know enough to fix your float code and that's what you should actually do.
That said, some of these aren't alternatives. Symbolic computation is a different thing entirely. Interval arithmetic can be built atop floats (e.g. IEEE-1788) and has its own zoo of unintuitive behaviors. BCD is better called a historical artifact than an alternative these days.
It's really just rationals and decimal floats in this list, which probably don't solve the issues you have if you're considering float alternatives.
I think people with certain backgrounds look at stuff like x86 BCD opcodes being removed in the move from x86-32 to amd64 and think "must be because noone uses it". Other backgrounds know that ain't so.
You can't "fix" floating point code if you are looking for deterministic answers. You just have to use other data types to handle money or complex mathematical operations like 0.2+0.1, no ifs and buts.
Floats are deterministic, but I get what you mean. Let's discuss what's meant by the result of a complex calculation. 0.1+0.2, or sqrt(2), or whatever.
1. Do you want your result to exactly encode the answer without rounding error? No fixed precision type can provide this in general, so you're stuck with symbolic approaches. If you can bound things (usually difficult), maybe you can get away with non-symbolic approaches.
2. Do you want a sensible numeric answer? This is what floats (and many other systems) give you. The definition of "sensible" is inherently tricky here and there's not a definition universally appropriate to every possible computation.
So let's return to 0.1+0.2=0.3000...1 specifically. There's two common ways to think of an encoded float. One is as the directly encoded value, as you're doing. Another way is to think of it as an interval of real numbers between the next lowest and highest intervals. Under this latter interpretation, it makes sense to discuss shortest decimal string within the interval, 0.3 in this case. There's no ambiguity because each real lives in exactly one interval. This is what algorithms like dragon box do for float to decimal string conversion.
What decimal floats give you is an encoding that tracks significant digits, where every decimal string exactly corresponds to a midpoint of an interval of reals. They do this at the cost of space, speed, and complexity. You don't get an escape from the fundamental issues of fixed precision types like rounding error, numerical sensitivity, precision loss, etc. I don't think that tradeoff makes sense for most algorithms in most contexts.
The benefit of sticking with floats is that lots of smart people have spent countless hours trying to give non-experts a "good enough" path through the untamed wilds of numerical analysis, tooling to help them when they get lost, tribal knowledge to point out the edge cases, and it's almost universally supported in hardware. By all means you should go wandering off the trail, but fully understand what you're doing and why beforehand.
> Another way is to think of it as an interval of real numbers between the next lowest and highest intervals. Under this latter interpretation, it makes sense to discuss shortest decimal string within the interval, 0.3 in this case.
Note that the result of 0.1+0.2 does not lie in the interval containing 0.3, which is was confuses most people. The issue is that there is some imprecision in representing 0.1 and 0.2 too, and that compounds when summing, resulting in something that does not actually correspond to 0.3 (hence the classic 0.1+0.2!=0.3)
But, as I understand it, 1+2=3 in all of these senses using floating point; as long as you don’t go outside of a certain very large range, they are really a superset of integers.
That makes me think that I can just plan ahead by storing the number of cents instead of dollars, or a “hack”, and then it makes me wonder why the format even requires me to do that.
0.2+0.1 with floating point numbers _is_ deterministic, as you'll always get the same answer.
I suspect you might instead mean exact calculations/answers (in the example above, neither 0.1, 0.2 nor 0.3 have exact representations using floating point numbers).
And just to be clear, there are non-determinism-like issues with floating point numbers, but those are much rarer/niche and _can_ be fixed. For example parallel summation depends on the order the summation was made, so non-determinism in the parallel implementation ripples through the summation result. Some non-basic operations (e.g. trigonometric operations) have platform dependent implementations with different roundings, so you might experience different result based on the platform you're on.
CPUs have many different configuration bits to configure floating point rounding, flushing denormals, etc. which mean that in practice anything that relies on floats being deterministic has the stability of a house of cards.
> Floating point is deterministic, what are you talking about?
Order of operations can change a result, for example. I suspect you mean that the algorithm never changes. While op means that mathematical operations which most folks would expect to be reliable are not.
There are enough problems for a 44 page paper titled "What Every Computer Scientist Should Know About Floating-Point Arithmetic"[1] I don't quibble on the language because I know what people mean.
Most folks won't encounter most of the issues, generally. But expose your code to a large enough dataset, or be like me and write a CAD/CAM system with motion control and experience most of them.
That (no doubt excellent, but) technical PDF is overselling the problem somewhat, when what every dev needs to know is better represented by a friendlier summary like https://floating-point-gui.de/
That's a great resource as well. Targeted at developers, rather than computer scientists. Same observations, different target audiences and expectations. You're probably right that the more practical reference targeted at developers is more useful here. My references are full of the academic papers because of my CAD work.
No. It's been quite some time since I realized that all language is a pidgin used to translate between individuals' unique lived experiences and points of reference. And find communication much more fluid and less confrontational when the focus is on shared meaning rather than perfect word choice. Especially when working with non-native speakers, but also just people in general. Stephen Fry captures the feeling: https://www.youtube.com/watch?v=Ovi7uQbtKas
When TZubiri made their original comment, I understood they were speaking about some or all of the issues outlined in the paper I linked. If you didn't, that's ok. If you think the referenced paper missed something, it's OK to add that.
These kinds of comments tend to happen when you are assuming a shared meaning that isn't so shared. Especially in this context, it's a good idea to be precise in your terminology when there is a commonly used vocabulary for talking about it. Especially when it comes to misconceptions about floating point, which is often treated as 'random' when it generally isn't.
Sometimes specificity matters. Usually when looking directly at some specific piece of code. In this conversation, the intended meaning was clear. Folks just love being the pedant and the brinksmanship which comes with it. There's a propensity to derail otherwise useful conversations into discussions like this rather than dig deeper into what people meant, and were trying to communicate.
> In this conversation, the intended meaning was clear
Apparently it wasn't, as the commenter who originally used the term has now clarified that they did indeed mean non-deterministic. You misunderstood them.
So maybe being specific about terminology here isn't just pointless pedantry?
Regardless of his choice of words, he's specified that he's speaking about IEEE754 and the sort of issues which arise systemically from the compromises inherent in it's design.
He can't attest to them being the same ones in the paper I linked, but I can. Everything he's said is in line with the situation detailed within.
He and I seem to understand each other. I get what he's saying. How the issues with IEEE754 give rise to the nondeterminism he's talking about. I should, I wrote a whole system of libraries to deal with them. Do you understand the conversation? Because it seems like you think we're talking about two unrelated things and you're still arguing over terminology.
Thanks for following the thread. I'll clarify on my intended meaning was indeed a strict actual definition of determinism, but a broader definition of floating point, to include its actual usage. But fwiw, it was indeed possible that I was someone who confuses determinism for precision, but no.
When I said that floating points are not deterministic, I wasn't very precise, but I do think that broadly speaking, floating point arithmetic, as used today, foregoes determinism, and this results from the very ethos of the foundational IEEE754 data type, the goal is to have a data type for approximate answers, turns out that when exact answers are sacrificed in the name of speed, so is determinism. And this has huge effects on modern day, Floating Point is used on separate hardware with parallel operations, and there's race conditions that make most Machine Learning and AI computing irreproducible, and that indeed seems to be a consequence, as you mention, of the lack of associativity of FP.
So, that said, I would make two clarifications:
>-- Floating Points
>++ Floating Point computing
where by Floating Point computing would mean the actual application computing that we build, as opposed to "Floating points" referring to the ideal ancient standardized hardware layer abstractions.
And if necessary:
> -- is
> ++ tends to be
In order to be perfectly correct, which after all, is what we are going after.
So if pressed, I wouldn't say "Floating points are not deterministic" but "Floating Point computing tends to be non-deterministic", but I would feel very comfortable shorthanding it to "Floating Points are non-deterministic" anyways.
The paper cited is a bit hard for me, so I can't verify if it matches what I'm saying. But I imagine by the date, it wouldn't be able to address the issues that we can empirically from the advent of ML systems, but maybe it did foresee from a theoretical standpoint some of their limitations.
There's a between-the-lines thesis here that there's two main schools of computing nowadays, one that seeks perfection, and another that seeks approximations, the CPU/GPU dichotomy is roughly analogous to the Mathematics/Physics vs Engineering/Industrial dichotomy.rroot@t14:/mnt/c/Users/TomZubiri/Desktop# cat fixed.txt
Thanks for following the thread. I'll clarify on my intended meaning was indeed a strict actual definition of determinism, but a broader definition of floating point, to include its actual usage. But fwiw, it was indeed possible that I was someone who confuses determinism for precision, but no.
When I said that floating points are not deterministic, I wasn't very precise, but I do think that broadly speaking, floating point arithmetic, as used today, foregoes determinism, and this results from the very ethos of the foundational IEEE754 data type, the goal is to have a data type for approximate answers, turns out that when exact answers are sacrificed in the name of speed, so is determinism. And this has huge effects on modern day, Floating Point is used on separate hardware with parallel operations, and there's race conditions that make most Machine Learning and AI computing irreproducible, and that indeed seems to be a consequence, as you mention, of the lack of associativity of FP.
So, that said, I would make two clarifications:
>-- Floating Points
>++ Floating Point computing
where by Floating Point computing would mean the actual application computing that we build, as opposed to "Floating points" referring to the ideal ancient standardized hardware layer abstractions.
And if necessary:
> -- is
> ++ tends to be
In order to be perfectly correct, which after all, is what we are going after.
So if pressed, I wouldn't say "Floating points are not deterministic" but "Floating Point computing tends to be non-deterministic", but I would feel very comfortable shorthanding it to "Floating Points are non-deterministic" anyways.
The paper cited is a bit hard for me, so I can't verify if it matches what I'm saying. But I imagine by the date, it wouldn't be able to address the issues that we can empirically from the advent of ML systems, but maybe it did foresee from a theoretical standpoint some of their limitations.
There's a between-the-lines thesis here that there's two main schools of computing nowadays, one that seeks perfection, and another that seeks approximations, the CPU/GPU dichotomy is roughly analogous to the Mathematics/Physics vs Engineering/Industrial dichotomy.
> when exact answers are sacrificed in the name of speed
I have found in https://github.com/timschmidt/hyperreal and the geometry layers built atop it, that exactness and speed are not fundamentally opposed. Hyperreal retains exact mathematical structure at the scalar level, and at each level higher up through vertices, vectors, matrices, triangles, curves, etc. And uses it to choose optimal datatypes, dispatch against the fastest algorithms, and eliminate large chunks of needless calculation where simpler proofs are sufficient.
The downside is a bit of additional code and API complexity. But the slightly more complex API accurately represents issues like uncertainty in decidable equality of arbitrary computables in bounded time, which is a limitation of math itself, so representing it accurately in the API permits the algorithms to be more robust.
> Floating Point is used on separate hardware with parallel operations, and there's race conditions that make most Machine Learning and AI computing irreproducible
Deterministic reproducibility is, I think, one of the most awesome superpowers of a system like hyperreal. It makes simulation much more interesting and useful. As well as cross-platform use.
floating point arithmetic, as used today, foregoes determinism, and this results from the very ethos of the foundational IEEE754 data type
This was somewhat true in the past, but the situation has been improving dramatically in recent years to the point where FP determinism is completely feasible. The remaining hurdles are primarily on the toolchains/kernel side. I have a library called rfloat that you can drop into most C/C++ code for practical determinism without thought (subject to documented caveats), for example. You can do the same thing manually with some more careful attention.
I'm in a very remote corner of the world on bad Wi-Fi though, so you'll have to forgive omitted links.
Also of interest: Herbie analyzes your math expressions and helps you figure out where FP error accumulates. https://herbie.uwplse.org/demo/
We use floats as a trade-off between speed and accuracy. IEEE 754 is a very reasonable trade-off for a wide range of applications, but if you can figure out where you need to trade speed to get more accuracy with e.g. one of the methods mentioned here, Herbie's gotcha covered.
I remember seeing some research about switching between formats, but I don't have anything to cite right now.
In some cases I use binary fixed-point numbers. In certain aspects they are much better than floats - no precision loss happens in addition/subtraction (if no overflow/underflow takes place), additions and subtractions are typically faster (since it's just an integer operation internally), casting from and to integers is also cheap (requires only bit-shift).
Multiplications are a little bit tricky. Multiplication by an integer is trivial. Multiplication of two fixed point numbers produces the result with the number of fractional binary digits equal to sum of the number of fractional digits in source numbers. The result may be stored in an extended type, truncated down or rounded.
Divisions work fine too, but sometimes may be slower compared to float types, because CPUs can for some reason do much faster floating-point divisions compared to integer divisions.
The only disadvantage of fixed-point numbers is that it's required to keep a balance between range and precision carefully. One can't just use some specific precision in the entire codebase, typically precision should be selected for each individual operation.
A neat trick many people aren't aware of is that you can treat binary floats as saturating fixed point, subject to some qualifications (generally the next larger float type can represent any given fixed). Float operations internally are "just" fixed point ops with some normalization steps and rounding bits on each side, so if we use a float type with enough mantissa bits to hold the fixed point value all we have to do is mask off the extra precision to get back to fixed point. This similarity to fixed point is exploited in some modern NPU hardware by storing only one exponent for an entire block of floats, with a wide fixed point unit doing the actual work, a.k.a block floating point.
This hack has some interesting advantages. Float to integer is still only a few cycles, the masking is one line of libm functions, you get better (and dynamically selectable!) precision, it has gradual underflow and overflow, you can write numeric code like usual, and normalization is automatic.
Worth noting the gap between floating point vs integer division isn't that bad on newer CPUs these days. On Zen5, for instance, DIVSD has a latency of 13 cycles vs 16 cycles for DIV.
Fixed-point can also be much more efficient in terms of bits if you know you are staying within some range. If you're working with 32 bits this can be a pretty big difference (4 billion values vs 8 million for single-precision floats).
>Divisions work fine too, but sometimes may be slower compared to float types, because CPUs can for some reason do much faster floating-point divisions compared to integer divisions.
The mantissa of a floating point number has less bits than the integer type of the same byte size.
Yeah I wonder why they aren't used for neural networks. It's been claimed they'd require far less power and they'd offer better accuracy and faster computations, although I am unable to verify that claim.
It's an infinite precision exact constructive real with excellent performance characteristics and approximation only at explicitly named lossy export functions.
“You’re making one operation cheaper, but making the other one more expensive” is the wrong way around. Say it this way: “You’re making one operation more expensive, but the other one cheaper.”
That's kind of exactly what floats are. You store the log2 of the number, a bit for its sign, and in what remaining bits you have left some fixed-point scaling between adjacent powers.
No, that is not what floats are. A logarithmic number system literally just stores the logarithm of a number (and a sign bit) and manipulates it as a logarithm. The significand is 1, always. So multiplication & division are simply addition & subtraction, respectively. But this simplification for multiplication, division, roots, and powers is counterbalanced by more complex addition and subtraction.[1]
None of the base 10 formats, but the hobby calculation language Frink supports exact rational fractions, arbitrary width bigints (not pictured), intervals arithmetic, and symbolic expressions.
Consider representing money in cents ¢ instead of $, €, etc. Often it’s faster to parse a serialized integer then divide by 100 than to parse a decimal value. And sometimes it’s faster to serialize and sometimes you can serialize to fewer bytes. And often aggregation of integers is faster. And it may make supporting non-decimalized currencies, such as ¥, easier.
Usually, if you know enough about your algorithms to select an appropriate float alternative, you also know enough to fix your float code and that's what you should actually do.
That said, some of these aren't alternatives. Symbolic computation is a different thing entirely. Interval arithmetic can be built atop floats (e.g. IEEE-1788) and has its own zoo of unintuitive behaviors. BCD is better called a historical artifact than an alternative these days.
It's really just rationals and decimal floats in this list, which probably don't solve the issues you have if you're considering float alternatives.
> BCD is better called a historical artifact than an alternative these days.
It's currently in use all over the world. You can't do a card payment, either in-person or online, without an intermediary using ISO8583.
I think people with certain backgrounds look at stuff like x86 BCD opcodes being removed in the move from x86-32 to amd64 and think "must be because noone uses it". Other backgrounds know that ain't so.
You can't "fix" floating point code if you are looking for deterministic answers. You just have to use other data types to handle money or complex mathematical operations like 0.2+0.1, no ifs and buts.
Floats are deterministic, but I get what you mean. Let's discuss what's meant by the result of a complex calculation. 0.1+0.2, or sqrt(2), or whatever.
1. Do you want your result to exactly encode the answer without rounding error? No fixed precision type can provide this in general, so you're stuck with symbolic approaches. If you can bound things (usually difficult), maybe you can get away with non-symbolic approaches.
2. Do you want a sensible numeric answer? This is what floats (and many other systems) give you. The definition of "sensible" is inherently tricky here and there's not a definition universally appropriate to every possible computation.
So let's return to 0.1+0.2=0.3000...1 specifically. There's two common ways to think of an encoded float. One is as the directly encoded value, as you're doing. Another way is to think of it as an interval of real numbers between the next lowest and highest intervals. Under this latter interpretation, it makes sense to discuss shortest decimal string within the interval, 0.3 in this case. There's no ambiguity because each real lives in exactly one interval. This is what algorithms like dragon box do for float to decimal string conversion.
What decimal floats give you is an encoding that tracks significant digits, where every decimal string exactly corresponds to a midpoint of an interval of reals. They do this at the cost of space, speed, and complexity. You don't get an escape from the fundamental issues of fixed precision types like rounding error, numerical sensitivity, precision loss, etc. I don't think that tradeoff makes sense for most algorithms in most contexts.
The benefit of sticking with floats is that lots of smart people have spent countless hours trying to give non-experts a "good enough" path through the untamed wilds of numerical analysis, tooling to help them when they get lost, tribal knowledge to point out the edge cases, and it's almost universally supported in hardware. By all means you should go wandering off the trail, but fully understand what you're doing and why beforehand.
> Another way is to think of it as an interval of real numbers between the next lowest and highest intervals. Under this latter interpretation, it makes sense to discuss shortest decimal string within the interval, 0.3 in this case.
Note that the result of 0.1+0.2 does not lie in the interval containing 0.3, which is was confuses most people. The issue is that there is some imprecision in representing 0.1 and 0.2 too, and that compounds when summing, resulting in something that does not actually correspond to 0.3 (hence the classic 0.1+0.2!=0.3)
But, as I understand it, 1+2=3 in all of these senses using floating point; as long as you don’t go outside of a certain very large range, they are really a superset of integers.
That makes me think that I can just plan ahead by storing the number of cents instead of dollars, or a “hack”, and then it makes me wonder why the format even requires me to do that.
> deterministic answers
> 0.2+0.1
0.2+0.1 with floating point numbers _is_ deterministic, as you'll always get the same answer.
I suspect you might instead mean exact calculations/answers (in the example above, neither 0.1, 0.2 nor 0.3 have exact representations using floating point numbers).
And just to be clear, there are non-determinism-like issues with floating point numbers, but those are much rarer/niche and _can_ be fixed. For example parallel summation depends on the order the summation was made, so non-determinism in the parallel implementation ripples through the summation result. Some non-basic operations (e.g. trigonometric operations) have platform dependent implementations with different roundings, so you might experience different result based on the platform you're on.
Floating point is deterministic, what are you talking about?
> You just have to use other data types to handle money or complex mathematical operations like 0.2+0.1
Such as... decimal floating point.
CPUs have many different configuration bits to configure floating point rounding, flushing denormals, etc. which mean that in practice anything that relies on floats being deterministic has the stability of a house of cards.
All of which are well defined and can be configured from user space. That doesn't make them non-deterministic.
> Floating point is deterministic, what are you talking about?
Order of operations can change a result, for example. I suspect you mean that the algorithm never changes. While op means that mathematical operations which most folks would expect to be reliable are not.
They're not associative, sure. But that's a very far cry from claiming they're non-deterministic.
There are enough problems for a 44 page paper titled "What Every Computer Scientist Should Know About Floating-Point Arithmetic"[1] I don't quibble on the language because I know what people mean.
Most folks won't encounter most of the issues, generally. But expose your code to a large enough dataset, or be like me and write a CAD/CAM system with motion control and experience most of them.
That's why I wrote hyperreal[2]
1: https://www.cs.tufts.edu/cs/40/docs/WhatEveryComputerScienti...
2: https://github.com/timschmidt/hyperreal
That (no doubt excellent, but) technical PDF is overselling the problem somewhat, when what every dev needs to know is better represented by a friendlier summary like https://floating-point-gui.de/
That's a great resource as well. Targeted at developers, rather than computer scientists. Same observations, different target audiences and expectations. You're probably right that the more practical reference targeted at developers is more useful here. My references are full of the academic papers because of my CAD work.
> Targeted at developers
Sorry, yes, I probably should have worded that in a way that made the distinction more obvious.
You don’t quibble about what words mean when the words you choose have very specific meanings in exactly the subject area you are talking about?
You make it really hard to take you seriously.
No. It's been quite some time since I realized that all language is a pidgin used to translate between individuals' unique lived experiences and points of reference. And find communication much more fluid and less confrontational when the focus is on shared meaning rather than perfect word choice. Especially when working with non-native speakers, but also just people in general. Stephen Fry captures the feeling: https://www.youtube.com/watch?v=Ovi7uQbtKas
When TZubiri made their original comment, I understood they were speaking about some or all of the issues outlined in the paper I linked. If you didn't, that's ok. If you think the referenced paper missed something, it's OK to add that.
> You make it really hard to take you seriously.
Same, bud.
These kinds of comments tend to happen when you are assuming a shared meaning that isn't so shared. Especially in this context, it's a good idea to be precise in your terminology when there is a commonly used vocabulary for talking about it. Especially when it comes to misconceptions about floating point, which is often treated as 'random' when it generally isn't.
Sometimes specificity matters. Usually when looking directly at some specific piece of code. In this conversation, the intended meaning was clear. Folks just love being the pedant and the brinksmanship which comes with it. There's a propensity to derail otherwise useful conversations into discussions like this rather than dig deeper into what people meant, and were trying to communicate.
> In this conversation, the intended meaning was clear
Apparently it wasn't, as the commenter who originally used the term has now clarified that they did indeed mean non-deterministic. You misunderstood them.
So maybe being specific about terminology here isn't just pointless pedantry?
Regardless of his choice of words, he's specified that he's speaking about IEEE754 and the sort of issues which arise systemically from the compromises inherent in it's design.
He can't attest to them being the same ones in the paper I linked, but I can. Everything he's said is in line with the situation detailed within.
He and I seem to understand each other. I get what he's saying. How the issues with IEEE754 give rise to the nondeterminism he's talking about. I should, I wrote a whole system of libraries to deal with them. Do you understand the conversation? Because it seems like you think we're talking about two unrelated things and you're still arguing over terminology.
Thanks for following the thread. I'll clarify on my intended meaning was indeed a strict actual definition of determinism, but a broader definition of floating point, to include its actual usage. But fwiw, it was indeed possible that I was someone who confuses determinism for precision, but no.
When I said that floating points are not deterministic, I wasn't very precise, but I do think that broadly speaking, floating point arithmetic, as used today, foregoes determinism, and this results from the very ethos of the foundational IEEE754 data type, the goal is to have a data type for approximate answers, turns out that when exact answers are sacrificed in the name of speed, so is determinism. And this has huge effects on modern day, Floating Point is used on separate hardware with parallel operations, and there's race conditions that make most Machine Learning and AI computing irreproducible, and that indeed seems to be a consequence, as you mention, of the lack of associativity of FP.
So, that said, I would make two clarifications:
>-- Floating Points
>++ Floating Point computing
where by Floating Point computing would mean the actual application computing that we build, as opposed to "Floating points" referring to the ideal ancient standardized hardware layer abstractions.
And if necessary:
> -- is
> ++ tends to be
In order to be perfectly correct, which after all, is what we are going after.
So if pressed, I wouldn't say "Floating points are not deterministic" but "Floating Point computing tends to be non-deterministic", but I would feel very comfortable shorthanding it to "Floating Points are non-deterministic" anyways.
The paper cited is a bit hard for me, so I can't verify if it matches what I'm saying. But I imagine by the date, it wouldn't be able to address the issues that we can empirically from the advent of ML systems, but maybe it did foresee from a theoretical standpoint some of their limitations.
There's a between-the-lines thesis here that there's two main schools of computing nowadays, one that seeks perfection, and another that seeks approximations, the CPU/GPU dichotomy is roughly analogous to the Mathematics/Physics vs Engineering/Industrial dichotomy.rroot@t14:/mnt/c/Users/TomZubiri/Desktop# cat fixed.txt Thanks for following the thread. I'll clarify on my intended meaning was indeed a strict actual definition of determinism, but a broader definition of floating point, to include its actual usage. But fwiw, it was indeed possible that I was someone who confuses determinism for precision, but no.
When I said that floating points are not deterministic, I wasn't very precise, but I do think that broadly speaking, floating point arithmetic, as used today, foregoes determinism, and this results from the very ethos of the foundational IEEE754 data type, the goal is to have a data type for approximate answers, turns out that when exact answers are sacrificed in the name of speed, so is determinism. And this has huge effects on modern day, Floating Point is used on separate hardware with parallel operations, and there's race conditions that make most Machine Learning and AI computing irreproducible, and that indeed seems to be a consequence, as you mention, of the lack of associativity of FP.
So, that said, I would make two clarifications:
>-- Floating Points
>++ Floating Point computing
where by Floating Point computing would mean the actual application computing that we build, as opposed to "Floating points" referring to the ideal ancient standardized hardware layer abstractions.
And if necessary:
> -- is
> ++ tends to be
In order to be perfectly correct, which after all, is what we are going after.
So if pressed, I wouldn't say "Floating points are not deterministic" but "Floating Point computing tends to be non-deterministic", but I would feel very comfortable shorthanding it to "Floating Points are non-deterministic" anyways.
The paper cited is a bit hard for me, so I can't verify if it matches what I'm saying. But I imagine by the date, it wouldn't be able to address the issues that we can empirically from the advent of ML systems, but maybe it did foresee from a theoretical standpoint some of their limitations.
There's a between-the-lines thesis here that there's two main schools of computing nowadays, one that seeks perfection, and another that seeks approximations, the CPU/GPU dichotomy is roughly analogous to the Mathematics/Physics vs Engineering/Industrial dichotomy.
> when exact answers are sacrificed in the name of speed
I have found in https://github.com/timschmidt/hyperreal and the geometry layers built atop it, that exactness and speed are not fundamentally opposed. Hyperreal retains exact mathematical structure at the scalar level, and at each level higher up through vertices, vectors, matrices, triangles, curves, etc. And uses it to choose optimal datatypes, dispatch against the fastest algorithms, and eliminate large chunks of needless calculation where simpler proofs are sufficient.
The downside is a bit of additional code and API complexity. But the slightly more complex API accurately represents issues like uncertainty in decidable equality of arbitrary computables in bounded time, which is a limitation of math itself, so representing it accurately in the API permits the algorithms to be more robust.
> Floating Point is used on separate hardware with parallel operations, and there's race conditions that make most Machine Learning and AI computing irreproducible
Deterministic reproducibility is, I think, one of the most awesome superpowers of a system like hyperreal. It makes simulation much more interesting and useful. As well as cross-platform use.
I'm in a very remote corner of the world on bad Wi-Fi though, so you'll have to forgive omitted links.
Also of interest: Herbie analyzes your math expressions and helps you figure out where FP error accumulates. https://herbie.uwplse.org/demo/
We use floats as a trade-off between speed and accuracy. IEEE 754 is a very reasonable trade-off for a wide range of applications, but if you can figure out where you need to trade speed to get more accuracy with e.g. one of the methods mentioned here, Herbie's gotcha covered.
I remember seeing some research about switching between formats, but I don't have anything to cite right now.
In some cases I use binary fixed-point numbers. In certain aspects they are much better than floats - no precision loss happens in addition/subtraction (if no overflow/underflow takes place), additions and subtractions are typically faster (since it's just an integer operation internally), casting from and to integers is also cheap (requires only bit-shift).
Multiplications are a little bit tricky. Multiplication by an integer is trivial. Multiplication of two fixed point numbers produces the result with the number of fractional binary digits equal to sum of the number of fractional digits in source numbers. The result may be stored in an extended type, truncated down or rounded.
Divisions work fine too, but sometimes may be slower compared to float types, because CPUs can for some reason do much faster floating-point divisions compared to integer divisions.
The only disadvantage of fixed-point numbers is that it's required to keep a balance between range and precision carefully. One can't just use some specific precision in the entire codebase, typically precision should be selected for each individual operation.
A neat trick many people aren't aware of is that you can treat binary floats as saturating fixed point, subject to some qualifications (generally the next larger float type can represent any given fixed). Float operations internally are "just" fixed point ops with some normalization steps and rounding bits on each side, so if we use a float type with enough mantissa bits to hold the fixed point value all we have to do is mask off the extra precision to get back to fixed point. This similarity to fixed point is exploited in some modern NPU hardware by storing only one exponent for an entire block of floats, with a wide fixed point unit doing the actual work, a.k.a block floating point.
This hack has some interesting advantages. Float to integer is still only a few cycles, the masking is one line of libm functions, you get better (and dynamically selectable!) precision, it has gradual underflow and overflow, you can write numeric code like usual, and normalization is automatic.
Worth noting the gap between floating point vs integer division isn't that bad on newer CPUs these days. On Zen5, for instance, DIVSD has a latency of 13 cycles vs 16 cycles for DIV.
Fixed-point can also be much more efficient in terms of bits if you know you are staying within some range. If you're working with 32 bits this can be a pretty big difference (4 billion values vs 8 million for single-precision floats).
>Divisions work fine too, but sometimes may be slower compared to float types, because CPUs can for some reason do much faster floating-point divisions compared to integer divisions.
The mantissa of a floating point number has less bits than the integer type of the same byte size.
Don't forget Posits (Unum). https://www.cs.cornell.edu/courses/cs6120/2019fa/blog/posits...
i recommend the book "The End of Error: Unum Computing"
Yeah I wonder why they aren't used for neural networks. It's been claimed they'd require far less power and they'd offer better accuracy and faster computations, although I am unable to verify that claim.
Strange the most obvious - fixed point numbers is not mentioned.
https://wizardzines.com/comics/fixed-point/
Nor unums!!
Oh hey, one of my projects is relevant to an article: https://github.com/timschmidt/hyperreal
It's an infinite precision exact constructive real with excellent performance characteristics and approximation only at explicitly named lossy export functions.
Some recent benchmarks: https://github.com/timschmidt/hyperlattice/blob/805d092d1d96...
Worth mentioning is storing the logarithm of the number.
Seen it used in a couple places. Logarithmic depth buffer is one. Yamaha DX7 is another.
You can also use this in analog hardware! :D
https://en.wikipedia.org/wiki/Translinear_circuit
how do you do FMAs then? You're making one operation cheaper, but making the other one expensive.
“You’re making one operation cheaper, but making the other one more expensive” is the wrong way around. Say it this way: “You’re making one operation more expensive, but the other one cheaper.”
That's kind of exactly what floats are. You store the log2 of the number, a bit for its sign, and in what remaining bits you have left some fixed-point scaling between adjacent powers.
No, that is not what floats are. A logarithmic number system literally just stores the logarithm of a number (and a sign bit) and manipulates it as a logarithm. The significand is 1, always. So multiplication & division are simply addition & subtraction, respectively. But this simplification for multiplication, division, roots, and powers is counterbalanced by more complex addition and subtraction.[1]
[1] https://en.wikipedia.org/wiki/Logarithmic_number_system
Floats are actually rational numbers with denominators of power of 2.
https://en.wikipedia.org/wiki/Dyadic_rational#In_computing
I think they mean storing just an exponent instead of an exponent + mantissa. Makes multiplication much easier to implement.
None of the base 10 formats, but the hobby calculation language Frink supports exact rational fractions, arbitrary width bigints (not pictured), intervals arithmetic, and symbolic expressions.
https://frinklang.org/fsp/frink.fsp?fromVal=new+interval%5B-...
Consider representing money in cents ¢ instead of $, €, etc. Often it’s faster to parse a serialized integer then divide by 100 than to parse a decimal value. And sometimes it’s faster to serialize and sometimes you can serialize to fewer bytes. And often aggregation of integers is faster. And it may make supporting non-decimalized currencies, such as ¥, easier.
[dead]