Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mth digit of 2^n

  1. Jul 3, 2008 #1
    How to find the mth digit of 2^n
     
  2. jcsd
  3. Jul 3, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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 [itex]n\log_{10}2-m[/itex] 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.
     
  4. Jul 4, 2008 #3
    Is it impossible to find an equation giving the mth digit of 2^n ?
     
  5. Jul 4, 2008 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Not at all. The problem is evaluating such an equation quickly.
     
  6. Jul 5, 2008 #5
    What do u ment by not at all ? Is it not at all possible? Or not atall imposible?
     
  7. Jul 6, 2008 #6
    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.
     
  8. Jul 6, 2008 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Easily possible, but pointless. The problem is how to evaluate it quickly.
     
  9. Jul 6, 2008 #8

    Ben Niehoff

    User Avatar
    Science Advisor
    Gold Member

    I found an algorithm to find the mth digit of 2^n in [itex]\mathcal O(mn^2)[/itex] time (possibly [itex]\mathcal O(mn \log n)[/itex], 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.
     
  10. Jul 6, 2008 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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 [tex]O(n^{2.585})[/tex] with Karatsuba.

    Binary exponentiation mod 10^m takes [tex]O(\lg n)[/tex] multiplications, each taking M(m) time, for a total of [tex]O(m\lg^2n)[/tex] or [tex]O(m\lg^{1.585}n)[/tex] 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.
     
  11. Jul 7, 2008 #10

    Ben Niehoff

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  12. Jul 7, 2008 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Would you like to describe your algorithm?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Mth digit of 2^n
Loading...