9
$\begingroup$

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$.)

  • 0
    @SeanEberhard - What makes you think that the first 3 digits must be the same in that case? Here's a counter example: 2^2136 = 1000016... yet 2^2136 - 2^2124 = 9999187...2012-08-21

6 Answers 6

0

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$.
2

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.

  • 1
    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.2012-08-19
2

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.

  • 0
    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.2012-08-19
2

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.

  • 0
    The difference between "100" and "999" is not 1.2012-08-21
1

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?

0

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...