The Shortest Decimal String That Round-Trips May Not Be The Nearest

Any double-precision floating-point number can be identified with at most 17 significant decimal digits. This means that if you convert a floating-point number to a decimal string, round it (to nearest) to 17 digits, and then convert that back to floating-point, you will recover the original floating-point number. In other words, the conversion will round-trip.

Sometimes (many) fewer than 17 digits will serve to round-trip; it is often desirable to find the shortest such string. Some programming languages generate shortest decimal strings, but many do not.¹ If your language does not, you can attempt this yourself using brute force, by rounding a floating-point number to increasing length decimal strings and checking each time whether conversion of the string round-trips. For double-precision, you’d start by rounding to 15 digits, then if necessary to 16 digits, and then finally, if necessary, to 17 digits.

There is an interesting anomaly in this process though, one that I recently learned about from Mark Dickinson on stackoverflow.com: in rare cases, it’s possible to overlook the shortest decimal string that round-trips. Mark described the problem in the context of single-precision binary floating-point, but it applies to double-precision binary floating-point as well — or any precision binary floating-point for that matter. I will look at this anomaly in the context of double-precision floating-point, and give a detailed analysis of its cause.

The Problem Numbers: Powers of Two

Let’s try the brute force algorithm on 2^-44, which as a hexadecimal floating point constant is 0x1p-44, and as a full-precision decimal value is 5.684341886080801486968994140625e-14. Rounded to 15 digits, it is 5.6843418860808e-14, but that doesn’t round-trip: it converts to 0x1.ffffffffffffep-45. Rounded to 16 digits, it is 5.684341886080801e-14, but that doesn’t round-trip either: it converts to 0x1.fffffffffffffp-45. So we must settle for the 17-digit value, 5.6843418860808015e-14.

But wait! There is 16-digit number that round-trips, and we missed it: 5.684341886080802e-14. Why does that round-trip, when the closer 16-digit number does not?

The root of the problem is that the size of the gaps between binary floating-point numbers changes at power of two boundaries; gap size above a power of two is double the gap size below a power of two. This asymmetry is a necessary condition, but it alone does not cause the problem; the size of the gaps between decimal numbers around powers of two factors in as well. For double-precision, the problematic decimal gap size occurs only for 16-digit numbers.

Even for 16-digit numbers, not all powers of two exhibit the anomaly; the binary and decimal numbers must align in a certain way. For starters, the nearest 16-digit decimal number must be below the power of two, and the next higher 16-digit decimal number must be above the power of two. Furthermore, the nearest 16-digit decimal number must be more than halfway towards the next lower 53-bit binary number (it can’t be halfway because round-to-nearest-even would map it to the power of two), while the next higher 16-digit decimal number can be no more than halfway toward the next higher 53-bit binary number. Because the halfway distance is different on either side of the power of two, the farther decimal number will map to the power of two, but the nearer one won’t.

This diagram, drawn to scale, depicts the situation as it applies to our example:

The diagram shows the 53-bit binary floating-point numbers transitioning from the 2^-45 exponent to the 2^-44 exponent range. This occurs under the 10^-14 range of 16-digit floating-point decimal numbers. The size of the binary gaps change from 2^(-45+1-53)= 2^-97 ≈ 6.3 x 10^-30 to 2^(-44+1-53) = 2^-96 ≈ 1.3 x 10^-29. The decimal gap over this range stays constant at 10^(-14+1-16)= 10^-29. Therein lies the problem; the decimal gap size is between the two binary gap sizes.

The Problematic Decimal Gap Size

Let’s derive the range of decimal gap size that sets the stage for the anomaly. First, let’s give things some names:

• p is the power of two, p-1 is the 53-bit binary number that precedes it, and p+1 is the 53-bit binary number that follows it.
• n is the nearest 16-digit decimal number, and n+1 is the next bigger 16-digit decimal number.
• p+1/2 is the halfway point between p and p+1; p-1/2 is the halfway point between p and p-1.
• p+1/4 is one quarter of the way between p and p+1.

It’s easier to analyze decimal gap size by considering two cases, which I’ll call the minimum range and maximum range.

For the minimum range, consider n fixed just below p-1/2, with n+1 varying from just above p+1/4 (enough to make it farther away than n) to p+1/2:

This shows the decimal gap size — the distance between n and n+1 — varies from a little more than one lower binary gap to a little more than 3/4 upper binary gap.

For the maximum range, consider n+1 fixed at p+1/2, with n varying from just below p-1/2 to just above p-1:

This shows the decimal gap size varies from a little more than 3/4 upper binary gap to a little less than one upper binary gap.

Combining the two ranges we see the problematic decimal gap size is between the lower and upper binary gap size. Gap size in this range is necessary for the anomaly to occur, but not sufficient.

When This Decimal Gap Size Occurs

The problematic decimal gap size only occurs for 16-digit decimal numbers. This is because for decimal numbers of 15 digits or less, the decimal gap size is greater than the largest double-precision binary gap size, and for decimal numbers of 17 digits or more, the decimal gap size is less than the smallest double-precision binary gap size. These latter two facts are a consequence of round-trip decimal to floating-point to decimal and floating-point to decimal to floating-point conversions, respectively.

All The Powers of Two For Which This Happens

I wrote a C program to test all 2,046 powers of two in the normal double-precision range: 2^-1022 to 2¹⁰²³. There are 54 for which the nearest 16-digit number does not round-trip, yet the next one up does:

2⁹⁷⁶, 2⁹⁶⁶, 2⁹⁵⁶, 2⁸⁹⁶, 2⁸⁹⁰, 2⁸⁶³, 2⁸⁰³, 2⁷⁴⁰, 2⁷¹⁰, 2⁵⁹⁴, 2⁵⁷⁴, 2⁵⁵⁴, 2⁵⁴⁴, 2⁵³⁴, 2⁴⁸¹, 2⁴⁰⁵, 2³⁹⁸, 2³⁷⁸, 2³⁴⁵, 2³⁰⁵, 2²⁷⁵, 2¹⁸², 2¹⁷², 2¹⁴⁹, 2¹³², 2¹²², 2⁸⁹, 2^-24, 2^-44, 2^-77, 2^-97, 2^-140, 2^-296, 2^-366, 2^-383, 2^-489, 2^-496, 2^-499, 2^-509, 2^-549, 2^-569, 2^-645, 2^-652, 2^-662, 2^-695, 2^-705, 2^-778, 2^-788, 2^-791, 2^-808, 2^-921, 2^-957, 2^-1007, 2^-1017

Of those, eight have a 15-digit rounded-to-nearest number that round-trips:

2⁹⁶⁶, 2⁹⁵⁶, 2⁸⁹⁰, 2⁷⁴⁰, 2¹⁴⁹, 2^-499, 2^-569, 2^-645

So if you use the brute force testing algorithm, the anomalous behavior only comes into play for 46 floating-point numbers.

(It turns out for each of the eight cases, the 15-digit rounding and non-nearest 16-digit number are the same.)

Single-Precision

The same anomaly applies to single-precision, as Mark showed on Stack Overflow. Round-tripping protects rounding to 6 digits or less or 9 digits or more, leaving 7 and 8 digit numbers as candidates. Of the 254 normal powers of two, the anomaly occurs only for three, and only for their 8-digit roundings: 2⁹⁰, 2⁸⁷, and 2^-96. (None of the three have 6 or 7 digit strings that round-trip.)

Discussion

For any binary precision, the problem area will be in the “middle ground” where the digit count is between the two round-trip bounds.

For negative numbers, the results are the same, except the drawings would be mirror images.

¹ I did a quick test on Java, Python, PHP, and Javascript (C doesn’t really have a mechanism for it). Only Python (3) and Javascript (tested on Firefox, Chrome, Edge, and Internet Explorer) appear to be designed to return the shortest decimal string. (Actually, I know Python is designed as such; I did not look into Javascript’s design and code.)