1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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




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