# Computing first k digits and last k digits of a large number using logarithm

How do we compute the first $k$ digits and last $k$ digits of a large number say $2^{N-1}$ for bigger values of $N$ using logarithms? An example for the algorithm will be greatly appreciated. I got this task in a programming contest and here is the editorial where the method is explained but I don't understand this well.

Now to get the last $k$ digits of $2^{N-1}$. We can use simple divide and conquer technique and can use modulo $10^{k-1}$ . So in this way we will get the last $k$ digits. As for large values of $N$, the value of $2^{N-1}$ will be very large and to get last first $k$ digits we can easily use the logarithm, which will give result which will be correct enough to get first $k$ digits correctly.

To calculate the last $$k$$ digits, you can simply calculate the number modulo $$10^k$$. For example, using $$2^n$$ as the number, you must start with 1 and keep multiplying by 2 $$n$$ times, calculating the result modulo $$10^k$$ whenever an intermediate step exceeds $$10^k$$, to speed up calculations.

To calculate the first $$k$$ digits, note that you need to calculate the integer part of $$\frac{N}{10^{\lfloor \log(N)\rfloor + 1 - k}}$$; as an example, to calculate the first 3 digits of 1234567, you need to find the integer part of $$\frac{1234567}{10^{7-3}} = 123.4567$$. Now, the logarithm of this number is equal to $$\log(N) - \log(10^{\lfloor \log(N)\rfloor + 1 - k}) = \log(N) - \lfloor \log(N) \rfloor -1 + k$$. This latter number is easily calculable, and raising 10 to the answer, you get the first $$k$$ digits.

• ideone.com/pYDjHD can u comment this code for better understanding – satyajeet jha Apr 4 '16 at 2:47
• @satya You should probably ask that question at StackOverflow – shardulc Apr 4 '16 at 2:51
• For computing powers with a large exponent, use the algorithm that uses squaring when it can. – marty cohen Apr 4 '16 at 3:42

As an example, suppose $N=12345$, and $b=2^{12344}$.

$\log_{10} b = 12344\cdot\log_{10} 2=12344\times 0.301029995663981195\dots\approx3715.9142664761839$. The first few digits are the same as the first few digits (ignoring the decimal place) of $10^{0.9142664761839}$ and between the first few digits of $10^{0.9142664761838}$ and $10^{0.9142664761840}$, which are each $820855053441$.

The last (10, say) digits can be computed by working out $2^{12344}$ modulo $10^{10}$. $2^{1}, 2^{10}, 2^{100}, 2^{1000}, \mbox{ and } 2^{10000} \mbox{ mod } 10^{10}$ are $2, 1024, 6703205376, 5668069376$, and $2596709376$, respectively, so

$2^{12344}\mbox{ mod }10^{10}\equiv(2596709376\cdot5668069376^2\cdot6703205376^3\cdot1024^4\cdot2^4)\mbox{ mod }10^{10}$, which turns out to be $4106172416$. Therefore

$$2^{12344} = 820855053441\dots4106172416.$$