United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-4511638 : Double.toString(double) sometimes produces incorrect results

Details
Type:
Enhancement
Submit Date:
2001-10-05
Status:
Open
Updated Date:
2014-01-09
Project Name:
JDK
Resolved Date:
Component:
core-libs
OS:
generic
Sub-Component:
java.lang
CPU:
generic
Priority:
P3
Resolution:
Unresolved
Affected Versions:
1.3.1,6
Targeted Versions:

Related Reports

Sub Tasks

Description
Name: bsT130419			Date: 10/05/2001


java version "1.3.1"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.1-b24)
Java HotSpot(TM) Client VM (build 1.3.1-b24, mixed mode)

According to the description of Double.toString(double), the resulting string
produced by this method shall be chosen so that the number of digits is as
small as possible:

"There must be at least one digit to represent the fractional part, and beyond
that as many, ***but only as many***, more digits as are needed to uniquely
distinguish the argument value from adjacent values of type double."


The following simple program shows that for the specific case coded, this is
not true.
The program first shows that, internally, 1.0E23 and 9.999999999999999E22 are
the *very same* double. In fact, as seen by the the first 2 System.out.println
() the raw bitstrings are the same.
However, converting this double to a string produces a result that is much
longer as needed to recover the original value. The conversion
produces "9.999999999999999E22" instead of the much shorter "1.0E23" which,
internally, represents the *same* value. Because "1.0E23" is shorter
than "9.999999999999999E22" and because when converted back to double both
produce the same double value, "1.0E23" *must* be output according to the
specification.


class DoubleIO {
    public static void main(String[] args) {
	String s0 = "1.0E23";
	String s1 = "9.999999999999999E22";
	double d0 = Double.valueOf(s0).doubleValue();
	double d1 = Double.valueOf(s1).doubleValue();

	System.out.println(Double.doubleToLongBits(d0));
	System.out.println(Double.doubleToLongBits(d1));

	System.out.println(s0 + " -> " + Double.toString(d0));
    }
}
(Review ID: 133203) 
======================================================================
###@###.### 2004-11-11 21:42:12 GMT
Commentary on a fix for this (un-edited), from Peabody community member:


A DESCRIPTION OF THE FIX :
Issues with java.lang.Double.toString()
---------------------------------------


Introduction
------------

Although reporting bugs, this document is longer than a usual bug report
due to some technical issues that require a deeper discussion. Moreover,
while I implemented a "bug fix" contribution, it is really new software
implemented from scratch, not a simple patch suite to apply to the
current source base. I will be glad to submit it to Mustang if you
decide that the issues described here are important enough to deserve
more attention.

In what follows, class names starting with a dot shall be prefixed with
java.lang: e.g. .String stands for java.lang.String. (The initial dot
prevents ambiguities with classes in unnamed packages.)

The current specification of .Double.toString(double) fails to produce
the shortest possible decimal number which can recover the original
double. This document discusses the issue and explains why producing the
shortest possible decimal is better, both from a theoretical as well as
from a practical point of view.
Moreover, several bugs in the current implementation of
.Double.toString(double) are shown.
Finally, a modified specification is proposed. The proposed
specification is accompanied by an implementation which solves all the
current bugs. In addition, it is about two times faster on the average
than the JDK implementation.


Definitions
-----------

* Exponentiation is denoted by ** to avoid confusion with Java's meaning
of ^ for xor.
* A decimal number is a real number of the form d*10**k, where d and k
are integers.
* A double is a real number whose value is in the Java double set.
* A denormal number is a double with a Java denormalized value.
* A normal number is any finite nonzero double which is not a denormal.

The discussion below is limited to nonzero finite positive numbers.


The problems with the current specification
-------------------------------------------

.Double.toString(double) is supposed to produce a .String denoting a
decimal number sufficiently close to the double argument so that the
converse transformation, as specified for example by
.Double.parseDouble(.String), can recover the original double. Moreover,
it is also supposed to produce a shortest decimal number which still can
recover the double.

.Double.toString(1e23) produces "9.999999999999999E22". In fact, this
output recovers the original double closest to 10**23 but, evidently, it
is not the shortest: "1.0E23" is quite shorter!
This is due to the current specification which fixes the exponent too
early. The premature commitment to the exponent then necessarily leads
to the long string of nines. The best exponent should be chosen while
producing the digits, not that early. (See also bug located at
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4511638 submittet
years ago by me and the relevant standard literature cited there by the
reviewer.)

.Double.toString(5e-324) produces "4.9E-324". All of 3*10**-324,
4*10**-324, 5*10**-324, 6*10**-324, 7*10**-324 can recover the original
double and they are all shorter than 4.9*10**-324. The proposed
specification would produce "5.0E-324" because, among the shortests, it
is also the nearest to the original double, which is in fact
approximatively 4.9*10**-324. (The trailing zero in "5.0E-324" is a
backward compatibility concession to the current specification. In my
opinion "5E-324" is even better: it has less characters while, at the
same time, syntactically denoting a floating point value.)

In some cases the specification is ambiguous. For example, it fails to
define which of two equally short values that both happen to recover the
original double shall be output. This underspecification could lead to
different results on different Java implementations.


Implementation issues
---------------------

The following list shows some examples that have been detected on
jdk1.5.0_05 and earlier releases as well as on the most recent Mustang
(build 1.6.0-ea-b56 of 2005-10-13). Conceptually, the arrow stands for
the double conversion decimal -> double -> decimal.

* Spurious unnecessary trailing 0. Note that this is not a mathematical
issue: the numbers on both sides of the arrow are the same.
0.001 --> 0.0010
0.002 --> 0.0020
0.003 --> 0.0030

* String of 9s.
8.41E21 --> 8.409999999999999E21
2.0E23 --> 1.9999999999999998E23
8.962E21 --> 8.961999999999999E21

* String of 0s.
7.3879E20 --> 7.387900000000001E20
3.1E22 --> 3.1000000000000002E22
5.63E21 --> 5.630000000000001E21

* 18 digits, even though 17 digits are *always* enough (see Matula's
papers cited in the references)
2.82879384806159E17 --> 2.82879384806159008E17
1.387364135037754E18 --> 1.38736413503775411E18
1.45800632428665E17 --> 1.45800632428664992E17

* 5 digits too much.
1.790086667993E18 --> 1.79008666799299994E18
2.273317134858E18 --> 2.27331713485799987E18
7.68905065813E17 --> 7.6890506581299994E17

* Not the closest to the intermediate double, left number is closer.
1.9400994884341945E25 --> 1.9400994884341944E25
3.6131332396758635E25 --> 3.6131332396758634E25
2.5138990223946153E25 --> 2.5138990223946152E25

* Among the powers of 2, there are more than 17% that are output as
unnecessarily long numbers, the worst case being 2**959:
4.8726570057E288 --> 4.8726570056999995E288
which is 6 digits longer than needed.

It is quite unfortunate that some of the cases presented above can be
produced in tons. All of them have not been found by clever analysis but
by really simple programs. On the good news, decimal outputs that
couldn't recover the original doubles have not been detected.


Advocating for a better specification
-------------------------------------

What is wrong with the "9.999999999999999E22" output? From the
perspective of a human user that types "1e23" and gets
"9.999999999999999E22" as feedback, this can be annoying, to say the
least. The system responds with a complicated number to a simple input.

In the late sixties, Matula published some results about floating-point
conversions (see references). One of his results states that there exist
conversions from decimal to binary and back to decimal which always
recover the very same decimal, provided it has no more than 15 digits
(and provided that the intermediate double is normal). Among many other
things, this means that 1e23 shall be output as "1.0E23".
(Although Matula limited the discussion to truncation and one form of
rounding conversion, the results can be extended to more general
roundings, including IEEE 754. See
http://homepage.sunrise.ch/mysunrise/r.giulietti/Matula.pdf for a short
discussion.)

By specifying that .Double.toString(double) shall produce the shortest
decimal that can recover the original double, Matula's result is
implicitly guaranteed.
In other words, if .Double.toString(double) is required to produce the
shortest decimal, then the decimal -> binary -> decimal is the identity
(as far as the numerical value is concerned), provided the original
decimal has no more than 15 digits and provided that the intermediate
double is normal.
In practical terms, this means that the vast majority of user inputs are
guaranteed to be output with the same numerical value. All physical
constants known to me, for example, can be input to the system and are
guaranteed to come out with the same numerical value.

This regularity and the "no surprise" side effects for the user, both
based on Matula's sound results, are the driving reasons to modify the
specification and to adopt the proposed one.
Another advantage of the proposed specification is that it clearly
separates the definition of the best decimal number from its
representation as .String. Moreover, the specified decimal number is
unique: there are sufficient rules to ensure that the conversion is
unambiguous. This contrasts with the current specification which is
ambiguous in the case that there is more than one "shortest" decimal.
Such underspecifications fail to ensure identity of the decimal ->
binary -> decimal conversion, where applicable. Moreover, they could
lead to different results on different implementations.


The proposed specification
--------------------------

Because this is longer than a usual contribution, the proposed
specification is located at
http://homepage.sunrise.ch/mysunrise/r.giulietti/Double.html in the form
of a Javadoc.


The accompanying implementation
-------------------------------

  To solve the bugs detected in the JDK, I wrote a new implementation of
.Double.toString(double) from scratch. Because it mirrors the proposed
specification instead of the current one, it only makes sense to submit
the implementation to Mustang if the spirit of the specification, if not
its exact wording, is accepted as well.

The implementation has the following features:
* It solves all the problems above.
* It is pure Java. It uses only JDK's public APIs in java.lang and
java.math and some self written supporting classes.
* It is threadsafe as long as the used API's are threadsafe.
* It has been extensively tested. All outputs up to 9 digits have been
found to be correct according to the proposed specification. Many days
of computing have been devoted to test other billions of randomly
generated doubles for correctness of the outputs. All boundary cases
have been tested (powers of 10, powers of 2, Paxson's test suite,
implementation dependent boundary cases).
* And last but not least, it performs twice as fast on the average, and
for long outputs is up to 4 times faster than the JDK.


References
----------

D. W. Matula, "The Base Conversion Theorem", Proc. AMS, 19 (1968) p.
716-723
D. W. Matula, "In-and-Out Conversions", Communications of the ACM, 11
(1968) p. 47-50

                                    

Comments
EVALUATION

The bug submitter has identified a corner case in the current algorithm which could be improved.  The current implementation is correct with respect to the current specfication but the specification should be updated to behave as expected; i.e. return the shortest string.

The actual specification is a little more subtle than just returning the shortest string; the right exponent must be found first.  See

http://java.sun.com/j2se/1.4/docs/api/java/lang/Double.html#toString(double)

	"Let n be the unique integer such that 10^n <= m < 10^(n+1); then
	let a be the mathematically exact quotient of m and 10^n so
	that 1 <= a < 10. The magnitude is then represented as the
	integer part of a, as a single decimal digit, followed by '.'
	('\u002E'), followed by decimal digits representing the
	fractional part of a, followed by the letter 'E' ('\u0045'),
	followed by a representation of n as a decimal integer, as
	produced by the method Integer.toString(int)."

In this case, the exact decimal value of the floating-point number in question is

99999999999999991611392 = 9.9999999999999991611392 x 10^22

Therefore, the floating-point number m is between 10^22 and 10^23, just a hair less than 10^23.  So, given that the exponent is determined to be 22, the longer 9.999... string is necessary.

However, besides being shorter, it is also true that the decimal value of "1.0e23" is closer than "9.999999999999999E22" to the actual numerical value value of the floating-point number is question.

The specification for Java's toString routine is based on a paper by Guy Steele and Jon White, "How to Print Floating-Point Number Accurately," Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, June 20-22, 1990.

http://www.acm.org/pubs/citations/proceedings/pldi/93542/p112-steele/

The algorithms in this paper will work with, but don't require, the IEEE 754 floating-point arithmetic mandated by Java.  IEEE 754 has more rigorous rounding policies than prior floating-point standards.  If IEEE 754 style rounding is assumed, variants of the Steele-White algorithm that return "1.0e23" instead of ""9.999999999999999E22" can be defined.  This latter point is discussed in David Gay's paper

"Correctly Rounded Binary-Decimal and Decimal-Binary Conversions,"
David M. Gay
http://www.ampl.com/cm/cs/what/ampl/REFS/abstracts.html#rounding

The specification of the toString method should be amended in such a way to return the shortest string.

###@###.### 2001-11-12

Changed from bug to RFE since the current spec is being followed.

###@###.### 2002-01-29

Decomitting from Tiger, issue should be addressed in a future release.

###@###.### 2003-09-08
                                     
2002-01-29
CONVERTED DATA

BugTraq+ Release Management Values

COMMIT TO FIX:
dragon


                                     
2004-06-14
EVALUATION

Contribution-Forum:https://jdk-collaboration.dev.java.net/servlets/ProjectForumMessageView?messageID=12001&forumID=1463
                                     
2006-03-15



Hardware and Software, Engineered to Work Together