Every integer has an equivalent representation in decimal and binary. Except for 0 and 1, the binary representation of an integer has more digits than its decimal counterpart. To find the number of binary digits (bits) corresponding to any given decimal integer, you could convert the decimal number to binary and count the bits. For example, the two-digit decimal integer 29 converts to the five-digit binary integer 11101. But there’s a way to compute the number of bits directly, without the conversion.
Sometimes you want to know, not how many bits are required for a specific integer, but how many are required for a d-digit integer — a range of integers. A range of integers has a range of bit counts. For example, four-digit decimal integers require between 10 and 14 bits. For any d-digit range, you might want to know its minimum, maximum, or average number of bits. Those values can be computed directly as well.
In my article “Composing Powers of Two Using The Laws of Exponents” I showed how to combine powers of two using the standard laws of exponents. There are two other rules I use when combining powers of two; I call them the add duplicate power of two rule and the subtract half power of two rule. These are nonstandard rules, applying only to powers of two. Although these are special cases of the existing multiplication and division rules, I’ve found value in recognizing them in addition and subtraction form. I’ll state these rules and show examples of their usage.
Numbers are entered into computers as strings of text. These strings are converted to binary, into the numeric form understood by the computer’s hardware. Numbers with a decimal point — numbers we think of as real numbers — are converted into a format called binary floating-point. The procedure that converts decimal strings to binary floating-point — IEEE double-precision binary floating-point in particular — goes by the name strtod(), which stands for string todouble.
Converting decimal strings to doubles correctly and efficiently is a surprisingly complex task; fortunately, David M. Gay did this for us when he wrote this paper and released this code over 20 years ago. (He maintains this reference copy of strtod() to this day.) His code appears in many places, including in the Python, PHP, and Java programming languages, and in the Firefox, Chrome, and Safari Web browsers.
I’ve spent considerable time reverse engineering strtod(); neither the paper nor the code are easy reads. I’ve written articles about how each of its major pieces work, and I’ve discovered bugs (as have a few of my readers) along the way. This article ties all of my strtod() research together.
In decimal, “0.9 repeating”, or 0.9, equals 1. In binary, a similar thing is true: “0.1 repeating”, or 0.1, equals 1. I’ll show you three ways to prove it, using the three bicimal to fraction conversion algorithms I described recently.
Many new programmers become aware of binary floating-point after seeing their programs give odd results: “Why does my program print 0.10000000000000001 when I enter 0.1?”; “Why does 0.3 + 0.6 = 0.89999999999999991?”; “Why does 6 * 0.1 not equal 0.6?” Questions like these are asked every day, on online forums like stackoverflow.com.
The answer is that most decimals have infinite representations in binary. Take 0.1 for example. It’s one of the simplest decimals you can think of, and yet it looks so complicated in binary:
The bits go on forever; no matter how many of those bits you store in a computer, you will never end up with the binary equivalent of decimal 0.1.
I’ve shown you two ways to convert a bicimal to a fraction: the subtraction method and the direct method. In this article, I will show you a third method — a common method I call the series method — that uses the formula for infinite geometric series to create the fraction.
There are several ways to convert a repeating bicimal to a fraction. I’ve shown you the subtraction method; now I’ll show you the direct method, my name for the method that creates a fraction directly, using a numerator and denominator of well-known form.
In my article “Binary Division” I showed how binary long division converts a fraction to a repeating bicimal. In this article, I’ll show you a well-known procedure — what I call the subtraction method — to do the reverse: convert a repeating bicimal to a fraction.
There is no widely accepted term for fractional binary numbers like 0.11001. A fractional decimal number like 0.427 is called a decimal or decimal fraction. A fractional binary number is called many things, including binary fraction, binary decimal, binary expansion, bicimal, binimal, binary radix fraction, and binary fractional (my term). In this article, I’m going to argue that bicimal should be the universal term.
(Please let me know what you think — take the poll at the end of this article.)
Last week, a reader of my blog, Geza Herman, told me about a bug he found in David Gay’s strtod() function. In random testing of decimal numbers nearly halfway between double-precision floating-point numbers, he discovered this 53-digit number, which converts incorrectly: