I’ve always thought Java was one of the languages that prints the shortest decimal strings that round-trip back to floating-point. I was wrong.

In my article “The Shortest Decimal String That Round-Trips May Not Be The Nearest” I describe some shortest string conversions that are tricky to get right. I tried some in Java and guess what? It got them wrong.

After some research I realized the problem is not limited to the tricky power-of-two conversions described in my article; Java fails to print the shortest strings for many other numbers. This is apparently not a bug, because Java is working as designed.

Continue reading …

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.^{1} 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.

Continue reading …

PHP’s base_convert() is a useful function that converts integers between any pair of bases, 2 through 36. However, you might hesitate to use it after reading this vague and mysterious warning in its documentation:

base_convert() may lose precision on large numbers due to properties related to the internal “double” or “float” type used.

The truth is that it works perfectly for integers up to a certain maximum — you just have to know what that is. I will show you this maximum value in each of the 35 bases, and how to check if the values you are using are within this limit.

Continue reading …

I’ve previously written a Windows program (in C++) and an Android app (in Java) to turn my Fretlight guitar into a binary clock. I’ve now written a Python program to do the same, running under Raspbian Linux on a Raspberry Pi computer. I will show you the code and tell you how to run it.

My Fretlight BCD Clock, Run by a Raspberry Pi (Time shown: 7:09:26)

Continue reading …

The 2015 edition of Hour of Code includes a new blocks-based, Star Wars themed coding lesson. In one of the exercises — a simple sprite-based game — you are asked to code a loop that adds 100 to your score every time R2-D2 encounters a Rebel Pilot. But instead of 100, I plugged in a floating-point number; I got the expected “unexpected” results.

Floating-point score in Star Wars Hour of Code exercise

Continue reading …

I traveled to Silicon Valley last week. I visited the Computer History Museum, the Intel Museum, and Stanford University. I took some binary-themed pictures that I’d like to share.

Continue reading …

About a year ago Bruce Dawson informed me that Microsoft is fixing their decimal to floating-point conversion routine in the next release of Visual Studio; I finally made the time to test the new code. I installed Visual Studio Community 2015 Release Candidate and ran my old C++ testcases. The good news: all of the individual conversion errors that I wrote about are fixed. The bad news: many errors remain.

Continue reading …

I have been writing about the spacing of decimal and binary floating-point numbers, and about how their relative spacing determines whether numbers round-trip between those two bases. I’ve stated an inequality that captures the required spacing, and from it I have derived formulas that specify the number of digits required for round-trip conversions. I *have not* proven that this inequality holds, but I will prove “half” of it here. (I’m looking for help to prove the other half.)

Continue reading …

In my article “7 Bits Are Not Enough for 2-Digit Accuracy” I showed how the relative spacing of decimal and binary floating-point numbers dictates when all conversions between those two bases round-trip. There are two formulas that capture this relationship, and I will derive them in this article. I will also show that it takes one more digit (or bit) of precision to round-trip a floating-point number than it does to round-trip an integer of equal significance.

Continue reading …

In the 1960s, I. Bennett Goldberg and David W. Matula published papers relating floating-point number systems of different bases, showing the conditions under which conversions between them round-trip; that is, when conversion to another base and back returns the original number. Independently, both authors derived the formula that specifies the number of significant digits required for round-trip conversions.

In his paper “27 Bits Are Not Enough for 8-Digit Accuracy”, Goldberg shows the formula in the context of decimal to binary floating-point conversions. He starts with a simple example — a 7-bit binary floating-point system — and shows that it does not have enough precision to round-trip all 2-digit decimal floating-point numbers. I took his example and put it into diagrams, giving you a high level view of what governs round-trip conversions. I also extended his example to show that the same concept applies to binary to decimal floating-point round-trips.

Relative Spacing Governs Round-Trips

The well-known digit counts for round-trip conversions to and from IEEE 754 floating-point are dictated by these same principles.

Continue reading …

In a computer, decimal floating-point numbers are converted to binary floating-point numbers for calculation, and binary floating-point numbers are converted to decimal floating-point numbers for display or storage. In general, these conversions are inexact; they are rounded, and rounding is governed by the spacing of numbers in each set.

Floating-point numbers are unevenly spaced, and the spacing varies with the base of the number system. Binary floating-point numbers have power of two sized gaps that change size at power of two boundaries. Decimal floating-point numbers are similarly spaced, but with power of ten sized gaps changing size at power of ten boundaries. In this article, I will discuss the spacing of decimal floating-point numbers.

Continue reading …

An IEEE 754 binary floating-point number is a number that can be represented in normalized binary scientific notation. This is a number like 1.00000110001001001101111 x 2^{-10}, which has two parts: a *significand*, which contains the significant digits of the number, and a power of two, which places the “floating” radix point. For this example, the power of two turns the shorthand 1.00000110001001001101111 x 2^{-10} into this ‘longhand’ binary representation: 0.000000000100000110001001001101111.

The significands of IEEE binary floating-point numbers have a limited number of bits, called the *precision*; single-precision has 24 bits, and double-precision has 53 bits. The range of power of two exponents is also limited: the exponents in single-precision range from -126 to 127; the exponents in double-precision range from -1022 to 1023. (The example above is a single-precision number.)

Limited precision makes binary floating-point numbers discontinuous; there are *gaps* between them. Precision determines the *number* of gaps, and precision and exponent together determine the *size* of the gaps. Gap size is the same between consecutive powers of two, but is different for every consecutive pair.

Gaps Between Binary Floating-Point Numbers In a Toy Floating-Point System

Continue reading …