CODEWITHSUNDEEP
calgorithmmath
Suvasish Sarker
Suvasish Sarker

Reputation: 435

Optimized way to handle extremely large number without using external library

Optimized way to handle the value of n^n (1 ≤ n ≤ 10^9)

I used long long int but it's not good enough as the value might be (1000^1000)

Searched and found the GMP library http://gmplib.org/ and BigInt class but don't wanna use them. I am looking for some numerical method to handle this.

I need to print the first and last k (1 ≤ k ≤ 9) digits of n^n

For the first k digits I am getting it like shown below (it's bit ugly way of doing it)

num = pow(n,n);
while(num){
    arr[i++] = num%10;
    num /= 10;
    digit++;
}
while(digit > 0){
    j=digit;
    j--;
    if(count<k){
        printf("%lld",arr[j]);
        count++;
    }
    digit--;
}

and for last k digits am using num % 10^k like below.

findk=pow(10,k);
lastDigits = num % findk;
enter code here

maximum value of k is 9. so i need only 18 digits at max. I am think of getting those 18 digits without really solving the complete n^n expression.

Any idea/suggestion??

Upvotes: 1

Views: 1642

Answers (3)

sowrov
sowrov

Reputation: 1050

Finding the Least Significant Digits (last k digits) are easy because of the property of modular arithmetic, which says: (n*n)%m == (n%m * n%m)%m, so the code shown by BLUEPIXY which followed exponentiation by squaring method will work well for finding k LSDs.

Now, Most Significant Digits (1st k digits) of N^N can be found in this way:

 We know, 
 N^N = 10^(N log N)

So if you calculate N log (N) you will get a number of this format xxxx.yyyy, now we have to use this number as a power of 10, it is easily understandable that xxxx or integer part of the number will add xxxx zeros after 10, which is not important for you! That means, if you calculate 10^0.yyyy, you will get those significants digits you are looking for. So the solution will be something like this:

double R = N * log10 (N);
R = R - (long long) R; //so taking only the fractional part
double V = pow(10, R);
int powerK = 1;
for (int i=0; i<k; i++) powerK *=10;
V *= powerK;
//Now Print the 1st K digits from V

Upvotes: 4

BLUEPIXY
BLUEPIXY

Reputation: 40155

// note: Scope of use is limited.

#include <stdio.h>

long long powerMod(long long a, long long d, long long n){
// a ^ d mod n
    long long result = 1;
    while(d > 0){
        if(d & 1)
            result = result * a % n;
        a = (a * a) % n;
        d >>=1;
    }
    return result;
}

int main(void){
    long long result = powerMod(999, 999, 1000000000);//999^999 mod 10^9
    printf("%lld\n", result);//499998999

    return 0;
}

Upvotes: 5

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

Why don't you want to use bigint libraries?

bignum arithmetic is very hard to do right and efficiently. You could still get a PhD by working on that subject.

Fist, bigint arithmetic have non-trivial algorithmics

Then, bigint implementations usually need some machine instructions (like add with carry) which are not easily accessible in plain C.

For your specific problem (first and last few digits of NN) you'll better also reason on paper (using arithmetic theorems) to lower the complexity. I am not an expert, but I guess that still remains intractable, perhaps with a complexity worse than O(N)

Upvotes: 0

Related Questions