5 ms·

Rendering floating numbers: advances in problems you didn’t know you had (2011)

76 points by pcr910303 6y ago

jrumbut 6y ago
This is in the running for the best HN post I've seen this year. I've read all about floating point precision, never about rendering. The existence of this problem is so obvious in hindsight and I was so completely unaware of it previously.
- SloopJon 6y ago
  I think Python was the first to bring this into my consciousness. See this enhancement request, which changed the float-to-string conversion from seventeen significant figures to shortest: https://bugs.python.org/issue1580 https://bugs.python.org/issue1580 After they did that, I learned that Scheme specifies similar behavior. In fact, I think it was added to R4RS after the Steele and White paper. As the article says, this behavior spread across languages, so that it's weird to see something different now. If you want to nerd out on this, here are a few other posts that explore the topic: https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-examples/ https://www.exploringbinary.com/the-shortest-decimal-string-... https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-may-not-be-the-nearest/ https://www.exploringbinary.com/the-shortest-decimal-string-... https://www.exploringbinary.com/java-doesnt-print-the-shortest-strings-that-round-trip/ https://www.exploringbinary.com/java-doesnt-print-the-shorte...
jcranmer 6y ago
This needs a 2011 on it, which will explain why it is missing the very recent Ryū algorithm, which I believe is the fastest algorithm at this point: https://dl.acm.org/doi/10.1145/3192366.3192369 https://dl.acm.org/doi/10.1145/3192366.3192369 (PLDI 2018 paper) https://github.com/ulfjack/ryu https://github.com/ulfjack/ryu (C source code)
- est31 6y ago
  Apparently Ryu is slower on shorter numbers than the Rust standard library's implementation which uses Grisu/Dragon. It might be only due to the implementation though. https://www.reddit.com/r/rust/comments/93d045/fast_floattostring_conversion_ryu_for_rust/e3d24f4/ https://www.reddit.com/r/rust/comments/93d045/fast_floattost... Also it seems that Ryu prints some numbers in weird ways even though "nicer" representations exist: https://github.com/rust-lang/rust/issues/52811#issuecomment-408644826 https://github.com/rust-lang/rust/issues/52811#issuecomment-...
  - StephanTLavavej 6y ago
    That “weirdness” is just scientific notation, which the Ryu implementation always emits. It is “superficial” in the sense that it’s separate from the core algorithm. When I adapted it for C++17 charconv in MSVC, I implemented fixed, general, and “plain shortest” notation, which will print 0.3 there. (General notation follows C printf %g’s rules for switching between fixed and scientific; “plain shortest” notation selects the one that’s fewer characters, tiebreaking to prefer fixed).
  - zX41ZdbW 6y ago
    In ClickHouse* we patched Ryu to provide nicer representations and to have better performance for floats that appear to be integers. * https://github.com/ClickHouse/ClickHouse/pull/8542 https://github.com/ClickHouse/ClickHouse/pull/8542
  - zX41ZdbW 6y ago
    The change to Ryu is here: https://github.com/ClickHouse-Extras/ryu/pull/1 https://github.com/ClickHouse-Extras/ryu/pull/1
- ygra 6y ago
  Stephan T Lavavej also had a surprisingly fun and approachable talk on that problem, talking about how charconv got implemented and improved in Microsoft's C++ standard library: https://youtu.be/4P_kbF0EbZM https://youtu.be/4P_kbF0EbZM
- 6y ago
deleted 6y ago
[deleted]
ashton314 6y ago
This is the kind of stuff that’s got me hooked on CS: small problems that no one thinks about much but have dramatic impact on developers’ lives and the things they build. There’s a lot of societal problems that we’ve inadvertently created, (see Technopoly by Postman or The Social Dilemma on Netflix) but it’s nice to be reminded about what makes this field fun and worthwhile.
zozbot234 6y ago
Unless you actually need to output human-readable numbers for some reason, the sensible approach when serializing floating point numbers is to just use hexfloats and skip the problematic "rendering" part altogether.
- adrian_b 6y ago
  I completely agree
- benibela 6y ago
  That is great, until you have to use JSON
  - rixed 6y ago
    It could be argued that if so many people have to use json to serialize floats then our problem is not a technical one.
spirographer 6y ago
Here is the reference for the most recent work (2019) of note in this domain. Ulf Adams extended his 2018 Ryū algorithm to implement Ryū printf which is 4x faster than the best other implementation tested on Linux, Mac and Windows. https://dl.acm.org/doi/pdf/10.1145/3360595 https://dl.acm.org/doi/pdf/10.1145/3360595
benibela 6y ago
I have to deal with this all the time. Unfortunately I wrote my programs in FreePascal, because Pascal was supposed to be the best, fastest, and safest language, but it is very bad at solving these kinds of problems. I wrote my own rendering function. It was not so hard. I just wrote functions to calculate with arbitrary precision decimal numbers and then put the float in there. Reallly slow, but perfectly accurate unlike those in FreePascal. Now FreePascal has implemented Grisu3, so it is fine to use their functions. Although it is printing weird numbers like 1.0000000000000001E-1 for 0.1. With my arbitrary precision calculation, I get 0.1 is exactly 0.1000000000000000055511151231257827021181583404541015625 and can round it to the shortest representation 0.1. But the reverse problem -- parsing floating numbers -- is also really hard. And I cannot just bruteforce it by printing arbitrary precision binary floats. FreePascal's parsing function still rounds wrongly ( https://bugs.freepascal.org/view.php?id=29531 https://bugs.freepascal.org/view.php?id=29531 ), so it is risky to use For fast parsing of 99% cases, the Eisel-Lemire algorithm can be used. Unfortunately, there is no FreePascal implementation. I hope someone will port it FreePascal, so I do not have to do it. And then it still leaves the hard 1% of cases. How do you parse them? Is there a simple way to do it with some arbitrary precision calculations?
im3w1l 6y ago
Mojibake? Now that's something I haven't seen in a while. (In the post script)

76 points by pcr910303 6y ago

This is in the running for the best HN post I've seen this year. I've read all about floating point precision, never about rendering. The existence of this problem is so obvious in hindsight and I was so completely unaware of it previously.

SloopJon 6y ago
I think Python was the first to bring this into my consciousness. See this enhancement request, which changed the float-to-string conversion from seventeen significant figures to shortest: https://bugs.python.org/issue1580 https://bugs.python.org/issue1580 After they did that, I learned that Scheme specifies similar behavior. In fact, I think it was added to R4RS after the Steele and White paper. As the article says, this behavior spread across languages, so that it's weird to see something different now. If you want to nerd out on this, here are a few other posts that explore the topic: https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-examples/ https://www.exploringbinary.com/the-shortest-decimal-string-... https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-may-not-be-the-nearest/ https://www.exploringbinary.com/the-shortest-decimal-string-... https://www.exploringbinary.com/java-doesnt-print-the-shortest-strings-that-round-trip/ https://www.exploringbinary.com/java-doesnt-print-the-shorte...

jcranmer 6y ago

This needs a 2011 on it, which will explain why it is missing the very recent Ryū algorithm, which I believe is the fastest algorithm at this point: https://dl.acm.org/doi/10.1145/3192366.3192369 https://dl.acm.org/doi/10.1145/3192366.3192369 (PLDI 2018 paper) https://github.com/ulfjack/ryu https://github.com/ulfjack/ryu (C source code)

est31 6y ago
Apparently Ryu is slower on shorter numbers than the Rust standard library's implementation which uses Grisu/Dragon. It might be only due to the implementation though. https://www.reddit.com/r/rust/comments/93d045/fast_floattostring_conversion_ryu_for_rust/e3d24f4/ https://www.reddit.com/r/rust/comments/93d045/fast_floattost... Also it seems that Ryu prints some numbers in weird ways even though "nicer" representations exist: https://github.com/rust-lang/rust/issues/52811#issuecomment-408644826 https://github.com/rust-lang/rust/issues/52811#issuecomment-...
- StephanTLavavej 6y ago
  That “weirdness” is just scientific notation, which the Ryu implementation always emits. It is “superficial” in the sense that it’s separate from the core algorithm. When I adapted it for C++17 charconv in MSVC, I implemented fixed, general, and “plain shortest” notation, which will print 0.3 there. (General notation follows C printf %g’s rules for switching between fixed and scientific; “plain shortest” notation selects the one that’s fewer characters, tiebreaking to prefer fixed).
- zX41ZdbW 6y ago
  In ClickHouse* we patched Ryu to provide nicer representations and to have better performance for floats that appear to be integers. * https://github.com/ClickHouse/ClickHouse/pull/8542 https://github.com/ClickHouse/ClickHouse/pull/8542
- zX41ZdbW 6y ago
  The change to Ryu is here: https://github.com/ClickHouse-Extras/ryu/pull/1 https://github.com/ClickHouse-Extras/ryu/pull/1
ygra 6y ago
Stephan T Lavavej also had a surprisingly fun and approachable talk on that problem, talking about how charconv got implemented and improved in Microsoft's C++ standard library: https://youtu.be/4P_kbF0EbZM https://youtu.be/4P_kbF0EbZM
6y ago

deleted 6y ago

[deleted]

ashton314 6y ago

This is the kind of stuff that’s got me hooked on CS: small problems that no one thinks about much but have dramatic impact on developers’ lives and the things they build. There’s a lot of societal problems that we’ve inadvertently created, (see Technopoly by Postman or The Social Dilemma on Netflix) but it’s nice to be reminded about what makes this field fun and worthwhile.

zozbot234 6y ago

Unless you actually need to output human-readable numbers for some reason, the sensible approach when serializing floating point numbers is to just use hexfloats and skip the problematic "rendering" part altogether.

adrian_b 6y ago
I completely agree
benibela 6y ago
That is great, until you have to use JSON
- rixed 6y ago
  It could be argued that if so many people have to use json to serialize floats then our problem is not a technical one.

spirographer 6y ago

Here is the reference for the most recent work (2019) of note in this domain. Ulf Adams extended his 2018 Ryū algorithm to implement Ryū printf which is 4x faster than the best other implementation tested on Linux, Mac and Windows. https://dl.acm.org/doi/pdf/10.1145/3360595 https://dl.acm.org/doi/pdf/10.1145/3360595

benibela 6y ago

I have to deal with this all the time. Unfortunately I wrote my programs in FreePascal, because Pascal was supposed to be the best, fastest, and safest language, but it is very bad at solving these kinds of problems. I wrote my own rendering function. It was not so hard. I just wrote functions to calculate with arbitrary precision decimal numbers and then put the float in there. Reallly slow, but perfectly accurate unlike those in FreePascal. Now FreePascal has implemented Grisu3, so it is fine to use their functions. Although it is printing weird numbers like 1.0000000000000001E-1 for 0.1. With my arbitrary precision calculation, I get 0.1 is exactly 0.1000000000000000055511151231257827021181583404541015625 and can round it to the shortest representation 0.1. But the reverse problem -- parsing floating numbers -- is also really hard. And I cannot just bruteforce it by printing arbitrary precision binary floats. FreePascal's parsing function still rounds wrongly ( https://bugs.freepascal.org/view.php?id=29531 https://bugs.freepascal.org/view.php?id=29531 ), so it is risky to use For fast parsing of 99% cases, the Eisel-Lemire algorithm can be used. Unfortunately, there is no FreePascal implementation. I hope someone will port it FreePascal, so I do not have to do it. And then it still leaves the hard 1% of cases. How do you parse them? Is there a simple way to do it with some arbitrary precision calculations?

im3w1l 6y ago

Mojibake? Now that's something I haven't seen in a while. (In the post script)