7 Bits Are Not Enough for 2-Digit Accuracy

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.

https://www.exploringbinary.com/wp-content/uploads/Round.trip.spacing.png
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 “7 Bits Are Not Enough for 2-Digit Accuracy”

The Spacing of Decimal Floating-Point Numbers

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 “The Spacing of Decimal Floating-Point Numbers”

The Spacing of Binary Floating-Point Numbers

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.

https://www.exploringbinary.com/wp-content/uploads/gaps.PO2.4.unmarked.png
Gaps Between Binary Floating-Point Numbers In a Toy Floating-Point System

Continue reading “The Spacing of Binary Floating-Point Numbers”

Nine Ways to Display a Floating-Point Number

(Updated June 22, 2015: added a tenth display form, “decimal integer times a power of ten”.)

In the strictest sense, converting a decimal number to binary floating-point means putting it in IEEE 754 format — a multi-byte structure composed of a sign field, an exponent field, and a significand field. Viewing it in this raw form (binary or hex) is useful, but there are other forms that are more enlightening.

I’ve written an online converter that takes a decimal number as input, converts it to floating-point, and then displays its exact floating-point value in ten forms (including the two raw IEEE forms). I will show examples of these forms in this article.

Continue reading “Nine Ways to Display a Floating-Point Number”

PHP Converts 2.2250738585072012e-308 Incorrectly

While testing my new decimal to floating-point converter I discovered a bug in old territory: PHP incorrectly converts the number 2.2250738585072012e-308.

<?php printf("%.17g",2.2250738585072012e-308); ?>

This prints 2.2250738585072009E-308; it should print 2.2250738585072014e-308. (I verified that the internal double value is wrong; the printed value correctly represents it.)

Continue reading “PHP Converts 2.2250738585072012e-308 Incorrectly”

Floating-Point Will Still Be Broken In the Year 2091

Variants of the question “Is floating point math broken?” are asked every day on Stackoverflow.com. I don’t think the questions will ever stop, not even by the year 2091 (that’s the year that popped into my head after just reading the gazillionth such question).

https://www.exploringbinary.com/wp-content/uploads/SO.2091.small.png
A representative floating-point question asked on stackoverflow.com in 2009, projected to be just as popular in 2091 (click thumbnail to enlarge)

Continue reading “Floating-Point Will Still Be Broken In the Year 2091”

Testing Some Edge Case Conversions In App Inventor

After discovering that App Inventor represents numbers in floating-point, I wanted to see how it handled some edge case decimal/floating-point conversions. In one group of tests, I gave it numbers that were converted to floating-point incorrectly in other programming languages (I include the famous PHP and Java numbers). In another group of tests, I gave it numbers that, when converted to floating-point and back, demonstrate the rounding algorithm used when printing halfway cases. It turns out that App Inventor converts all examples correctly, and prints numbers using the round-half-to-even rule.

Continue reading “Testing Some Edge Case Conversions In App Inventor”

Numbers In App Inventor Are Stored As Floating-Point

I am exploring App Inventor, an Android application development environment for novice programmers. I am teaching it to my kids, as an introductory step towards “real” app development. While playing with it I wondered: are its numbers implemented in decimal? No, they aren’t. They are implemented in double-precision binary floating-point. I put together a few simple block programs to demonstrate this, and to expose the usual floating-point “gotchas”.

App Inventor Blocks To Display 0.1 to 17 Digits
App Inventor Blocks To Display 0.1 to 17 Digits

Continue reading “Numbers In App Inventor Are Stored As Floating-Point”

GCC Avoids Double Rounding Errors With Round-To-Odd

GCC was recently fixed so that its decimal to floating-point conversions are done correctly; it now calls the MPFR function mpfr_strtofr() instead of using its own algorithm. However, GCC still does its conversion in two steps: first it converts to an intermediate precision (160 or 192 bits), and then it rounds that result to a target precision (53 bits for double-precision floating-point). That is double rounding — how does it avoid double rounding errors? It uses round-to-odd rounding on the intermediate result.

Continue reading “GCC Avoids Double Rounding Errors With Round-To-Odd”

real.c Rounding Is Perfect (GCC Now Converts Correctly)

GCC, the GNU Compiler Collection, recently fixed this eight and a half year old bug: “GCC Bugzilla – Bug 21718: real.c rounding not perfect.” This bug was the cause of incorrect decimal string to binary floating-point conversions. I first wrote about it over three years ago, and then recently in September and October. I also just wrote a detailed description of GCC’s conversion algorithm last month.

This fix, which will be available in version 4.9, scraps the old algorithm and replaces it with a call to MPFR function mpfr_strtofr(). I tested the fix on version 4.8.1, replacing its copy of gcc/real.c with the fixed one. I found no incorrect conversions.

Continue reading “real.c Rounding Is Perfect (GCC Now Converts Correctly)”

Gay’s strtod() Returns Zero For Inputs Just Above 2^-1075

While running some of GCC’s string to double conversion testcases I discovered a bug in David Gay’s strtod(): it converts some very small subnormal numbers incorrectly. Unlike numbers 2-1075 or smaller, which should convert to zero under round-to-nearest/ties-to-even rounding, numbers between 2-1075 and 2-1074 should convert to 2-1074, the smallest number representable in double-precision binary floating-point. strtod() correctly converts the former to 0, but it incorrectly converts the latter to 0 as well.

(Update 11/25/13: This bug has been fixed.)

Continue reading “Gay’s strtod() Returns Zero For Inputs Just Above 2^-1075”

College Notebook: When I Was Taught Floating-Point

In my article “Floating-Point Questions Are Endless on stackoverflow.com” I showed examples of the many questions asked that demonstrate lack of knowledge of the most basic property of floating-point — that not all decimal values are representable in binary. In response to a reader’s comment on my article I wrote:

It would be interesting to know how it’s taught today (it’s been a very long time since I was taught it). I can’t imagine though that the person teaching it wouldn’t say — within a sentence or two of saying “floating-point” — that it “can’t represent all decimal numbers accurately”.

That prompted me to look through my box of thirty plus year old college (undergraduate) notebooks. I found notebooks for four classes in which I was taught floating-point. The notes from three of those classes confirm what I thought — that we were warned early of the decimal/binary mismatch. But in the first class of the four — the beginner’s class — it’s less clear what we were told. I’ll show you images of the relevant excerpts from my notes. (I notice I had some elements of cursive in my handwriting back then.)

Continue reading “College Notebook: When I Was Taught Floating-Point”