2
$\begingroup$

Is there an efficient way to find the most significant $k$ digits of $2^n$

I tried using the following method:

  1. Compute $n \log2$

  2. Get the fractional part f

  3. 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?

$\endgroup$
2
  • 1
    $\begingroup$ You can always generate $\log 2$ yourself. $\endgroup$
    – dtldarek
    Commented Jul 6, 2013 at 9:08
  • 1
    $\begingroup$ How big is your $n$? You can easily pre-compute your $\log 2$ to very high accuracy, say a 100 digits and store it in your program. If the $k$ you need is small, say you only need the first 14-15 digits representable by ordinary IEEE double. You pre-stored $\log 2$ will allow you to cover $n$ up to $10^{80}$. $\endgroup$
    – achille hui
    Commented Nov 6, 2013 at 10:40

2 Answers 2

Reset to default
2
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ A computer can represent billions of digits internally. $\endgroup$
    – user14972
    Commented Oct 7, 2013 at 8:57
  • $\begingroup$ of course... but the first 15 are easier to get :-) $\endgroup$
    – Emanuele Paolini
    Commented Oct 8, 2013 at 6:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .