Gargi SharmaI am a software engineer who contributes to OCaml open source at Tarides. Previously, I worked at Bloomberg, Uber, and eBay. I also attended the Recurse Center.
In my talk, I'm explaining the problem behind printing floats. See the notes for my talk below.
Section 1
What happens when you print 0.3 + 0.03 in python REPL?
- The output is 0.32999999999999996. The problem could either lie with the floating point arithmetic or with the printing of the floating point number.
- Printing phase converts the binary representation of a floating point number to human readable decimal representation with as few digits as possible to convey the result.
Section 2
- The problem is that not all decimal point number can be accurately represented with binary format.
- Example of converting floating point to binary and back, every binary number has an exact decimal equivalent but not every decimal number has a binary equivalent.
-----------------------------------------------------
| signed bit | exponent | mantissa |
-----------------------------------------------------
- The “wrong” output 0.32999999999999996 and the “right” output 0.33 both fall in the same interval.
- Since there isn’t an exact representation for 0.3 in binary, the algorithm now has to decide how to round up this number, and how many digits to slice off to get an accurate representation.
How did the first algorithm to solve this address the problems?
Dragon4 algorithm for printing floating point numbers from 1990
- Illustrate the algorithm with a visual example, the core principles this algorithm is based on are:
- Information preservation - when you print a number and parse it again, you should be able to get the same number
- Print the shortest number while maintaining the first criteria
- Correctly rounded
- Illustrate the above criterion of the algorithm with an example.
- Drawbacks of Dragon4 - arbitrary precision arithmetic is slow (because it has to implemented in software rather than hardware)
What’s new in the land of dragons?
Grisu (2010)
- The next jump in the printing floats space came in 2010 (20 years after the first paper was published!!)
- One of the big drawbacks of Dragon4 was using arbitrary precision numbers, but Grisu uses machine integers. Grisu is only accurate 99.4% of the times and has to fall back to Dragon4 for the rest of 0.6% cases.
- Explain Grisu with the same example as before.
- Grisu is used in both V8 and Mozilla Javascript engines and is 5 times faster than Dragon4
- Show benchmarks of Grisu vs Dragon4
Ryū (2018)
- Improving on Grisu, doesn’t need to fallback on Dragon4 (Is a complete algorithm)
- Same example as before, a run through with Ryū
- Show benchmarks of Dragon4 vs Grisu vs Ryū
Slides:
Bibliography:
http://kurtstephens.com/files/p372-steele.pdf
https://github.com/dtolnay/ryu
https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf
https://cseweb.ucsd.edu/~lerner/papers/fp-printing-popl16.pdf
Here is a download link to the talk slides (PDF)
This talk will be presented as part of CodeLand:Distributed on July 23. After the talk is streamed as part of the conference, it will be added to this post as a recorded video.
