How to Find the Mth Digit of 2^n?

[Krypton]

How to find the mth digit of 2^n

 

[CRGreathouse]

If n is small, compute 2^n and look at the mth digit.

If m is small, compute 2^n modulo an appropriate power of your base (e.g. mod 10^9) with binary exponentiation or another efficient method.

If $n\log_{10}2-m$ is small, compute a floating-point approximation of 2^n with similar methods. If you're using a binary computer, this is just a base-10 conversion. If n is sufficiently small and your algorithm is fast, i.e. quasilinear, this is a good method.

Otherwise the calculation will be difficult, both because of the speed required and the memory requirements. You may need a specialized system, because I can't think of any special way to do this.

 

[Krypton]

Is it impossible to find an equation giving the mth digit of 2^n ?

 

[CRGreathouse]

Not at all. The problem is evaluating such an equation quickly.

 

[Krypton]

What do u ment by not at all ? Is it not at all possible? Or not atall imposible?

 

[kts123]

It's possible, but it's silly to bother. There really isn't anything special about base ten, so picking what digit is where is nothing more than a feat of clever arithmetic. Rather, I should say, creating a function which yields a specific digit is silly. Since we define base ten, we might as well pluck the damn thing out with an algorithm.

 

[CRGreathouse]

What do u ment by not at all ? Is it not at all possible? Or not atall imposible?

Easily possible, but pointless. The problem is how to evaluate it quickly.

 

[Ben Niehoff]

I found an algorithm to find the mth digit of 2^n in $\mathcal O(mn^2)$ time (possibly $\mathcal O(mn \log n)$, but I haven't proven it mathematically) using only integer additions (modulo 10). I don't know how this compares to CRGreathouse's suggestions above.

 

[CRGreathouse]

I found an algorithm to find the mth digit of 2^n in $\mathcal O(mn^2)$ time (possibly $\mathcal O(mn \log n)$, but I haven't proven it mathematically) using only integer additions (modulo 10). I don't know how this compares to CRGreathouse's suggestions above.

Adding 1 + 1, 2 + 2, 4 + 4, 8 + 8, (mod 10^m) ... takes n additions, each taking O(m) time, for a total of O(mn).

Multiplying 2 * 2 * ... * 2 (mod 10^m) takes n - 1 multiplications, each taking M(m) time, for a total of O(n^3) or $$O(n^{2.585})$$ with Karatsuba.

Binary exponentiation mod 10^m takes $$O(\lg n)$$ multiplications, each taking M(m) time, for a total of $$O(m\lg^2n)$$ or $$O(m\lg^{1.585}n)$$ with Karatsuba.

The latter two could be improved with FFT-based multiplications methods, but that would be silly here. The real problem is that all of these methods take somewhere around m bytes (m lg 10 bits per number, plus overhead). This can be substantial for large m.

 

[Ben Niehoff]

My algorithm uses at most 4n^2 bits, plus overhead, so I suppose it is worse in both time and space complexity. Oh well. :P

It's quick to do on paper, though.

 

[CRGreathouse]

Would you like to describe your algorithm?