0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.