Get the last 1000 digits of 5^1234566789893943

Question

I saw the following interview question on some online forum. What is a good solution for this?

Get the last 1000 digits of 5^1234566789893943

Answer 1

Simple algorithm:

1. Maintain a 1000-digits array which will have the answer at the end
2. Implement a multiplication routine like you do in school. It is O(d^2).
3. Use modular exponentiation by squaring.

Iterative exponentiation:

array ans;
int a = 5;

while (p > 0) {

    if (p&1) {

       ans = multiply(ans, a)
    }

    p = p>>1;

    ans = multiply(ans, ans);
}

multiply: multiplies two large number using the school method and return last 1000 digits.

Time complexity: O(d^2*logp) where d is number of last digits needed and p is power.