TIP #132 Version 1.3: 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 be the smallest number of decimal digits required to distinguish any two floating point numbers; on the nearly-ubiquitous IEEE-754 system of floating point arithmetic, the default value of ::tcl_precision shall be 17. 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 suitably modified version of David Gay's input conversion code shall be added to the Tcl library. (It is worthy of note that several platforms already use a strtod from the compat/ library in place of the native one, 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.

     The dtoa function in David Gay's floating-point conversion library already has a collection of options that implement these semantics.

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.

Additional Possibilities

As long as we're changing floating-point conversions anyway, we may also want to address the correct handling of infinities and "not a number" conditions. The current code contains some peculiar surprises. Tcl tries hard not to present these exceptions to the Tcl script. It does not return Not a Number:

 % expr { 1. / 0. }
 divide by zero
 % expr { asin( 1.5 ) }
 domain error: argument not in valid range

nor Infinity:

 % expr { pow( 2., 512 ) * pow( 2., 512 ) }
 floating-point value too large to represent

Some cases even cause it to consider arithmetic underflow an error:

 % expr { pow( 2., -1075 ) }
 floating-point value too small to represent

Worst of all, these errors can occur when a Not-a-Number or Infinity arrives in the Tcl script by other means:

 % binary scan \x7f\xf8\x00\x00\x00\x00\x00\x00 d num
 1
 % set num
 NaN
 % expr $num
 domain error: argument not in valid range

and even can happen because of conversions from strings:

 % expr { "NaN" }
 domain error: argument not in valid range
 % expr "Inf"
 floating-point value too large to represent

I would therefore be inclined to allow output conversion of "Not a Number" and "Infinity", rather than simply signalling Tcl errors. At the very least, the documentation should warn that certain alphabetic strings are "numbers":

 % string is double NaN
 1
 % string is double Inf
 1

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. [1]

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. [2]

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. [3]

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. [4]

Reference Implementation

The updates described herein have not yet been integrated into the Tcl library, but most of the groundwork has been laid. In particular, Gay's codes are available from Netlib [5], and Verdonk's test vectors to assess IEEE-754 compliance are available from her Web site at [6]. Both have license agreements that are sufficiently liberal to permit incorporating them into the Tcl library.

Acknowledgments

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

Copyright

Copyright (c) 2003 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 [7].

This is not necessarily the current version of this TIP.