Printing floating point numbers with Gargi Sharma

I 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.

Comments

[Ben Halpern]

There is so much I really don't understand about this subject. Already learning some stuff in the first couple mins 😄

[Abhishek Sharma]

My favorite demo on importance of machine epsilon:

~
def f(x):
if x <= 1/2:
return 2 * x
if x > 1/2:
return 2*x - 1

x = 1/10
for i in range(80):
print(x)
x = f(x)
~

[Paula]

This is so interesting, so cool to better understand how maths work under the higher programming levels we are used to work with! thank you to take the time to explain to us! loving it

[Dangeranger]

Fun fact, there are more numbers between 0 and 1, than there are integers above 0.

[Omar]

Thanks , Every computer scientist out there including me will be happy to watch this!

[Andy Zhao (he/him)]

I wonder why they're all dragon related haha

[Gargi Sharma]

I think it's a tribute to the first algorithm! The first one was called Dragon4 because of the Dragon curve and the folds & peaks in the making of a dragon curve and others followed tradition. :)

[Andy Zhao (he/him)]

Ahh that makes sense! Interesting!

[Linda Thompson]

Good job! I never really thought about computers doing floating point math based in binary instead of decimal.....no wonder it always works so weird!!

[Terri Fricker]

So excited. I've just run into this and I was so confused!

[SpicyC]

Love the folded paper representation of dragon f, p, f, p.... makes logical sense - Thank you :)

[SpicyC]

Technical Support Question: Every time I select 'checkin' in takes me to purchase ticket page and says I already have a ticket....??

[Nicole Hopkins]

I haven't figured out how to check in either!