Back in 2007-ish I spent a bunch of time trying to figure out how to print floating point numbers losslessly. Annoyingly, there's no printf() format string that says "print exactly as many digits as needed so that it parses back to the same value". You can specify a number of digits to use, but to avoid printing unnecessary digits in all cases (e.g. "0.20000000000000001" for 0.2) you must ask for a maximum of 15 digits, but in some cases you will lose data if you ask for fewer than 17 digits.
After asking around, I came across the Steele & White paper, and the implementation known as `dtoa()` written by David M. Gay. At the time, this seemed to be understood to be the "correct" answer.
There's a lot to dislike about that code, but arguably the worst thing is that it isn't thread-agnostic. It mutates global variables and protects them with a global mutex. A global mutex lock, just to print a number! Whyyyyyyyy?
So then I tried something different: I wrote some code that would do sprintf() with 15 digits precision first, then parse it with strtod() to see if it came back exact. If not... then I did sprintf() with 17 digits precision... and called it a day.
In benchmarks, this turned out to be just as fast as calling dtoa().
And so that's how the Protocol Buffers library deals with numbers when writing TextFormat:
But the bigger lesson for me was: Transmitting floating-point numbers in text is awful. People have no idea how ridiculously complex this is, because it seems like it ought to be simple. When you send JSON with numbers in it, you are probably invoking code that looks something like dtoa(), over and over and over again. And that's just to write them out; I have no idea how complex the parsing side is.
Please, folks, think of the CPU cycles. When sending numeric data, use a binary format.
People often forget about the numeric locale with floating point as text. Long ago, we had European collaborations, e.g. with Anglophone at one end of the network, Francophone or Danish at the other, sometimes "with hilarious consequences". I know %g etc. in C's printf isn't subject to that, but it was a real issue at the time.
Binary representations of floating point number are a bit of a nest of vipers too, though. You can probably just pipe IEEE floats across the network as bytes, in practice, but it's risky.
It's probably safer in many cases to just transmit things in fixed point.
The parent didn't say "don't have any float". I have had to translate between little endian IEEE754 and big endian IBM format, roughly copying what HDF did. Protein crystallographers invented their own binary file format rather than just using HDF, and didn't define the binary floating point format, so that the files weren't portable initially.
I was mainly thinking of byte order issues and handling of NaN / infinities (especially if, say, you're sending a value from one computer with FPU exceptions disabled to another one with exceptions enabled), but I seem to recall reading about other subtle implementation differences which tended to mean that floats aren't always portable between different CPUs even if they're ostensibly all IEEE compliant.
Almost everything uses IEEE-754. For those that don't, converting IEEE-754 to the local native format is almost certainly much easier than parsing text. Dealing with NaN-related issues is also only a couple instructions; much easier than parsing text. (Ideally, use a serialization library that already does these things.)
It's too long ago to remember details, though the code may still be in use, but I remember the binary conversion being hairy and ill-defined (754 not mapping onto IBM/VAX), maybe even dependent on the FPU settings. Not that textual conversion would be well-defined either, of course.
754 has won, as has little endian. Even PowerPC has switched. There are IBM mainframes still being made but even they are now bi-endian because they know they've lost the war.
Unfortunately, that format will print 0.2 as "0.20000000000000001". What we want is the shortest-length string that will parse back to the same original value, which is "0.2".
We were able to update the paper on the ACM website: https://dl.acm.org/citation.cfm?id=2837654, although looking at it now, they did not update the title. I'll see if they can fix that.
There is very exciting news coming up with printing floating point. Ulf Adams from Google will be presenting a new algorithm called Ryu that appears to be super fast, simple, and perfectly accurate. Assuming the claims are correct, Ryu ought displace all of the current algorithms.
Thanks! My comment was not meant as a criticism of your work (I still like the paper, and do appreciate that you went to the effort of putting the amended results online), but more of the CS conference publishing model.
I've been looking at key-value stores recently, and I wonder what people think about collating numbers of heterogeneous types.
FoundationDB tuples have type codes that segregate values of different types, so that the strings "1" and "2" sort before the integers 1 and 2, which sort before the single-precision floats 1.0f and 2.0f, which sort before the double-precision floats 1.0 and 2.0.
The database that I test supports double-precision IEEE floats, and a proprietary decimal float with a signed 64-bit significand and signed 8-bit exponent. When converted to string for use as keys, these collate as expected. The price of this is that you don't get shortest representations of the sort sought by this paper and others. Otherwise, a binary and decimal float that compare unequal could convert to the same string.
I guess it's kind of unusual to use floats as keys, and more unusual still to use both binary and decimal floats, but I wonder if there is another strategy for collating them.
That's the paper referenced in this one, which more people may have seen, also about correctly converting floats to strings and vice-versa: https://www.ampl.com/REFS/rounding.pdf
After asking around, I came across the Steele & White paper, and the implementation known as `dtoa()` written by David M. Gay. At the time, this seemed to be understood to be the "correct" answer.
But then I looked at the code: http://www.netlib.org/fp/dtoa.c
Uh.
There's a lot to dislike about that code, but arguably the worst thing is that it isn't thread-agnostic. It mutates global variables and protects them with a global mutex. A global mutex lock, just to print a number! Whyyyyyyyy?
So then I tried something different: I wrote some code that would do sprintf() with 15 digits precision first, then parse it with strtod() to see if it came back exact. If not... then I did sprintf() with 17 digits precision... and called it a day.
In benchmarks, this turned out to be just as fast as calling dtoa().
And so that's how the Protocol Buffers library deals with numbers when writing TextFormat:
https://github.com/google/protobuf/blob/ed4321d1cb3319998411...
But the bigger lesson for me was: Transmitting floating-point numbers in text is awful. People have no idea how ridiculously complex this is, because it seems like it ought to be simple. When you send JSON with numbers in it, you are probably invoking code that looks something like dtoa(), over and over and over again. And that's just to write them out; I have no idea how complex the parsing side is.
Please, folks, think of the CPU cycles. When sending numeric data, use a binary format.