Is there a quick way to determine the first k digits on n ^ n

Question

I am writing a program where I need to know only the first k (k can be anywhere between 1-5) the number of another large number, which can be represented as n ^ n, where n is a very large number.

Currently, I actually compute n ^ n and then parse it as a string. I wonder if there is a faster method.

Answer 1

There are two possibilities.

If you want the first k leading digits (as in: the highest digit 12345 is 1), you can use the fact that

n^n = 10^(n*Log10(n)) 

so you calculate the fractional part f of n*Log10(n) , and then your first k digits 10^f will be your result. This works for numbers up to 10 ^ 10 until rounding errors start if you use double precision. For example, for n = 2^20 , f = 0.57466709... , 10^f = 3.755494... , so your first 5 digits are 37554. For n = 4 , f = 0.4082... , 10^f = 2.56 , so your first digit is 2.

If you want the first k lagging digits (as in: the final digit 12345 is 5), you can use modular arithmetic. I would use a square trick:

 factor = n mod 10^k result = 1 while (n != 0) if (n is odd) then result = (result * factor) mod 10^k factor = (factor * factor) mod 10^k n >>= 1 

Taking n = 2 ^ 20 as an example again, we get that result = 88576 . For n = 4, we have factor = 1, 4, 6 and result = 1, 1, 6 , so the answer is 6.

Answer 2

if you mean the least significant or rightmost digits, this can be done using modular multiplication. This is O (N) complexity and does not require any special bignum data types.

 #include <cmath> #include <cstdio> //returns ((base ^ exponent) % mod) int modularExponentiation(int base, int exponent, int mod){ int result = 1; for(int i = 0; i < exponent; i++){ result = (result * base) % mod; } return result; } int firstKDigitsOfNToThePowerOfN(int k, int n){ return modularExponentiation(n, n, pow(10, k)); } int main(){ int n = 11; int result = firstKDigitsOfNToThePowerOfN(3, n); printf("%d", result); } 

This will print 611, the first three digits 11 ^ 11 = 285311670611.

This implementation is suitable for N values ​​less than sqrt (INT_MAX), which will change, but on my machine and language it exceeds 46,000.

Also, if it so happens that your INT_MAX is less than (10 ^ k) ^ 2, you can change modularExponentiation to handle any N that can fit in int:

 int modularExponentiation(int base, int exponent, int mod){ int result = 1; for(int i = 0; i < exponent; i++){ result = (result * (base % mod)) % mod; //doesn't overflow as long as mod * mod < INT_MAX } return result; } 

if O (n) is not enough time for you, we can use the property of raising to the power that A ^ (2 * C) = (A ^ C) ^ 2 and get the logarithmic efficiency.

 //returns ((base ^ exponent) % mod) int modularExponentiation(int base, int exponent, int mod){ if (exponent == 0){return 1;} if (exponent == 1){return base % mod;} if (exponent % 2 == 1){ return ((base % mod) * modularExponentiation(base, exponent-1, mod)) % mod; } else{ int newBase = modularExponentiation(base, exponent / 2, mod); return (newBase * newBase) % mod; } }