3 ms·

What do you make of this algorithm which claims to be faster than the Ryu algorithm [0]? I think this is the implementation in C++ [1]. The author also worked o

What do you make of this algorithm which claims to be faster than the Ryu algorithm [0]? I think this is the implementation in C++ [1]. The author also worked on an algorithm for half-precision conversions. [2] [0] http://www.fox-toolkit.org/ http://www.fox-toolkit.org/ New, faster, and often more accurate floating point to string conversion. No, this is not based on Ryu paper. New method reliably generates 16 digits, and does much better rounding. [1] https://github.com/gogglesguy/fox/blob/77396c6/lib/fxprintf.cpp#L381 https://github.com/gogglesguy/fox/blob/77396c6/lib/fxprintf.... [2] [PDF] http://www.fox-toolkit.org/ftp/fasthalffloatconversion.pdf http://www.fox-toolkit.org/ftp/fasthalffloatconversion.pdf

SloopJon 6y ago
If I understand correctly, it's a printf-style function for which the %g format code outputs the shortest decimal string that round trips. This implies that it would output no more than seventeen significant figures, regardless of the requested precision. The first thing I notice is this comment in a later changelog: > I believe we have a very fast numerical conversion that appears to be reliably generating about 15 to 16 digits out output [last digit may be off by 1 or 2 in typical case]. If the last digit of a fifteen- to sixteen-digit output is off by one or two, are we sure it round trips? Second, the test coverage for this feature in tests/format.cpp looks pretty sparse, and it's not obvious to me how the output is verified. Interesting find. I may play around with this later. Edit: I tried the test cases from here: https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-examples/ https://www.exploringbinary.com/the-shortest-decimal-string-... Here's the result: format="%.30g" output="0.1" format="%.30g" output="50388143.06823721984" format="%.30g" output="54167628.18" format="%.30g" output="9161196241250.051072" The first and third cases output the correct string. The second case outputs nineteen digits, instead of seventeen, and does not round trip (i.e., it rounded incorrectly). The last case outputs nineteen digits instead of fifteen, but does round trip.
- MaxBarraclough 6y ago
  Nice work, thanks for looking into it.
jcranmer 6y ago
Looking at the code briefly, it doesn't seem like it's actually an accurate conversion. The core of the conversion algorithm appears to be based on doing a series of floating-point multiplies, which of course will tend to trash the last few bits. Using volatile to try to avoid reassociation here. But there's no comments indicating why the rounding is going to be correct in the range provided, and my gut is that it's not going to be correct. (Especially since the double-to-int conversion is truncating, and I'd naïvely expect half the rounding error to round down, which means the last digit is off by one).

SloopJon 6y ago

If I understand correctly, it's a printf-style function for which the %g format code outputs the shortest decimal string that round trips. This implies that it would output no more than seventeen significant figures, regardless of the requested precision. The first thing I notice is this comment in a later changelog: > I believe we have a very fast numerical conversion that appears to be reliably generating about 15 to 16 digits out output [last digit may be off by 1 or 2 in typical case]. If the last digit of a fifteen- to sixteen-digit output is off by one or two, are we sure it round trips? Second, the test coverage for this feature in tests/format.cpp looks pretty sparse, and it's not obvious to me how the output is verified. Interesting find. I may play around with this later. Edit: I tried the test cases from here: https://www.exploringbinary.com/the-shortest-decimal-string-that-round-trips-examples/ https://www.exploringbinary.com/the-shortest-decimal-string-... Here's the result: format="%.30g" output="0.1" format="%.30g" output="50388143.06823721984" format="%.30g" output="54167628.18" format="%.30g" output="9161196241250.051072" The first and third cases output the correct string. The second case outputs nineteen digits, instead of seventeen, and does not round trip (i.e., it rounded incorrectly). The last case outputs nineteen digits instead of fifteen, but does round trip.

MaxBarraclough 6y ago
Nice work, thanks for looking into it.

jcranmer 6y ago

Looking at the code briefly, it doesn't seem like it's actually an accurate conversion. The core of the conversion algorithm appears to be based on doing a series of floating-point multiplies, which of course will tend to trash the last few bits. Using volatile to try to avoid reassociation here. But there's no comments indicating why the rounding is going to be correct in the range provided, and my gut is that it's not going to be correct. (Especially since the double-to-int conversion is truncating, and I'd naïvely expect half the rounding error to round down, which means the last digit is off by one).