I have two integers named $n$ and $k$. I want to find the first and last three significant digits of $n^k$.
Here $n$ and $k$ can be very large ($2 \le n < 2^{31}$ and $1 \le k \le 10^7$). What can I do in order to get the first and last $3$ significant digits of $n^k$.
I have found a way to get the most significant digits of $N^M$. The procedure is as follows :
- I have to use logarithms.
- If $X=N^M$, compute $z=3+(\log X \bmod 1)$ (base of log is $10$) and then round $y=10^z$ down to the next integer.
This should work for $X\ge 10^3$ and should give a correct answer in IEEE arithmetic for the desired range of $N$ and $M$. For smaller $X$, just compute it directly.
But what should I do in order to get the least $3$ significant digits of $n^k$?
Best Answer
The least significant 3 digits of $n^k$ are also the least significant 3 digits of
$$n^k \pmod{1000}$$