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
    Is their a lower bound to n and m like there is an upper bound?2012-08-19
  • 1
    Also what language is this? If this is general mathematics, then this belongs on Mathematics.2012-08-19
  • 0
    In ACM, we are supposed to use PASCAL/C/C++/JAVA.Either is OK.2012-08-19
  • 0
    There is no lower bound, it can be [1, 10^100].2012-08-19
  • 0
    `2^n` will work as long as n isn't bigger than the number of bits in the integer type. I've never heard of a 10000 bit integer :/2012-08-19
  • 0
    Suppose we can only use 64-bit numbers, or smaller.2012-08-19
  • 0
    We usually use array to represent a huge number to handle this kind of problem, but useless in this prob.2012-08-19
  • 0
    Why not use a bignum library?2012-08-19
  • 0
    is `m` guaranteed to be greater or equal to `n`?2012-08-19
  • 0
    @Anurag That shouldn't matter. Since all it does it flip the sign.2012-08-19
  • 0
    @Mysticial - I think it matters because a solution may not actually calculate the entire answer. So flipping the sign may not be as easy.2012-08-19
  • 0
    @Anurag Yes,it is guaranteed. I'll put this in the prob. Thanks.2012-08-19
  • 0
    The only feasible way I can think of is to store several most significant bit + the exponent for all calculations. Not sure if there is any case that this is incorrect.2012-08-19
  • 0
    @Cole There are a number of very high quality bigint libraries which can take 10k-bit integers in their stride…2012-08-19
  • 0
    @DonalFellows However 2^(10^100) is a _lot_ bigger than 10k-bit integers will handle. If every person on earth had 1 million computers each with a million gigs of ram .. you still wouldn't go close to fitting that number into all that memory as a simple int. As other answers have mentioned you need to use exponential ranges to get anywhere.2012-08-19
  • 1
    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.2012-08-19
  • 0
    @MichaelAnderson oh yah. I was thinking 10*100. Keep in mind "(2^x)" is just "(1<2012-08-19
  • 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.

  • 3
    No arbitrary precision library is going to like 2^(10^100). You're going to need a lot of ram to support that.2012-08-19
  • 0
    @MichaelAnderson: Hard problems requires massive resources. That's just the way it is.2012-08-19
  • 3
    @MichaelAnderson: a good arbitrary precision library won't have any problems with these numbers at all. 2^(10^100) ~ 2.551789e+3010299956639811952137388947244930267681898814621085413104274611271081892744245094869272521181861720. You don't need to store every digit, only enough that the interval is tight enough to confirm the first few digits.2012-08-19
  • 0
    @DSM you're correct. I'm used to thinking of "arbitrary precision" as meaning all digits.2012-08-19
  • 0
    @DSM Realistically speaking, most of the major bignum libraries only use 64-bit integers for their exponents. What you would need is a bignum for the exponent as well. But that doesn't stop you from taking one and hacking it to work.2012-08-19
  • 1
    @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).2012-08-19
  • 0
    @MichaelAnderson: as I said, you need as many digits as you need to ensure that the interval of possible values is tight enough. Since I'm lazy, I wouldn't even bother working out how many I'd need beforehand: I'd simply do the computation at some low precision, see whether or not the [interval](http://en.wikipedia.org/wiki/Interval_arithmetic) confirms the first few digits, and if not, repeat at higher precision. But this is very much a brute force approach, and there's probably a slick base-2 related one instead.2012-08-19
  • 0
    @DSM, I guess what I'm saying is that its possible that in some (very rare) cases you'll need to be tracking more digits than is feasible, to get an accurate enough representation. This is why I'm scared of solutions that just say "Just use a good bignum library".2012-08-19
  • 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.

  • 2
    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?2012-08-19
  • 0
    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.2012-08-19
  • 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
    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.2012-08-21
  • 0
    @MichaelAnderson That's fair enough, but at least that effect can only change the answer by $1$.2012-08-21
  • 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...