The fast path in David Gay’s decimal to floating-point conversion routine relies on this property of the first twenty-three nonnegative powers of ten: they have exact representations in double-precision floating-point. While it’s easy to see why powers of ten up to 10^{15} are exact, it’s less clear why the powers of ten from 10^{16} to 10^{22} are. To see why, you have to look at their binary representations.

## Trailing Zeros Become “Significantly Insignificant”

10^{15} is the largest power of ten less than 2^{53} – 1, the largest integer representable in 53 bits. 10^{15} has 50 bits, and the next larger power of ten, 10^{16}, has 54 bits. So how can 10^{16} — and the 74-bit 10^{22} for that matter — have an exact double-precision representation, when doubles only store a 53-bit significand? The answer is simple: it has a binary representation with trailing zeros after bit 53.

A nonnegative power of ten 10^{n} equals 5^{n} * 2^{n}; in binary, that’s a power of five followed by n zeros (a power of five always ends in ‘1’). For example, 10^{22} (10000000000000000000000) is

10000111100001100111100000110010011011101010110010010000000000000000000000

This is 5^{22} (2384185791015625), which is 52 bits long, followed by 22 zeros. Here it is in binary scientific notation, showing only its significant bits — the bits of its power of five factor:

1.000011110000110011110000011001001101110101011001001 x 2^{73}

Since this is 52 bits, it maps directly to a double — no rounding is required.

So what happened to the 22 significant trailing zeros? They were preserved in the exponent, as the factor 2^{22}. (The remaining factor, 2^{51}, undoes the normalization.)

### Why 10^{22} Is the Maximum

To see why 10^{22} is the maximum exact power of ten, look at 10^{23}. Its power of five factor is 5^{23} (11920928955078125), which is 54 bits long; this is too long for exact representation in a double.

## 10^{16} to 10^{22}

Here are the powers of ten from 10^{16} to 10^{22}, shown in binary and in binary scientific notation (in the binary representation, bits 54 and beyond are highlighted):

10^{16} |
---|

100011100001101111001001101111110000010000000000000000 |

1.0001110000110111100100110111111000001 x 2^{53} |

10^{17} |
---|

101100011010001010111100001011101100010100000000000000000 |

1.011000110100010101111000010111011000101 x 2^{56} |

10^{18} |
---|

110111100000101101101011001110100111011001000000000000000000 |

1.10111100000101101101011001110100111011001 x 2^{59} |

10^{19} |
---|

1000101011000111001000110000010010001001111010000000000000000000 |

1.00010101100011100100011000001001000100111101 x 2^{63} |

10^{20} |
---|

1010110101111000111010111100010110101100011000100000000000000000000 |

1.0101101011110001110101111000101101011000110001 x 2^{66} |

10^{21} |
---|

1101100011010111001001101011011100010111011110101000000000000000000000 |

1.101100011010111001001101011011100010111011110101 x 2^{69} |

10^{22} |
---|

10000111100001100111100000110010011011101010110010010000000000000000000000 |

1.000011110000110011110000011001001101110101011001001 x 2^{73} |

### On Binary Scientific Notation for Exact Integers

In decimal scientific notation, when trailing zeros are significant, they are displayed. For example, if you know a value to be exactly 300,000, you would write it as 3.00000 x 10^{5}. In binary scientific notation, however, this convention is not followed. I don’t know if there’s an official explanation, but I have my own. Binary scientific notation is used to represent binary floating-point numbers, and binary floating-point numbers are, in general, approximations to decimal numbers. Displaying trailing zeros, which could be the result of rounding, might imply an exactness that’s not there. Also, binary floating-point numbers have a limited length significand; keeping the number of significant bits displayed within this limit makes the mapping clearer.

## Other Large Numbers With Exact Representations

For the same reason, other large numbers — like 14^{18} (greater than 10^{20}), 6^{33} (greater than 10^{25}), and 2^{1023} (greater than 10^{307}) — are exact as doubles. In fact, any integer with a power of two factor that takes it beyond 53 bits can be represented exactly (as long as the maximum exponent isn’t exceeded). In this case, **a double can represent more than 53 significant bits!**

I’m not an expert on floating point format, but I do consider myself an amateur radicologist – studier of number bases. Those things added together meant that after you said “it’s easy to see why powers of ten up to 1015 are exact”, I sort of knew what the answer was going to be. It’s quite a nice trick.

Being a dozenist by preference, I thought it would be nice to find out how far I could go for powers of twelve. Twelve is 2^2 * 3, so that would suggest twice as many trailing zeros. Here goes (in decimal/binary)…

12^22 = 111010011100111010011111000000110010000000000000000000000000000

0000000000000000

Mantissa: 35 bits, easy!

12^36 = 100001010100111110010001101000101110010001110001101101000100000

000000000000000000000000000000000000000000000000000000000000000

0000

Mantissa: 58 bits, too much.

12^32 = 110100101010100111111100010000111100011111010000001000000000000

0000000000000000000000000000000000000000000000000000

Mantissa: 51 bits.

12^34 = 111011001111111100111011110011000100000011001010001001000000000

00000000000000000000000000000000000000000000000000000000000

Mantissa: 53 bits, that’s our limit.

Also, it’s worth mentioning that despite the fact you can get 10^22, multiplying it by anything other than 2 will smeg it up. It’s easy to forget that (although I assume that a lot of your readers will find this obvious).

Anyway, good article. I might come here more often.

| Edited by Rick to format correctly.

James,

Thanks for the comment, and I do hope you come back (consider subscribing through my RSS feed). BTW, did you use my binary converter or another tool?

You might also like http://www.exploringbinary.com/nines-in-binary/ .

Rick

Sorry, I left for almost a month. But I came back to check today, and have subscribed to the RSS feed. I’m currently working my way through some similar posts, and I might comment to let you know.

I think I used WolframAlpha for the binary output. It’s an extremely powerful tool, and is largely unbeatable for calculations and conversions together. While I’ve been away, I’ve developed my own base converter, which can handle arbitrary bases (using any digit set) as well as recurring digital fractions in both the input and output. I’m quite proud, to be honest :-D. Here it is. It’s all in JavaScript, so you can easily snoop around the source if you want.

James,

I’m having a problem using your converter. For one, I can’t get it to work at all in IE (IE8). In Chrome, when I try to enter 0.1111111111111111 in the input box it hangs.

I ought to go through compatibility checks at some time. I’m using a Chromebook at the moment, so it’s a hassle to try it in another browser. As for the hanging, I tried what you said, and it did indeed freeze (when converting decimal to dozenal, at least). Thank you for that, I’ll look into it.