First $ k $ digits of $2^{n}$ Is there an efficient way to find the most significant $k$ digits of $2^n$
I tried using the following method:


*

*Compute $n \log2$

*Get the fractional part f

*Compute $10^{f+k-1}$
This should be the required answer.This does work for small numbers, but for very large n, the precision of this method falls appreciably due to the fact that it is very difficult to have exact $\log{2}$
Is there an easier and efficient algorithm?
 A: Computing $2^n$ with the computer is very easy, you just have to evaluate 1 << n, whereby << is the bit shift operator to the left.
In a programming language like Python, you also do not have problems with overflows of your integer value (which might be the case in C or C++). Python automatically converts the integer for you.
To compute for example the first 20 digits of $2^{100000}$ in Python, you have to type:
str(1 << 100000)[0:20]

which evaluates to
'99900209301438450794'

On my computer, computing 1 << 100000 =$2^{100000}$ in Python was really fast, but for $n=1000000$ the calculation took a while. So you will need a better algorithm, if $n$ is very, very large.
In programming languages which do not automatically convert integers, if they get to big, you need to find a data type, which can hold arbitrary high values. In Java you can use for example the class BigInteger.
If $n$ is smaller than the amount of bits of your integer variable, you have no problems with integer overflows. In Java you can use ((long)1) << n, iff $n\le 63$ (in Java the integer type long has 64 bits, but the first one is used for the sign).  
A: If you want to skip $m$ digits you have to compute
$$
    \lfloor\frac{2^n}{10^m}\rfloor = \lfloor 10^{n\frac{\log 2}{\log 10}-m}\rfloor
$$
with this formula you get as many correct digits as the computer can represent internally, so I would say about 15 correct digits.
