Is there any way to determine the first $3$ digits of $2^m-2^n$ ($n\leq m\leq 10^{100}$)

It's a problem in my ACM training.

Since $n,m$ are really huge, I don't think the algo $2^n=10^{n\log2}$ will work. Also, it's not really wise to calculate the value of $2^n$, I think. So I stack.

Can any one come up with a way? Thanks.

e.g.: $m=16$, $n=12$, and the answer is $614$.
($2^{16}=65536$, $2^{12}=4096$, $65536-4096=61440$.)

-

migrated from stackoverflow.comAug 19 '12 at 13:33

This question came from our site for professional and enthusiast programmers.

Is their a lower bound to n and m like there is an upper bound? –  Cole Johnson Aug 19 '12 at 3:40
Also what language is this? If this is general mathematics, then this belongs on Mathematics. –  Cole Johnson Aug 19 '12 at 3:41
In ACM, we are supposed to use PASCAL/C/C++/JAVA.Either is OK. –  MForever78 Aug 19 '12 at 3:42
There is no lower bound, it can be [1, 10^100]. –  MForever78 Aug 19 '12 at 3:44
Just a recommendation to improve this question: Note that the first three digits of $2^m-2^n$ are just the first three digits of $2^m$, unless $m-n\leq 10$. Since these cases comprise extremely few of the pairs $(m,n)$ in question, I would leave out $n$ all together. Moreover, all the difficulty in the problem seems to be present in the single case $m=10^{100}$, so I would ask just about this case. In other words, I would ask simply "What are the first three digits of $2^{10^{100}}$?. This question is bound to attract useful answers more rapidly. –  Sean Eberhard Aug 19 '12 at 15:40

I think $2^n=10^{n\lg2}$ does help.

It gives you the first digits of $2^n$ and $2^m$ and their respective number of digits. Assuming you have n and m in scientific notation with sufficient precision. And what is better you can improve the precision of the respective result incrementally as needed using the algorithm used when multiplying numbers by hand.

So a proposed algorithm works like this:

• calculate $2^n$ and $2^m$ using the formula above and the first $k$ digits of $\lg2$.

• calculate the same values again but now increase the last digit of your approximation of $\lg2$ by one, thus giving you upper and lower bound of the two terms.

• using those calculate upper and lower bound of the final result.

• if the first 3 digits of the two approximations are the same you are done

• otherwise increase number of digits used and repeat.

As hinted above you should be able to reuse results from the previous iteration.

Alternatively you could use @Anurag s result + the formular above + the suggested estimation of errors, thus adding powers of 2 until sufficient precision is reached. You'll have to deal with an arbitrary (but fast becomming irrelevant) number of terms instead of 2 though.

-
Sorry I didn't really get it.Since m and n are really huge, for example, 10^99, how can I use the formula when I can't even store the number to a variable? –  MForever78 Aug 19 '12 at 5:54
You just need the first digits of it. And their difference in length. For this you could just 'assume' that a given number of digits is sufficient (like 20, which most likely is) or you read it in using streams, where you can pull in one digit at a time. –  Jens Schauder Aug 19 '12 at 6:09
One step in doing this might be to work out n ln(2)/ln(10) and then take the largest integer <= this and call it k. This would allow you to work out ln(10^k) and subtract it from ln(2^n). After doing this you could easily work out the first few digits of 2^n. But for large n k is also very large so I don't think ordinary floating point will work. If this is a solution, it is a way to make a calculation with extended precision more practical, not a way to do with with ordinary floating point. –  mcdowella Aug 19 '12 at 7:58

You'll need to use an arbitrary precision math library. But there's one great simplification:

Assuming m > n:
2^m - 2^n = 2^n [ 2^(m-n) - 1]

So with m = 16 and n = 12:
2^12 [ 2^4 - 1 ] = (4096)(16 - 1) = 4096 x 15 = 61440.

Computing 2^12 and 2^4 and then doing one multiplication is easier than computing 2^16 and 2^12.

-
No arbitrary precision library is going to like 2^(10^100). You're going to need a lot of ram to support that. –  Michael Anderson Aug 19 '12 at 3:55
@MichaelAnderson: Hard problems requires massive resources. That's just the way it is. –  David Schwartz Aug 19 '12 at 3:57
@MichaelAnderson: a good arbitrary precision library won't have any problems with these numbers at all. 2^(10^100) ~ 2.551789e+3010299956639811952137388947244930267681898814621085413104274611271081‌​892744245094869272521181861720. You don't need to store every digit, only enough that the interval is tight enough to confirm the first few digits. –  DSM Aug 19 '12 at 3:58
@DSM How do you know how many digits you need? Consider this low valued case : pow(2,2136) - pow(2,2124) = 9999187..., here 2^2136 = 1000016... and tracking just the top 4 or 5 digits is not sufficient to get the right answer. While such "tricky" cases are rare, there are values of n that will give 2^n a form of 1 followed by an arbitrarily large number of zeros. (Not sure what the longest such string for n<10^100 will be though - maybe tracking the top couple of hundred digits will suffice - maybe not). –  Michael Anderson Aug 19 '12 at 4:29
You don't actually need to "do the multiplication" since multiplying a number by 2^n is the same shifting it bitwise to the left by n positions. –  jmbr Aug 19 '12 at 10:59

Note $2^m - 2^n = (1-1/2^{m-n}) 2^m$. The first factor can usually be ignored, or else dealt with straight-forwardly. Let's just think about $m=10^{100}$.

What are the first three digits of $2^{10^{100}}$?

If $x$ is the fractional part of $\log_{1000} 2^{10^{100}} = 10^{100}\log_{1000}2$, then the answer is the integer part of $1000^x$. You need to know $1000^x$ within a distance $1$, so you need to know $x$ within a distance $\log_{1000}1.001 \leq 0.0002$ You therefore just need to know the first $100$ digits or so of $\log_{1000}2$, which can be found here (press "more digits" a lot).

I find that $x \approx 0.80228$, so $\lfloor 1000^x\rfloor = 255$.

It might be wise to store the digits of $\log_{1000} 2$, especially if you want to carry out several of these computations.

-
That second factor is the tricky bit. There are cases where it underflows in a nasty way. The example I;m citing is : 2^2136 = 1000016... yet 2^2136 - 2^2124 = 9999187.... My suspicions is that these kind of degenerate cases happen regularly enough that the accuracy required to make your approach work in all cases is infeasible. –  Michael Anderson Aug 21 '12 at 0:13
@MichaelAnderson That's fair enough, but at least that effect can only change the answer by $1$. –  Sean Eberhard Aug 21 '12 at 8:34
The difference between "100" and "999" is not 1. –  Michael Anderson Aug 21 '12 at 9:07

Not sure if this would work:

2^x1 - 2^x2 = 2^(x1 - x2) * (2^x2 - 2^(2*x2 - x1) )

let x3 = x2 and x4 = 2*x2 - x1

then

2^x1 - 2^x2 = 2^(x1 - x2) * (2^x3 - 2^x4)

= 2^(x1 - x2) * 2^(x3 - x4) * 2^(x5 - x6) ..

= 2^(x1 - x2 + x3 - x4 + x5 - x6)

so inclusion exclusion?

-

I think you can do this by representing numbers as A * 10^B, where both A and B fit in the lower half of a 64-bit int (so multiplication is easy) and B is only needed some of the time, and then only correct up to an unknown offset.

Write 2^m - 2^n = 2^n * (1 + 2 + 4 + .. 2^(m-n-1)) and do the calculation in two stages:

1) calculate 2^n by repeated squaring

2) Accumulate 2^n + 2^(n+1) + .. 2^(m-1)

If m is much larger than n then just use stage 1 to compute 2^m.

For the first stage you don't need to keep track of powers of 10 at all - just divide A through by some power of 10 to keep it just below 2^32, to make sure multiplication doesn't overflow.

For the second stage, you need to know the relative size of 2^k and 2^(k-1)+2^(k-2)... - but these are almost the same size, so a perfectly ordinary integer will keep track of the difference between the number of powers of 10 used to scale 2^k and those used to scale 2^(k-1)+...

At the end you have roughly 32 bits of precision of the answer you need, up to multiplication by an unknown power of 10. This should be enough to work out the 3 most significant digits of the answer, unless you are very unlucky and it is very close to the gap between 9999... and 10000...

-

Computing the first leading digit of $2^n$ efficiently is an open problem, as far as I know. The sequence in OEIS was computed up to $n=10^6$ far (FAR) away from $10^{100}$. And this is simpler than your problem for $2^m-2^0$ that requires 3 digits.

So two possibilities :

1. The question is asked to see what you can do on a very difficult problem (probably one without solution known)
2. This is not the 3 leading digits but the 3 trailing digits, so you can compute the solution very quickly modulo $10^3$.
-