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.
Best Answer
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.