Number of Bits in a Decimal Integer

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.

Continue reading “Number of Bits in a Decimal Integer”

Special Case Laws of Exponents for Powers of Two

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.

Continue reading “Special Case Laws of Exponents for Powers of Two”

How strtod() Works (and Sometimes Doesn’t)

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 to double.

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.

Continue reading “How strtod() Works (and Sometimes Doesn’t)”

Adjusting the Floating-Point Approximation in strtod()

I’ve discussed how David Gay’s strtod() function computes an initial floating-point approximation and then uses a loop to check and correct it, but I have not discussed how the correction is made. That is the last piece of the strtod() puzzle, and I will cover it in this article.

Continue reading “Adjusting the Floating-Point Approximation in strtod()”

“0.1 Repeating” In Binary Equals 1

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.

Continue reading ““0.1 Repeating” In Binary Equals 1″

Why 0.1 Does Not Exist In Floating-Point

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:

Decimal 0.1 In Binary ( To 1369 Places)
Decimal 0.1 In Binary ( To 1369 Places)

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.

Continue reading “Why 0.1 Does Not Exist In Floating-Point”

Converting a Bicimal to a Fraction (Series Method)

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.

Continue reading “Converting a Bicimal to a Fraction (Series Method)”

Converting a Bicimal to a Fraction (Direct Method)

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.

Example of Direct Method (7/12 in Decimal)
Example of Direct Method (7/12 in Decimal)

Continue reading “Converting a Bicimal to a Fraction (Direct Method)”

Converting a Bicimal to a Fraction (Subtraction Method)

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.

Equivalent Representations of 47/12, in Binary
Equivalent Representations of 47/12, in Binary

Continue reading “Converting a Bicimal to a Fraction (Subtraction Method)”

Bicimals

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.)

Continue reading “Bicimals”

A Bug in the Bigcomp Function of David Gay’s strtod()

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:

1.8254370818746402660437411213933955878019332885742187

As Geza noted, the problem is in the bigcomp() function, an optimization that kicks in for long decimal inputs. I traced his example through bigcomp() — I’ll show you what’s going on.

Continue reading “A Bug in the Bigcomp Function of David Gay’s strtod()”