Formatting floating point numbers
zverovich.net
zverovich.net
It's really surprising, how long it took to find the most efficient algorithms for double-conversions. In 1980 Coonen already published a good algorithm, but that one was kind-of lost.
For a long time Steele & White's algorithm was the state-of-the-art (with some improvements here and there over time).
Now, Ryu is by far the fastest algorithm out there, but that took ages...
Unfortunately, there doesn't seem to be an easy-to-use, complete library for Ryu yet.
The Grisu library (https://github.com/google/double-conversion) is probably still the go-to library if you don't want to implement it again...
Internally it uses the same algorithm, Grisu, (with some additional optimizations) so there shouldn't be any difference in output.
If it's easier to use for you, just go with it!
I'm guessing the double-conversion library is a bit more flexible, but I could be wrong.
#include "third_party/double-conversion/double-conversion/double-conversion.h"> Expands to the most recent, preceding word for which this is a prefix.
"Correct" conversion, where the length doesn't matter (which could be called "fixed length" for a certain length that is big enough) is easier, because one can avoid a lot of rounding and imprecision issue: using the right technique, just produce enough digits until the imprecisions don't matter anymore.
However, fixed length is as difficult as the shortest, if the length is limited, since the last digit sometimes lies on the boundary and thus runs into the same difficulties as the shortest digit. Think of it this way: needing to decide whether 6 digits is enough, is often similar to asking whether the 6th digit is a 0 or a 9 (roughly speaking). This means that producing the best fixed-length representation (for length 6) runs into the exactly same question.
https://dl.acm.org/citation.cfm?id=3192369
"Ryū: fast float-to-string conversion", Ulf Adams 2018
"Section 5 reviews the existing literature. All of the early ap- proaches require arbitrary precision arithmetic in the general case. More recent developments work with xed precision arithmetic, which is faster, but can increase the complexity of the code. By contrast, Ryu ̄ is simple and fast."
Also interesting:
"We did not compare our implementation against the C standard library function printf, as its specification does not include the correctness criteria set forth by Steele and White [15], and, accordingly, neither the glibc nor the MacOS implementation does."
In fact, thinking about it now, I bet Wireshark would be awesome for that.
This won't account for endianness.
In the future, hopefully big-endian machines will be as uncommon as bytes that are not 8 bits, and the only protocols still using it are the ones which were designed long ago.
> printf ("%a\n", M_PI);
0x1.921fb54442d18p+1
> printf ("%a\n", 42.0);
0x1.5p+5Edit: someone else mentioned that roundtrip accuracy could also be an issue. Theoretically true, I guess, but really, if you want to use decimal-based float input you should just use an algorithm that roundtrips correctly, and eat that overhead. Anything else has a potential to impact reproducibility of results, etc. It's not worth it silently corrupting your data just for that saving in compute cost.
Sometimes you do need to reliably communicate a floating-point number across a text channel. Hex float is low-risk in the sense that both the encoding and decoding process are much simpler and therefore easier to verify than something that round-trips through decimal. Yes, there are some correct implementations of the decimal<->binary algorithms that round-trip correctly. But there also remain a number of incorrect implementations.
An interesting aspect of decimal formatting is how it frequently masks representation error (i.e encoding of 0.1 etc), because the error is symmetrical in the formatter/parser it makes such non-representable fractions appear to be stored perfectly to unsuspecting users.
This can be quite deceptive, if more users were aware of just how many of the simple rational decimals they input were converted into imprecise representations they probably wouldn't trust computers as much as they do. To confuse things more, when operating upon periodic representations the result often matches the representation error of the the equivalent accurate decimal value encoded directly (i.e there were errors, but everything canceled out through formatting) - when they occasionally do not (e.g 0.1 + 0.2) it makes the problem appear all the more elusive.
I think this detail is often lost in explanations of 0.1 + 0.2, that is: representation error is extremely common, 0.1 + 0.2 is merely one of the cases where it both persists through the formatter AND you notice it because the inputs were short decimals, and it's so obvious that the output should be a non-periodic decimal..
TL;DR formatting floats to decimals makes us trust floating point math far more than we should - it's healthy to remember that the formatting process is necessarily imprecise and that you are merely looking at a proxy for the underlying value. Remember that next time you look at _seemingly_ non-periodic decimal output.
When I format a float out to 5 decimal places, I'm sort of making a statement that anything beyond that doesn't matter to me.
Yes, it's true the vast majority of the time it doesn't actually matter. However decimal formatting does such a good job at giving us the impression that these errors are merely edge-cases, and calculators automatically formatting to 10sf etc further that illusion. If people are not aware it's only an illusion (or just how far the rabbit hole goes) it can be dangerous when they go on to create or use things where that fact matters.
I'd be curious to hear some of the problems programmers have run into from this conceptual discrepancy. We've got probably billions of running instances of web frameworks build atop double precision IEEE 754 to choose from. Are there any obvious examples you know?
These are an easy target to find issues that _matter_ because users are essentially fuzzing the inputs, so they are bound to find an error if it exists, and they will also care when they do!
When these oversights become a problem is very context sensitive. I suppose mine is quite biased.
That is far inside the range of 64bit double precision. For error to propagate up to that range of significance depends on the math, but i doubt the aggregation you are describing would cause it... provided nothing silly happens to subtotals like intermediate rounding to precision (you'd be surprised).
Something like compounding as the parent was describing are far more prone to significant error propagation.
In a real-life transaction where pennies are not exchanged this could mean a difference of a nickel on a $20 purchase which isn't a meaningful difference but certainly not insignificant.
What does this mean to you? It's very easy to get horrible rounding error with real-life sized things. For instance
document.writeln(1.0 % 0.2);
btw: I think IEEE-754 is really great, but it's also important to understand your tools.
The types of errors being discussed by others are all in the realm of non-integer rationals where limitations in either precision or representation introduce error and then compound in operations no matter the order of magnitude... and btw _real_ life tends to contain _real_ numbers, that commonly includes rationals in use of IEEE 754.
> The right answer is 0.0, and the most it can be wrong is 0.2. It's nearly as wrong as possible.
Just to clarify for others, you're implicitly contriving that to mean: you care about the error being positive. The numerical error in 0.1 % 0.2 is actually fairly ordinarily tiny (on the order of x10^-17), but using modulo may create sensitivity to these tiny errors by introducing discontinuity where it matters.
Not sure why you changed it from "1.0 % 0.2" to "0.1 % 0.2". The error on the one I showed was near 0.2, not 1e-17. Did I miss your point?
I'm not arguing against you just clarifying the difference between propagation of error into significant numerical error through something like compounding; and being sensitive to very tiny errors by to depending on discontinuities such as those introduced by modulo.
x = 1e-20 + 1e20 - 1e20
y = 1e20 - 1e20 + 1e-20
assert x == y* Never mind that "millions" isn't large by current standards...
x = 1e20 + 1 - 1e20
y = 1e20 - 1e20 + 1
assert x == y
class Time {
uint32 m_CycleCount;
float m_CyclesPerSec;
float m_Time;
public:
Time() {
m_CyclesPerSec = CPU_GetCyclesPerSec();
m_CycleCount = CPU_GetCurCycleCount();
m_Time = 0.0f;
}
float GetTime() { return m_Time; }
void Update() {
// note that this is expected to wrap
// during the lifetime of the game --
// modular math works correctly in that case
// as long as Update() is called at least once
// every 2^32-1 cycles.
uint32 curCycleCount = CPU_GetCurCycleCount();
float dt = (m_CycleCount - curCycleCount) / m_CyclesPerSec;
m_CycleCount = curCycleCount;
m_Time += dt;
}
};
void GAME_MainLoop() {
Timer t;
while( !GAME_HasQuit() ) {
t.Update();
GAME_step( t.GetTime() );
}
}
At 300fps, time will literally stop advancing after the game has been running for around 8 hours, and in-game things that depend on framerate can become noticably jittery well before then.
https://randomascii.wordpress.com/category/floating-point/
https://stackoverflow.com/questions/46028336/inconsistent-be...
The root problem, of course, was that 0.2 + 0.1 <= 0.3 isn't actually true in floating point arithmetic.
It wasn't immediately obvious where the problem was since there were a lot of moving parts in play, and it did not immediately occur to us to doubt the seemingly simple arithmetic.
One thing along similar lines that I've always hated to see is when the floating-point type in a programming language is called "real".
Whereas, even between their minimum and maximum values, and even subject to their numeric precision, there are still so many rational numbers that an IEEE float can't represent. So it's not even a rational. Nor can it represent a single irrational number, thereby failing to capture one iota of what qualitatively distinguishes the real numbers. . . if Hacker News supported gifs, I'd be inserting one that features Mandy Patinkin right here.
Thanks for the read! More fun than the original article to my taste :)
Here's the link, since Googling "floating bar" nets you very different results:
http://www.iquilezles.org/www/articles/floatingbar/floatingb...
My favorite post by him is where he explains that you never need to have trigonometry calls in your 3D engine. Because everyone now and then you still see "educational" article in the spirit of "learn trig to spin a cube in 3D!" :/
I guess the smart people writing a lot of this stuff just assume everyone will derive them as they go. That's why we need more Inigo Quilez's :D to lay it out for us mere mortals and encourage it's use more widely.
You can't say the same about most real numbers, all the ones that we postulate must exist but that have infinite complexity. You can't ever construct a single one of them.
Or in other words: It can store all the non-computable numbers you give it. That should suffice.
Of course any self-respecting modern language should also provide arbitrary-precision integers at least as an option.
One that comes to mind for me is the old game Kohan: Immortal Sovereigns. There was a native Linux port for the game that could play online with the Windows machines. However, the pathfinding solution used floating point numbers to make the decisions. A very small difference in the way Linux and Windows rounded the numbers meant that an online game between a Linux and Windows host would de-synchronize after 15-30 minutes because a model that zigged on the Linux host would zag on the Windows host, and the game would detect the difference in state after a bit and kick one of the players out. There was no way to rejoin the game at this point either.
This bug was never fixed, and the company that made the port (Loki) went out of business.
Don't knock the impact of cumulative loss of precision.
Another way to phrase it is that a single float value represents a range of real numbers, rather than a single real number. So 0.1 stored as a double precision float really represents the range of real numbers from roughly 0.09999999999999999862 to 0.10000000000000001249.
But the range is different for every number, it's not a constant error like precision epsilon. I think "representation error" is reasonable name, as it's used when describing the error in converting representation between base10 and base2.
> I wonder about the terminology of calling these "errors". That implies that there's a mistake, when really floats are among the most accurate ways to represent arbitrary real numbers in a finite number of bits.
If you only care about the irrational portion of real numbers maybe, but for rationals this is definitely not true, you could use a format based on fractions which unlike IEEE754 would contain no representation error compared to base 10 decimals - in fact they would even allow you to represent rationals that base10 decimals could not such as 1/3. Inigo Quilez came up with one such format "floating bar" [1]. There are advantages and disadvantages to such a format (e.g performance). But in terms of numerical error I doubt IEEE 754 is best, for representation error it is definitely not (and I say that as someone who likes the IEEE 754 design O_o).
[1] http://www.iquilezles.org/www/articles/floatingbar/floatingb...
I'm not sure I understand what you mean by "holes", the idea is that all the real numbers between roughly 0.09999999999999999862 and 0.10000000000000001249 are represented by the same double precision floating point value as for 0.1.
Thinking about it in terms of ranges helps to understand why 0.1 + 0.2 goes "wrong", as the middle of the range of real numbers represented by a double precision floating point value 0.1 is slightly higher than 0.1.
How if you took a limited precision range of rationals in base 10, e.g 0.10000 to 0.20000 and convert them to base 2, there are "holes" of non-representable numbers in the range. These holes are of different sizes, (one of which is the range you are talking about), so I summarized it as that.
There is nothing inherently less accurate about binary floating-point representation than decimal. Some binary numbers can be identical to their decimal counterparts, while others aren't. This is OK, as we should know what amount of precision is required in our answer and round to that.
No, exactly, if the decimal was non-periodic such as 0.1 it is exact, it is exactly representing 1/10, but base2 cannot represent 1/10 exactly.
> There is nothing inherently less accurate about binary floating-point representation than decimal.
Yes there is, and this is the part that most people do not intuit, this was the entire point i was making about the deceptiveness of formatting masking representation error of the fractional part in my original comment... we are not talking merely about precision, but the representation error which is dependent on the base:
base10 base3 base2
1/10 yes no no
1/3 no yes no
1/2 yes no yes
This is not a deficiency of IEEE 754 per say, but the entire concept of a decimal point in any base, which makes it impossible to finitely represent all rational numbers, kind of making them pseudo irrational numbers as a side-effect of representation... the solution is to use fractions of course.
What is the relative error in 0.1? What is the relative error in 0.3? And what is the relative error in the sum? And whats the relative error in 0.4?
(i.e if they are the same it will be obscured by the formatter).
If you think this isn't precise enough for you, maybe you don't really understand your precision needs.
I disagree. People overestimate the accuracy of decimal encoding so much more than they ever overestimate floating point. Then when they see 0.1 + 0.2 they tend to learn entirely the wrong lesson, and start underestimating the accuracy of floating point alone.
> TL;DR formatting floats to decimals makes us trust floating point math far more than we should
The only reason a decimal encoding can cause too much trust is because we trust decimal too much. Decimal fails in exactly the same ways.
It's a trade-off of CPU usage versus flexibility. It's not surprising that textual serialization formats took off together with managed memory languages.
Text formats are popular because you don't have to use a special tool to view them. That's the only reason.
But you need a special tool to get a computer to read them. Seems like not a win. Throw in compression & encryption... and suddenly you need a special tool anyway.
e.g., when I've done my own binary formats, I typically also create a "dump" utility that converts the file to a readable text dump. I find the ergonomics of this are just fine for my purposes.
less somefile.json
dumpdat somefile.dat | less
There are probably similar issues in other programming languages, this is not to rag on Java; my point is that when you don't need the 'fancy' floating point formatting stuff, and you need high performance (in my case, I had to convert many billions of floating-points-as-strings and the conversion took ~50% of my program's runtime, which was measured in days), it can pay off to write a custom version of something as seemingly mundane as converting a string to a number.
The standard library functions occupy an awkward middle ground between this type of much faster, slightly sloppy float-to-string converter, and direct storage of the binary representation; in most applications where float serialization performance is actually relevant, at least one of these two alternatives is better.
I deal with financial data which is in well-defined formats for the various asset classes. You can save a lot of time by just writing some parsing functions to deal with your exact needs and avoid needless work. And, hopefully avoid using the built-in functions for conversions as those will almost always be A LOT slower due to what they're required to handle.
I prefer to store that type of data in csv files because there are times when you need to read through the data to find errors, adhoc analysis, etc....If you're loading those types of files very frequently, there are better formats of course. But, when the parsing time is peanuts compared to the runtime of your program, it's nice to be able to load the file into other programs when you need without having to convert it first.
What about numbers with a large order of magnitude? e.g 1e234. Is making very long strings still faster than switching to e notation?
Users probably wouldn't like it thought :P damn users.
This is easy to write off as micro-optimizing, but it's no joke. I recently profiled some hard real-time software and was surprised to find that >50% of busy processor time was spent somewhere in the fcvt() family of functions.
It's fine for the use case in the medium term (we're within deadline and not starving for more cycles) so I'm avoiding the serialization format transition headache, but it did send me down the rabbit hole of floating point conversion techniques for half a day.
Somewhat annoying, but might avoid a lot of confusion ("Is floating point math broken?", https://stackoverflow.com/questions/588004/is-floating-point... ).
1.00000000000000001999189980260288361964776078853415942018260300593659569925554346761767628861329298958274607481091185079852827053974965402226843604196126360835628314127871794272492894246908066589163059300043457860230145025079449986855914338755579873208034769049845635890960693359375e-100?As I said, make it optional...
>>> 0.1.hex()
0x1.999999999999ap-4
>>> 1e-100.hex()
0x1.bff2ee48e0530p-333Personally, I consider binary formats to be just as readable (from the hexdump, or sometimes even the ASCII directly) and in some ways even easier to parse without ambiguity --- it just requires a bit (pun intended) of learning, like any language. I've worked with someone who could "read" TCP/IP; and I can read much of Z80 and some x86 Asm as well as a few other binary formats.
You're probably going to do something stupid like showing the user a comma-separated list of numbers at some point, which will be needlessly hard to parse for a human when your numbers use a comma as a decimal separator. You (or someone else, or your users if they are technical) will probably at some point make something which tries to parse some output, and that will break if you switch between points and commas arbitrarily. Your users will want to copy a number your software prints and paste it into a calculator or REPL or something, and that probably doesn't work with comma as a decimal separator.
Half-assed "localization" from people who don't know anything about how other countries work is just needlessly annoying to be subjected to.
That's at least my perspective as a Norwegian who experiences a lot of _bad_ localization even though I know English fairly well and configure all my computing devices to use English. The perspective of someone from a country where English is less well known might be different.
<rant>
Examples of horrible localization from clueless American companies or organizations include:
* A lot of software will use your IP address to determine your language. That's annoying when I'm in Norway and want my computers to use English, but it's horrible when abroad. No, Google, I don't want French text just because I'm staying in France for a bit.
* Software will translate error messages, but not provide an error code. All information about error messages online is in English on stackoverflow or whatever. If Debian prints an error message in Norwegian, there's absolutely no information about the error anywhere on the web.
* There was a trend for a while where websites would tick the "localization" checkbox by adding a Google Translate widget, so English websites would automatically translate themselves into completely broken Norwegian automatically. That would've been useless if I didn't know English, and it's even worse considering I already know the source language just as well as Norwegian. Luckily, most websites seem to have stopped doing that.
</rant>
Resist the temptation to use commas or dots as thousand-separators. Seeing a number with a dot as a decimal separator instead of a comma will be fine for most people (even if proper localisation would mean using a comma), but if you throw in commas that mean something else you WILL confuse people. And I imagine the inverse is also true.
I personally don't like it though, and tend to prefer either the swiss system (ie, 3'800'000.0), or maritime system (ie 3_800_000.0) if separators must be used
If round tripping is important, my recommendation would be to output something that directly corresponds to the binary representation of the float. For example, printf %a
These algorithms (Grisu, Ryu, ...) all satisfy the "internal identity requirement", which means that they can print a double and read it back in to the same double.
The harder part is to also produce the shortest of all possible string-representations. (And then picking the closest if there are many).
When considering the correctness of a floating point decimal printing algorithm, you could use "round trips with Y parsing algorithm", but that's flawed -- it ties the printing algorithm directly to a particular parsing algorithm.
Instead what is usually considered is "what is the closest representable floating point value to the real value output by the printing algorithm?" If the printing algorithm outputs a string representation which is closer to the input float than it is to any other float, then it's correct. It's up to each parsing algorithm to provide the reverse condition -- that it parses each string to the float which is closest to the real value of the represented string.
Modern float-print algorithms like Grisu / Dragon / etc. also add the additional restriction that they output the shortest possible string that meets that condition; for example, the real number 0.69999998 is closer to the 32-bit float (0b1.011_0011_0011_0011_0011_0011 * 2^-1, represented in memory as 0x3f333333) than any other float. The real number 0.7 is slightly further from that float, but it's still closer to it than any other float, and is much shorter -- those algorithms should print that float as "0.7".
A correct parser should parse both the string "0.7" and "0.69999998" to the same 32-bit float result.