CODEWITHSUNDEEP
algorithmnumerical-methods
Eastern Monk
Eastern Monk

Reputation: 6635

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

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

Currently I am actually calculating n^n and then parsing it as a string. I wonder if there is a better more fast method exists.

Upvotes: 7

Views: 2920

Answers (2)

Jeffrey Sax
Jeffrey Sax

Reputation: 10313

There are two possibilities.

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

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

so you compute the fractional part f of n*Log10(n), and then the first k digits of 10^f will be your result. This works for numbers up to about 10^10 before round-off errors start kicking in 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 trailing digits (as in: the trailing digit of 12345 is 5), then you can use modular arithmetic. I would use the squaring 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 find that result = 88576. For n=4, we have factor = 1, 4, 6 and result = 1, 1, 6 so the answer is 6.

Upvotes: 11

Kevin
Kevin

Reputation: 76194

if you mean the least significant or rightmost digits, this can be done with modular multiplication. It's O(N) complexity and doesn't 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 of 11^11 = 285311670611.

This implementation is suitable for values of N less than sqrt(INT_MAX), which will vary but on my machine and language it's over 46,000.

Furthermore, 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 an 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) time is insufficient for you, we can take advantage of the property of exponentiation that A^(2*C) = (A^C)^2, and get 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;
    }
}

Upvotes: 3

Related Questions