Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

A Problem So Simple That It Took Decades To Solve

March 13, 2014

Last week's article was the last in a series discussing the problems of floating-point input and output conversion, leading up to a seemingly simple question: What is the ideal default precision for floating-point output? This question does not arise for floating-point input because we know the precision of both the input that the user provided and the variable in which the input is to be put. With output, however, we know only the variable's precision; we do not know how many decimal digits should represent that variable.

We have already established that idempotence is important. That is, when we convert a floating-point value to decimal with enough precision, and we read that converted value in again, we should get exactly the same bits. It is even easy for us to figure out how many digits will preserve the number's value exactly, namely the same number of digits after the decimal point as the number of bits that the original number had after its binary point. But here is where the easy part of the problem ends.

We saw last week that on a typical computer, converting 0.1 to double-precision floating-point and then back to decimal yields exactly 0.09999999999999997779553950749686919152736663818359375. It is hard to understand why it is useful to print all of those digits.

In many C and C++ implementations, the default output precision is six significant digits. On such an implementation, printing 0.1 yields 0.1, which is both convenient and idempotent — in this case. However, printing (1.0/3.0) yields 0.333333, which most definitely destroys idempotence. As I mentioned last week, Jerome Coonen proved that it is always possible to preserve idempotence by printing enough digits to keep the difference between what is printed and the exact value of the number within 0.47 times the least significant bit — but it is not always easy to figure out exactly how many digits that would be.

In early 1971, Jon White started analyzing this problem. This analysis began a 20-year odyssey, which he and Guy Steele described in detail in a fascinating, albeit complicated, paper. Although the paper itself is complicated, and the path to its results is even more so, the paper's conclusion seems so simple as to be flagrantly obvious:

Convert floating-point numbers to decimal with the fewest digits needed to preserve idempotence.

This strategy has several wonderful properties.

First, if you print the value of a short literal, you will get that same literal as output. For example, on such an implementation,

 
std::cout << 0.1 << std::endl;

will print 0.1. We know this because the literal 0.1 gets converted to a particular floating-point value, and therefore printing that value as 0.1 guarantees idempotence. More generally, printing any floating-point literal will yield exactly the same value unless that literal has so much precision that it is not the only one to yield that particular floating-point number. For example, if we were to print the literal 0.10000000000000000000000001, we could reasonably expect that this literal would be converted on input to the same floating-point value as would result from reading 0.1, so we should not be surprised to see that value converted to 0.1 on output.

Second, when a printed value appears with many digits, we can be confident that all of those digits are needed to characterize that particular value — they're not just amplified noise. Of course, we do not know how meaningful the value itself is — garbage in, garbage out — but we know that removing even a single digit from that output value would change the corresponding floating-point value to something else.

Finally, idempotence itself is a useful property, because it means that we can store floating-point values in human-readable form without worrying that doing so might erode those values.

In short, through a laborious process, we have come up with two simple rules for floating-point input and output conversions:

Convert decimal numbers to floating-point by yielding the decimal value as an exact number
 and rounding it to the required floating-point precision.
 Convert floating-point numbers to decimal by producing as few digits as possible while preserving idempotence.

Moreover, reasonably efficient implementations exist that follow these two rules. Therefore, it would seem that by now every C and C++ implementation should follow these rules.

Next week, we'll start exploring the social processes that explain why this hasn't happened yet.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video