Hacker News Reader

Comment by floitsch | Hacker News Reader

Author of Grisu here.

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...

View on HN

I just wanted to say I appreciate the imagery preceeding you paper, as I think it captures the struggle of FPP conversion perfectly. As my office's unofficial, "FPP expert" I sympathize the struggle. You've done an excellent job crafting a paper that not only captures your work, but you've managed to articulate the FPP problem so accessibly. Anybody that cares to consider your paper can gain insight into the true nature of the dragon.

For those who are interested in the paper:

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."

My understanding is that fixed-length conversion to string is more or less trivial, the tricky part is writing a fast algorithm to compute the shortest round-trippable conversion to string, correct?

Depends.

"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.

What about libfmt? Frankly I find it a little easier to use than double-conversion and it's equal in speed.

Looks like a great library. Not sure I actually knew about it. I will probably update the double-conversion library README to add a link.

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.

libdouble-conversion is indeed far more flexible. I think that's what leads to all the extra typing! I mean, just including it is almost more typing than I'm willing to undertake ;-)

  #include "third_party/double-conversion/double-conversion/double-conversion.h"

In emacs, Meta-/ might help. :)

> Expands to the most recent, preceding word for which this is a prefix.

libfmt's implementation of Grisu is what the original post (Formatting Floating Point Numbers) concerns, no?

MSVC has the std charconv stuff for this, and the other implementors should soon enough too. That means sooner or later all C++ compilers will probably have Ryu soon

Reply on news.ycombinator.com