Number of Decimal Digits In a Binary Fraction

The binary fraction 0.101 converts to the decimal fraction 0.625; the binary fraction 0.1010001 converts to the decimal fraction 0.6328125; the binary fraction 0.00111011011 converts to the decimal fraction 0.23193359375. In each of those examples, the binary fraction converts to a decimal fraction — that is, a terminating decimal representation — that has the same number of digits as the binary fraction has bits.

One digit per bit? We know that’s not true for binary integers. But it is true for binary fractions; every binary fraction of length n has a corresponding equivalent decimal fraction of length n.

This is the reason why you get all those “extra” digits when you print the full decimal value of an IEEE binary floating-point fraction, and why glibc strtod() and Visual C++ strtod() were once broken.

(In the text that follows, I will usually refer to decimal digits as just digits and binary digits as just bits — but where context allows, I will use digits to refer to both generically.)

There Are As Many Digits As Bits

I will prove, in two steps, that every binary fraction has a corresponding decimal fraction of the same length:

1. Show that every binary fraction can be written as a/2ⁿ, where a is a positive integer < 2ⁿ.
2. Show that every fraction of the form a/2ⁿ can be written as a fraction of the form b/10ⁿ, where b is a positive integer < 10ⁿ.

Any fraction with a power of ten denominator represents a decimal fraction, with a number of digits equal to the exponent of the power of ten.

Every Binary Fraction Can Be Expressed As a/2ⁿ

A binary fraction is a finite sum of negative powers of two. For example, 0.00111011011 =

0·2^-1 + 0·2^-2 + 1·2^-3 + 1·2^-4 + 1·2^-5 + 0·2^-6 + 1·2^-7 + 1·2^-8 + 0·2^-9 + 1·2^-10 + 1·2^-11

= 2^-3 + 2^-4 + 2^-5 + 2^-7 + 2^-8 + 2^-10 + 2^-11

= 1/2³ + 1/2⁴ + 1/2⁵ + 1/2⁷ + 1/2⁸ + 1/2¹⁰ + 1/2¹¹.

If a binary fraction has n bits, its lowest weighted bit has a place value of 2^-n, or 1/2ⁿ. For our example, that’s 2^-11, or 1/2¹¹.

The denominator of each term in the series divides 2ⁿ. (The divisors of a nonnegative power of two are all the nonnegative powers of two less than or equal to it.) As such, each term can be rewritten as a fraction with denominator 2ⁿ, with a corresponding power of two numerator. All terms can then be combined into a single value a/2ⁿ. For our example, we’d have

2⁸/2¹¹ + 2⁷/2¹¹ + 2⁶/2¹¹ + 2⁴/2¹¹ + 2³/2¹¹ + 2¹/2¹¹ + 2⁰/2¹¹

= (2⁸ + 2⁷ + 2⁶ + 2⁴ + 2³ + 2¹ + 2⁰)/2¹¹

= (256 + 128 + 64 + 16 + 8 + 2 + 1)/2¹¹

= 475/2¹¹.

(A way to view what we’ve shown: every binary fraction is a multiple of the smallest negative power of two contained within it.)

A Simpler Way

The above proof suggests a simpler way to convert a binary fraction to the form a/2ⁿ. First, treat the digits of the binary fraction as a binary integer, and convert that integer to decimal (ignore superfluous leading zeros). Next, divide that number by 2ⁿ, where n is the number of bits in the binary fraction. For our example, we have 111011011 = 475 as the numerator, and 2¹¹ as the denominator: 475/2¹¹.

Every Binary Fraction Can Be Expressed As b/10ⁿ

This step is trivial: simply multiply a/2ⁿ by 5ⁿ/5ⁿ, getting (a·5ⁿ)/(2ⁿ·5ⁿ) = (a·5ⁿ)/10ⁿ = b/10ⁿ, where b = a·5ⁿ. It has n digits.

For our example, we have (475·5¹¹)/10¹¹ = 23193359375/10¹¹ = 0.23193359375.

We’ve shown that every binary fraction is a decimal fraction with the same number of digits.

Sketch Of Alternate Proof

Having understood the above proof, you can reason towards the answer with this shortcut: Think of each place of the n-bit binary fraction as having the place value 2^-m = 1/2^m = (1/2)^m = (5/10)^m = 5^m/10^m. This makes it obvious from the outset that the binary fraction is equivalent to an n-digit decimal.

There Are More Significant Digits Than Significant Bits

In general, a decimal fraction has more significant digits than its corresponding binary fraction has significant bits. ¹ (A decimal fraction can have an equal number of significant digits, but it can never have less.) This may seem counterintuitive at first, since the opposite is true for integers. The difference in the number of significant digits and significant bits depends on three properties of the binary fraction:

• The starting place of the significant bits.

  For any given combination of length and value of significant bits, the lower the starting place — that is, the more leading zeros, or smaller the number — the more significant digits, in general. For example, 0.000011 = 0.046875 (2 bits to 5 digits), 0.0000011 = 0.0234375 (2 bits to 6 digits), and 0.00000011 = 0.01171875 (2 bits to 7 digits).

  Lowering the starting place won’t always increase the number of significant digits — it may stay the same. For example, continuing the sequence above, 0.000000011 = 0.005859375 (2 bits to 7 digits). The length of the fractions increased by one, but the number of significant digits remained the same; a leading decimal zero accumulated instead.

  As you incrementally lower the starting place, the number of significant digits can increase two or three times in a row, after which a leading decimal zero must be added. From my observations the pattern is: significant digits increase twice in a row, then a leading zero is added; significant digits increase twice in a row, then a leading zero is added; significant digits increase three times in a row, then a leading zero is added. This pattern then repeats. This reflects a ratio of about 7 significant digits to 3 leading zeros, which is expected (this is the same as saying you get about 3 leading decimal zeros for every 10 leading binary zeros — see “Where log₁₀(2) Fits In” below).

  If the binary fraction has no leading zeros, then the decimal fraction won’t either; both will have the same number of significant digits no matter how you vary length or value.

  To emphasize the effect that starting place has on the number of significant digits, consider this example, a very small single-bit number, 2^-100:

  0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

  It has 70 significant digits (and 30 leading zeros):

  0.0000000000000000000000000000007888609052210118054117285652827862296732064351090230047702789306640625.

• The number of significant bits it has.

  For any given starting place, more significant bits equates to more significant digits. For example, 0.0001 = 0.0625 (1 bit to 3 digits), 0.00011 = 0.09375 (2 bits to 4 digits), and 0.000111 = 0.109375 (3 bits to 6 digits). You almost always get just one significant digit per bit, but sometimes you get two (a leading decimal zero is replaced). From my observations, the latter only happens for some starting places, only once per starting place, and only after just a few significant bits.

• The value of the significant bits.

  For any given combination of starting place and number of significant bits, a greater value can lead to more significant digits. For example, 0.000000101 = 0.009765625 (3 bits to 7 digits), and 0.000000111 = 0.013671875 (3 bits to 8 digits). The effect is minimal though, since it can only add up to one significant digit. From my observations, this happens about 30% of the time, when you change the value from its minimum (only its most and least significant bits set) to its maximum (all its bits set).

Counting The Number of Significant Digits

You can count the number of significant digits indirectly by counting the number of leading zeros and then subtracting that from the length of the binary fraction (decimal fraction). The number of leading zeros is easily deduced from the starting place of the significant digits, which is determined using a logarithm.

The starting place of the significant digits of a number x is determined by taking the floor of the logarithm of x to the base i of the number: ⌊log_i(x)⌋. ² This value is the exponent of the power of i of the place containing the most significant digit. (The logarithm is negative, so remember that floor will round it towards negative infinity.) If you negate that value, you get the number of the place (1, 2, 3, etc.) at which the significant digits start, p_i = -⌊log_i(x)⌋. For a binary fraction b, p_b = -⌊log₂(x)⌋; for a decimal fraction d, p_d = -⌊log₁₀(x)⌋. ³

The number of leading zeros z_i is simply the starting place of the significant digits minus one. The number of leading binary zeros is z_b = p_b – 1; the number of leading decimal zeros is z_d = p_d – 1.

Knowing the starting place of the significant digits — and hence the number of leading zeros — and the length n of the binary fraction (decimal fraction), you can compute the number of significant digits s_i = n – z_i. The number of significant bits is s_b = n – z_b; the number of significant digits is s_d = n – z_d.

For example, for b = 0.00111011011, p_b = 3, z_b = 2, and s_b = 9; for d = 0.23193359375, p_d = 1, z_d = 0, and s_d = 11.

Where log₁₀(2) Fits In

For integers, just like for fractions, the logarithm tells you the starting place of the significant digits. But for integers, it tells you more: it also says how many significant digits there are. Furthermore, the ratio of significant digits in one base relative to another is predictable, approaching a constant as the integers get large. For example, the ratio of significant digits to significant bits converges to log₁₀(2) ≈ 0.3.

For fractional values, there is no such relationship. The logarithm does not help you count significant digits. There is no significant digit ratio in any case — it can vary from one to essentially infinite. But from the logarithm you can count leading zeros, and from that you can determine the ratio of leading decimal zeros to leading binary zeros, z_d/z_b, as the numbers get small: log₁₀(2) ≈ 0.3.

The Other Direction: Decimal Fraction To Binary Fraction

All binary fractions are decimal fractions, but the reverse is not true. Some decimal fractions do convert to binary fractions (when put in lowest terms as a fraction their denominator becomes a power of two), so in this case, the above analysis applies.

However, most decimal fractions do not convert to binary fractions, which means that their binary representations are infinite (repeating bicimals as I call them ⁴). The only part of the above analysis that applies is the computation of the starting place of the significant digits, and hence the number of leading zeros.

Footnotes

¹ Significant digits are the digits following the leading zeros of the fraction — don’t think of them as digits of precision.

² I use ⌊log_i(x)⌋ and not ⌈log_i(x)⌉ + 1 because the calculation using ceiling fails when i = 2 and x is a power of two or i = 10 and x is a power of ten.

³ I have not specified how to compute ⌊log_i(x)⌋ programatically, but imagine that x is in an internal binary representation.

⁴ A binary fraction can be called a terminating bicimal, just as a decimal fraction can be called a terminating decimal. In this article, I chose to go with the standard terminology, which I think of as inferior in most contexts.