TIP #132 Version 1.6: Revised Floating-Point Conversions in Tcl

This is not necessarily the current version of this TIP.

Abstract

This TIP proposes several changes to the conversion between floating point numbers and character strings. The changes are made to restore the "everything is a string" contract that Tcl implicitly makes; without them, there are observable differences in the behavior of floating point numbers, depending on the state of the internal representation.

Rationale

In today's (8.4) Tcl, there are several gaffes that make floating-point arithmetic less useful than it might be, and cause confusion for the users. Chief among these is that string equality does not imply value equality for floating point numbers:

    % set tcl_precision 12
    12
    % set a [expr 1.00000000000123]
    1.0
    % set b [expr 1.0]
    1.0
    % expr { $a == $b }
    0
    % expr { $a eq $b }
    1

This behavior flies in the face of Tcl's "everything is a string" mantra. In the interaction above, it is visible that a and b are not entirely strings; they have identical string representations, but still test to be unequal with "==". The underlying cause of the behavior is the fact that the default setting for tcl_precision loses precision when converting the floating-point number to a string. Behaviors like this have caused Tcl's cognoscenti to recommend that all programs set tcl_precision to 17; once this setting is made, double-to-string conversions are invertible, and everything is once again a string.

(Why 17? With IEEE-754 arithmetic, 17 decimal digits suffice to distinguish between any two floating point numbers, no matter how small their difference. No smaller number of digits suffices.)

Why is tcl_precision not 17 by default? The reason appears to be that when the precision is set that high, the default IEEE-754 semantics for floating point conversions cause a certain degree of trouble. They require that the decimal representation be the nearest decimal representation to the value of the floating-point number that has the given number of significant digits. This conversion gives rise to peculiarities:

    % set tcl_precision 17; expr 0.2
    0.20000000000000001

The peculiar behavior is, for the most part, suppressed by a lower value for tcl_precision:

    % set tcl_precision 16; expr 0.2
    0.2

The lower value, nevertheless, introduces the trouble above. This TIP proposes a solution to both problems.

Specification

This TIP proposes the following changes to the floating point conversions in the Tcl library:

1. The default value of ::tcl_precision shall be changed to 0. A value of 0 (currently an error) shall be interpreted to mean that a number shall be formatted using the smallest number of decimal digits required to distinguish it from the next floating point number above it and the next floating point number below. The documentation shall formally deprecate changing ::tcl_precision to any other value, warning that doing so risks both loss of precision and inconsistency between string equality and "==".

2. The default input conversion of floating-point numbers, SetDoubleFromAny shall be documented to guarantee precise rounding (generally to within one-half a unit of the least significant place [1/2 ULP]). IEEE-754 rounding semantics are correct for this input. The strtod procedure from the standard C library shall not be used for this conversion, since so many implementations are buggy; instead, a Tcl implementation shall be developed from scratch based on the algorithms developed by Burger and Dybvig [1]. (It is worthy of note that several platforms already eschew the native strtod in favour of one provided in the compat/ library, because of known bugs.)

3. The default output conversion of floating-point numbers, UpdateStringOfDouble shall be implemented to convert a floating-point number to the string having at most $::tcl_precision significant digits that satisfies the following constraints:

   • if reconverted to a binary floating point number, it yields a number that is the closest among all strings having the given number of significant digits.

   • if there is more than one string that is equally close but neither string yields the given number exactly, then the string with the even digit in the least significant place is chosen. Examples:

                   % set tcl_precision 2 ; expr 0.125
                   0.12
                   % set tcl_precision 2 ; expr 0.375
                   0.38
     

   • if there is more than one string with at most the given number of significant digits that yields the given floating-point number, but one has fewer significant digits than the other, then the shorter one is chosen. Example:

                   % expr 0.2
                   0.2
     

     Note that the case above does not return

                   0.20000000000000001
     

     even though that number is closer to the actual floating point value of

                   0.200000000000000011102230246251565404236316680908203125
     

     because 0.2 is the shorter representation.

   • if there is more than one string with at most the given number of significant digits that reconverts exactly to the same floating point number, and all such strings are equally long, then the one closest to the given floating point number is chosen.

4. The test suite for Tcl shall be upgraded to include suitable test vectors for assessing correct rounding behavior. The paper by Verdonk, Cuyt and Verschaeren in the References, and the associated software, present a suitable data set for inclusion.

5. The input and output conversions shall allow for the IEEE special values +Inf, -Inf, and NaN (and for denormalized numbers). The [expr] command shall be changed to allow +Inf and -Inf as the result of an expression; NaN shall still cause an error. Tcl_GetDoubleFromObj shall treat +Inf and -Inf as it does any ordinary floating point number, and return an error for NaN.

6. The [binary scan] and [binary format] commands shall explicitly permit infinities and NaN as values.

Donal K. Fellows notes that... the expr command will handle Inf and NaN quite well if asked nicely; it just won't return them.

 % expr {1 / Inf}
 0.0

References

The basic principles of correctly-rounded floating point conversions have been known for a good many years. Perhaps the two most seminal papers on modern floating point conversion are:

William D. Clinger, How to Read Floating Point Numbers Accurately, Proceedings of the ACM Conference on Programming Language Design and Implementation, June 20-22 1990, pp. 92-101. [2]

Guy L. Steele Jr. and Jon L. White, How to print floating-point numbers accurately. In Proceedings of the ACM Conference on Programming Language Design and Implementation, June 20-22 1990, pp. 112-126. [3]

Both of these papers inspired David Gay to implement a library to do correct rounding in floating point input and output conversions:

David M. Gay, Correctly rounded binary-decimal and decimal-binary conversions, Numerical Analysis Manuscript 90-10, AT&T Bell Laboratories, Murray Hill, New Jersey, November 1990. [4]

A reasonably comprehensive set of test vectors detailing problem cases for rounding conversions is documented in:

Brigitte Verdonk, Annie Cuyt, Dennis Verschaeren, A precision and range independent tool for testing floating-point arithmetic II: Conversions, ACM Transactions on Mathematical Software 27:2 (March 2001), pp. 119-140. [5]

Reference Implementation

A partial reference implementation of this TIP is available in CVS on the kennykb-tcl-numerics branch. Since it requires additional third-party code that is not yet in the core, a different module name is required to check it out:

 export CVSROOT=:ext:yourname@cvs.sourceforge.net:/cvsroot/tcl
 cvs -q checkout -rkennykb-numerics-branch tcl_numerics

As of 2 March 2005, the input and output conversions are implemented, and rounding tests are in the test suite. Work still needs to be done to update [expr] to handle Inf and NaN appropriately, to update [binary] to handle them without throwing errors in Tcl_GetDoubleFromObj, and to adjust the test suite accordingly.

Acknowledgments

The discussion of just why 17 is magical was prompted by a suggestion from Lars Hellstrøm.

Copyright

Copyright (c) 2005 by Kevin B. Kenny. All rights reserved.

This document may be distributed subject to the terms and conditions set forth in the Open Publication License, version 1.0 [6].

This is not necessarily the current version of this TIP.