Why Powers of Ten Up to 1022 Are Exact As Doubles

http://www.exploringbinary.com/why-powers-of-ten-up-to-10-to-the-22-are-exact-as-doubles/


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 1015 are exact, it’s less clear why the powers of ten from 1016 to 1022 are. To see why, you have to look at their binary representations.

Trailing Zeros Become “Significantly Insignificant”

1015 is the largest power of ten less than 253 – 1, the largest integer representable in 53 bits. 1015 has 50 bits, and the next larger power of ten, 1016, has 54 bits. So how can 1016 — and the 74-bit 1022 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 10n equals 5n * 2n; in binary, that’s a power of five followed by n zeros (a power of five always ends in ‘1’). For example, 1022 (10000000000000000000000) is

10000111100001100111100000110010011011101010110010010000000000000000000000

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

1.000011110000110011110000011001001101110101011001001 x 273

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 222. (The remaining factor, 251, undoes the normalization.)

Why 1022 Is the Maximum

To see why 1022 is the maximum exact power of ten, look at 1023. Its power of five factor is 523 (11920928955078125), which is 54 bits long; this is too long for exact representation in a double.

1016 to 1022

Here are the powers of ten from 1016 to 1022, shown in binary and in binary scientific notation (in the binary representation, bits 54 and beyond are highlighted):

1016
100011100001101111001001101111110000010000000000000000
1.0001110000110111100100110111111000001 x 253
1017
101100011010001010111100001011101100010100000000000000000
1.011000110100010101111000010111011000101 x 256
1018
110111100000101101101011001110100111011001000000000000000000
1.10111100000101101101011001110100111011001 x 259
1019
1000101011000111001000110000010010001001111010000000000000000000
1.00010101100011100100011000001001000100111101 x 263
1020
1010110101111000111010111100010110101100011000100000000000000000000
1.0101101011110001110101111000101101011000110001 x 266
1021
1101100011010111001001101011011100010111011110101000000000000000000000
1.101100011010111001001101011011100010111011110101 x 269
1022
10000111100001100111100000110010011011101010110010010000000000000000000000
1.000011110000110011110000011001001101110101011001001 x 273

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 105. 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 1418 (greater than 1020), 633 (greater than 1025), and 21023 (greater than 10307) — 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!

Dingbat

5 Responses to “Why Powers of Ten Up to 1022 Are Exact As Doubles”

  1. James Says:

    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.

  2. Rick Regan Says:

    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

  3. James Says:

    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.

  4. Rick Regan Says:

    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.

  5. James Says:

    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.

Leave a Comment

(To reduce spam, cookies must be enabled)


css.php