To truly understand decimal to binary and binary to decimal conversion, you should know how the powers of ten and the powers of two relate. In particular, you should know how they are interleaved. The interleaving explains why, for example, the number of bits required to represent an n-digit decimal integer varies. Consequently, it also explains why 9,007,199,254,740,991 (253 – 1) is representable in binary floating-point, and why 9,007,199,254,740,993 (253 + 1) is not.
In this article, I will discuss the interleaving of the positive powers of ten and two, and prove some properties of it. (The interleaving of the negative powers is the mirror image of the positive powers, centered around 100 = 20 = 1.)
Powers of Ten and Two Meet Only Once
One is the only number that is both a power of ten and a power of two. One way to see this is to compare the ending digits of the remaining powers:
- Positive powers of ten end in 0; positive powers of two end in 2, 4, 6, or 8.
- Negative powers of ten end in 1; negative powers of two end in 5.
This means that all the other powers are interleaved.
Nonnegative Powers of Ten and Two in Logarithmic Scale
It’s easier to see the relationship between powers of ten and powers of two when you draw them on a number line in logarithmic scale:
In logarithmic scale, a fixed linear distance represents a fixed factor; as such, powers of ten are equidistant from one another, as are powers of two.
In the diagram, let d10 be the linear distance between powers of ten, and d2 be the linear distance between powers of two. d10 and d2 are related as such:
d10 = log2(10) · d2 ≈ 3.32 · d2
or
d2 = log10(2) · d10 ≈ 0.3 · d10
This shows that the distance between consecutive powers of ten is greater than the distance spanned by three consecutive powers of two. Multiplying a power of ten by two three times, in terms of the diagram, would bring it only approximately 3 · 0.3 = 0.9 of the way to the next power of ten.
This diagram may add insight:
Each tick mark represents 1/10 of the distance between powers of ten, and represents a factor of 101/10, or approximately 1.26. Going right one tick mark is multiplication by approximately 1.26; going left is division by approximately 1.26. Three tick marks represent a factor of 103/10, or approximately 2, so nine tick marks represent approximately three factors of two.
There are Three or Four Powers of Two Between Powers of Ten
Given the above relationship, you’ll see that there will be three or four powers of two between every consecutive pair of powers of ten. Whether it’s three or four depends on where the first power of two in the interval falls.
In my diagram above, you can see there are four powers of two between 103 and 104. (There are four powers of two in the interval [100, 101), but since 100 = 20, I won’t count that as “between”.) A span of four powers of two represents a factor of 8 (the first one is not a factor; it’s just the starting point). Under what conditions do four powers of two occur between powers of ten?
Let p10n and p10n+1 be consecutive powers of ten, and let p2m be the least power of two greater than p10n. Four powers of two appear between p10n and p10n+1 when p2m < 1.25 · p10n; three powers of two appear when p2m > 1.25 · p10n (p2m can never be equal to 1.25 · p10n ; multiplying it by 8 would make it a power of two and power of ten).
For example, there are four powers of two between 103 and 104 because 210 = 1024 is less than 1.25 · 103 = 1250; there are three powers of two between 102 and 103 because 27 = 128 is greater than 1.25 · 102 = 125.
On the Factor 1.25
I got the factor 1.25 by recognizing that 1.25 · 8 = 10. In terms of my logarithmic scale diagram, 1.25 is just slightly less than one power of ten tick mark in length.
Four Powers of Two Never Occur Twice in a Row
There are never two consecutive power of ten intervals that contain four powers of two each. The constraint on where the first power of two must occur cannot be met in back-to-back intervals.
Assume there are four powers of two between p10n and p10n+1; call them p2m , p2m+1 , p2m+2 , and p2m+3. Here’s why there can’t be four powers of two between p10n+1 and p10n+2:
- The first power of two, p2m, satisfies the inequality p10n < p2m < 1.25 · p10n
- The first power of two in the next power of ten interval, p2m+4, satisfies the inequality 16 · p10n < p2m+4 < 20 · p10n (I multiplied everything by 24 = 16)
- That inequality can be rewritten as 1.6 · p10n+1 < p2m+4 < 2 · p10n+1 (I pulled a factor of ten out of each constant to reflect the crossing of a power of ten boundary)
- That inequality says that p2m+4 starts after 1.6 · p10n+1, which means that there can’t be four powers of two between p10n+1 and p10n+2
Three Powers of Two Can Occur Three Times in a Row
So as not to bog you (or me) down in symbols, let’s prove this less formally:
- Assume the worst case start for the first power of two in a three power of two range, just below 2 · p10n
- The worst case start for the first power of two in the next power of ten range will be just below 1.6 · p10n+1
- The worst case start for the first power of two in the next power of ten range will be just below 1.28 · p10n+2, just barely meeting the criteria for a three power of two range.
- The worst case start for the first power of two in the next power of ten range will be just below 1.024 · p10n+3, which means four powers of two will occur in that range.
All told, three powers of two occurred in three consecutive power of ten ranges.
Here’s an example where this occurs
- Between 1028 and 1029, since 294 ≈ 1.98 · 1028
- Between 1029 and 1030, since 297 ≈ 1.58 · 1029
- Between 1030 and 1031, since 2100 ≈ 1.27 · 1030
The three powers of two run stops there because 2103 ≈ 1.01 · 1031.
(I observed patterns in consecutive power of two counts, but I will not state or prove them here.)
Relating to Decimal/Binary Conversion
The interleaving of powers explains some properties of decimal to binary and binary to decimal conversions.
Decimal to Binary Conversion
In decimal to binary conversion, a given d-digit decimal integer may convert to a binary integer of four or five different lengths. If three powers of two occur between 10d-1 and 10d, all or part of four power of two ranges span that power of ten range; if four powers of two occur between 10d-1 and 10d, all or part of five power of two ranges span it. (This doesn’t apply to 1-digit decimal integers, since 100 = 20 — there are four powers of two, but only all or part of four power of two ranges.)
As for my example in the introduction, 9,007,199,254,740,991 and 9,007,199,254,740,993 both have 16 decimal digits, but the latter is not representable in double-precision binary floating-point. 16-digit integers lie between 1015 and 1016 – 1, and that span contains four powers of two: 250 , 251 , 252 , and 253 . Double-precision stores only 53 bits, which means it can only represent integers up to 253 – 1 = 9,007,199,254,740,991 exactly. 16-digit decimal integers greater than or equal to 253 require 54 bits.
(Actually, because of how floating-point numbers work — specifically that they have an associated power of two exponent — some integers beyond 253 – 1 will be exactly representable. In this case, half of the 16-digit/54-bit integers — the even ones —will be exact.)
Binary to Decimal Conversion
In terms of binary to decimal conversion, swap your viewpoint and think in terms of where powers of ten fall between powers of two:
This is the same diagram as above, only with the labeling reversed: the powers of two are more prominently displayed. On this diagram, it’s a bit easier to see that at most one power of ten can appear between powers of two. This means that a b-bit binary integer may convert to a decimal integer of one or two lengths.
>>(I observed patterns in consecutive power of two counts, but I will not state or prove them here.)<<
Probably what I found: The pattern is 3,3,4… until 2^93. Then there is one 3,3,3,4 and 3,3,4… resumes until 2^186 which begins 3,3,3,4 again.
I was not able to see if 2^93n is generally the start of 3 3s.
Walter
Walter,
Yes, that’s what I saw. Furthermore, I found that between each ‘3334’ sequence there were either 8 or 9 ‘334’ sequences. It looked like the pattern of 8 vs 9 went ‘88989’ (repeating), but that was just based on how far I looked.
Thanks for checking in.
I looked how close 2^n comes to 10^m in the formula D= ABS(2^n-10^m)/10^m where D is the fractional difference and n and m are integers. I found for n=485, m=146, D = .0010. That was the lowest value of D for n from 1 to 1000.
Walter,
We must be on the same wavelength — but I’ve got you beat. I have a PARI script that I used to provide evidence for my proofs. I looked closer at the output I saved from it and found these lines (I only went to 10978 — I don’t remember why I stopped there):
10^146 from 2^485 = 1.0010415 (the one you found)
10^643 to 2^2136 = 1.0001629
10^789 from 2^2621 = 1.0008785
BTW, I did a straight ratio, either 2^n/10^m (“to”) or 10^m/2^n (“from”).
Update: I just ran it a little longer and found these two:
10^4004 from 2^13301 = 1.0000637
10^4647 to 2^15437 = 1.0000992
Update 2:
10^97879 to 2^325147 = 1.0000004
(OK, I’ll quit now.)
Walter,
It’s interesting. As the ratio approaches 1, the ratio of the exponents, n/m, approaches log2(10):
2n/10m = 1
2n = 10m
n = m · log2(10)
n/m = log2(10)
Of course 2n/10m can never be 1, because the powers would be equal.
The following description is probably clumsy and possibly even wrong.
The numbers A= 2^(n+10*m) where n is a constant from n=0 to 9 and m is serially 0, 1, 2, 3… eg 2^7, 2^17, 2^27… , give values for B=(2^(n+10*m)-10^c)/10^c where 10^c is the closest number to A. Plotting B vs A gives a smooth curve that rises to about .8 then drops to about -.8 and repeats that pattern with a period of 2^970. The pattern is similar for each value of n, but displaced along the 2^(n+10m) axis.. The points close to the zero axis are the minima that we found. These minima for equal values of n are 2^970 apart, but sometimes 980, ie m=97 or 98.
I hope that is clear enough that you can see what I am trying to say.
First correction: I did not plot B vs A, but B vs n+10*m. The pattern repeats with a periodicity of m=97 or 98, not 2^970.
The 3,3,4,3,3,4 pattern is a Beatty sequence and cannot have a period. However, using Benford’s law it is possible to deduce that, if a very long section of the sequence were split into pieces ending in 4, then we can expect that the longer (3,3,3,4) would be 10.628372% of the pieces.