4 ms·

Some context: http://www.serpentine.com/blog/2011/06/29/here-be-dragons-advances-in-problems-you-didnt-even-know-you-had/ http://www.serpentine.com/blog/2011/06

Some context: http://www.serpentine.com/blog/2011/06/29/here-be-dragons-advances-in-problems-you-didnt-even-know-you-had/ http://www.serpentine.com/blog/2011/06/29/here-be-dragons-ad... It probably marks the end of the quest to find the unconditionally correct and fast algorithm to print floating point numbers. The prior state of the art, Grisu3 (2010), is great but is only fast for 99.5% of inputs; it was nevertheless so useful that there are now several language implementations with Grisu3 (IIRC, including V8, SpiderMonkey, Go, Julia and Rust). The new algorithm, Errol3, improves Grisu3 by using double-double floating point format (instead of 64-bit custom FP) and applying more precise error analysis. Quoting the highlight of the paper: (emphases original) > After removing the narrowing and widening steps, we used the enumeration algorithm to generate a list of possibly incorrect or suboptimal inputs. Each input was run using Errol2 to enumerate a complete list of inputs that do not generate correct and optimal outputs. In total, we found that only 45 inputs (of the nearly 2^64 inputs) generate incorrect or suboptimal results; all other inputs are guaranteed to generete correct and optimal output. In order to correctly and optimally handle the failing inputs, they are hard-coded into a lookup table that maps the failing inputs to correct and optimal outputs. Combining the special handling of integers and this lookup table, Errol3 is guaranteed to be correct and optimal without runtime checks.

userbinator 11y ago
In order to correctly and optimally handle the failing inputs, they are hard-coded into a lookup table that maps the failing inputs to correct and optimal outputs. That makes one wonder, what's so special about these 45 values? I think it would be far closer to "the end of the quest" if that could be determined, and those could also be handled by the rest of the algorithm somehow.
- lifthrasiir 11y ago
  IIRC both Grisu and Errol has a fairly specific class of pathological inputs, referred as to pathological midpoints in the paper. I have implemented Grisu3 myself so I would use that as an example. (I don't know if this example is also problematic in Errol1.) 10^23 is not exactly representable in IEEE 754 binary64 format (aka double). 10^23 - 3 * 2^23, 10^23 - 2^23 and 10^23 + 2^23 are exactly representable however, so any number from 10^23 - 2 * 2^24 to 10^23 (inclusive, because IEEE 754 has a specific rounding mode here) is round to 10^23 - 2^23. Clearly the shortest correct output in the range would be 10^23, but 10^23 is the midpoint between two FP values! Both Grisu and Errol use a fixed size mantissa (64 bits and 106 bits respectively) and have a conservative error margin as a result, and that margin would always contain such midpoints. Errol uses more precise error analysis to show that pathological midpoints are always integral and in the specific range. Since the specific range is <= 2^131, it simply tries to calculate the midpoint as a 128-bit integer and works around the conservative error margin. This removes a major source of pathological inputs, but the conservative error margin still exists and numbers may still fall in that hole. The final enumeration shows that there are only 45 such numbers.
- marcandrysco 11y ago
  Author here. The simplest way to describe those 42 values: the value we want to output (the shortest value) is very close to the midpoint between two floating-point values. Since the best answer so close to a midpoint, its difficult for the algorithm to decide which direction that number will round. So, how can we make sure that such numbers are converted correctly? The answer from Steel & White's paper is to perform arbitrary integer arithmetic and leave nothing up to chance. The Grisu3 algorithm by Loitsch showed that 64-bits correct converts about 99.5% of numbers. As you increase the amount of precision, you can improve your accuracy, but there is no guarantee that even 128-bits or 256-bits is enough to correctly convert all numbers. Instead of trying to be 100% correct, our algorithm sidesteps the issue entirely by enumerating all failures a priori.

userbinator 11y ago

In order to correctly and optimally handle the failing inputs, they are hard-coded into a lookup table that maps the failing inputs to correct and optimal outputs. That makes one wonder, what's so special about these 45 values? I think it would be far closer to "the end of the quest" if that could be determined, and those could also be handled by the rest of the algorithm somehow.

lifthrasiir 11y ago
IIRC both Grisu and Errol has a fairly specific class of pathological inputs, referred as to pathological midpoints in the paper. I have implemented Grisu3 myself so I would use that as an example. (I don't know if this example is also problematic in Errol1.) 10^23 is not exactly representable in IEEE 754 binary64 format (aka double). 10^23 - 3 * 2^23, 10^23 - 2^23 and 10^23 + 2^23 are exactly representable however, so any number from 10^23 - 2 * 2^24 to 10^23 (inclusive, because IEEE 754 has a specific rounding mode here) is round to 10^23 - 2^23. Clearly the shortest correct output in the range would be 10^23, but 10^23 is the midpoint between two FP values! Both Grisu and Errol use a fixed size mantissa (64 bits and 106 bits respectively) and have a conservative error margin as a result, and that margin would always contain such midpoints. Errol uses more precise error analysis to show that pathological midpoints are always integral and in the specific range. Since the specific range is <= 2^131, it simply tries to calculate the midpoint as a 128-bit integer and works around the conservative error margin. This removes a major source of pathological inputs, but the conservative error margin still exists and numbers may still fall in that hole. The final enumeration shows that there are only 45 such numbers.
marcandrysco 11y ago
Author here. The simplest way to describe those 42 values: the value we want to output (the shortest value) is very close to the midpoint between two floating-point values. Since the best answer so close to a midpoint, its difficult for the algorithm to decide which direction that number will round. So, how can we make sure that such numbers are converted correctly? The answer from Steel & White's paper is to perform arbitrary integer arithmetic and leave nothing up to chance. The Grisu3 algorithm by Loitsch showed that 64-bits correct converts about 99.5% of numbers. As you increase the amount of precision, you can improve your accuracy, but there is no guarantee that even 128-bits or 256-bits is enough to correctly convert all numbers. Instead of trying to be 100% correct, our algorithm sidesteps the issue entirely by enumerating all failures a priori.