5 ms·

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

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 https://github.com/google/double-conversion) is probably still the go-to library if you don't want to implement it again...

shereadsthenews 7y ago
What about libfmt? Frankly I find it a little easier to use than double-conversion and it's equal in speed.
- floitsch 7y ago
  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.
  - shereadsthenews 7y ago
    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"
    - dunham 7y ago
      In emacs, Meta-/ might help. :) > Expands to the most recent, preceding word for which this is a prefix.
  - TazeTSchnitzel 7y ago
    libfmt's implementation of Grisu is what the original post (Formatting Floating Point Numbers) concerns, no?
bumblebritches5 7y ago
Ryu is better than your code. Why are you still peddling this bad algorithm?
haberman 7y ago
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?
- floitsch 7y ago
  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.
ducktypegoose 7y ago
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.
beached_whale 7y ago
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
acqq 7y ago
For those who are interested in the paper: https://dl.acm.org/citation.cfm?id=3192369 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."

shereadsthenews 7y ago

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

floitsch 7y ago
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.
- shereadsthenews 7y ago
  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"
  - dunham 7y ago
    In emacs, Meta-/ might help. :) > Expands to the most recent, preceding word for which this is a prefix.
- TazeTSchnitzel 7y ago
  libfmt's implementation of Grisu is what the original post (Formatting Floating Point Numbers) concerns, no?

bumblebritches5 7y ago

Ryu is better than your code. Why are you still peddling this bad algorithm?

haberman 7y ago

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?

floitsch 7y ago
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.

ducktypegoose 7y ago

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.

beached_whale 7y ago

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

acqq 7y ago

For those who are interested in the paper: https://dl.acm.org/citation.cfm?id=3192369 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."