Power function in C gives the same output for large numbers

Question

The problem statement requires me to find out the last digit of a^b. The constraints are that 0 <= a <= 20 and 0 <= b <= 2,147,483,000.

My code works pretty well for numbers like 12^8 or 6^9 or something similar. But when I move to the large number territory, something like 14^1234 or 17^148713, I am always getting an output of -8.

#include <stdio.h>
#include <math.h> 
int main() {
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int a;
        long long int b;
        double x, y, res;
        scanf("%d %lld", &a, &b);
        x=(double)a;
        y=(double)b;
        res = pow(x, y);
        int rem;
        rem = (int)res%10;
        printf("%d\n", rem);
    }
    return 0; }

What could be the reasons for such a weird output?

Is there no way out apart from storing the big numbers in an array (I guess something like How to calculate 2 to the power 10000000)?

Answer 1

int can hold values up to and including 2^31 - 1 so you basically have an overflow (actually it is causing Undefined Behaviour in contrast to overflowing unsigned types).

As already pointed out by @PaulR in comments to your question the general idea is to abuse certain properties of modular exponentiation. In short: you need to keep numbers 'small enough' to prevent overflow and to be able to get desired result.

We can use the folowing property: (a * b) % m == (a % m) * (b % m). In code it can look like this:

const unsigned int m = 10;  // our modulus
while(t--)
{
    ...                     // read 'a' and 'b'

    unsigned int res = 1;   // last digit of a^b (e.g. res == (a^b % m))
    for (unsigned int i = 0; i < b; ++i)
    {
        res *= a;           // rising to power i
        res %= m;           // keep res small !
    }

    ...                     // you get desired result
}

Note: declare a and b as unsigned int - this would be enough for your limits and would prevent unnessesary and unwanted convertions between signed and unsigned.