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)?

You need a better algorithm - think about the underlying maths a little more, instead of just trying to use brute force. — Paul R, Feb 02 '17 at 15:50
Floating point numbers are far to limited in precision for your current solution. — Klas Lindbäck, Feb 02 '17 at 15:55
Hint: read up on [Modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation). — Paul R, Feb 02 '17 at 15:55
You should check the value of `DBL_MAX`, a constant defined in ``, on your system. Odds are, it is many orders of magnitude smaller than the numbers you are trying to deal with. — Random Davis, Feb 02 '17 at 16:09
As for the -8, once `res` becomes infinite, casting it to `int` yields _undefined behavior_ as explained in [What is the result of casting float +INF, -INF, and NAN to integer in C?](http://stackoverflow.com/q/3986795). On my machine the result of the cast is 0x80000000 or -2,147,483,648. That number mod 10 is -8. — Josh Sanford, Feb 02 '17 at 16:51
This can be done very fast with two mods and a 4x10 table lookup. — dbush, Feb 03 '17 at 03:20
@KaranSingh See the link above on modular exponentiation. It follows from that. — dbush, Feb 03 '17 at 11:44

score 1 · Accepted Answer · answered Feb 02 '17 at 16:32

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.

Okay I get the logic. Thanks a lot. One more question: is there any approach to make it more efficient. i am getting a TLE error(Time limit exceeded ) on the online judge :/ — Karan Singh, Feb 02 '17 at 17:28
@KaranSingh When `b % 2^n == 0` then you can divide `b` by `2^n` then iterate using above loop and finally do `res << n` - effectively rising to the power of 2^n (careful, if `n` is too big it would be a problem, so if `n` is bigger than say 30 do `res << 30` then `res %= m` and then `res << n-30`) — Yuriy Ivaskevych, Feb 02 '17 at 18:28
@KaranSingh take a look at this [answer](http://stackoverflow.com/a/39433518/7095889) (from the link you noted in question) particularly at the bottom code — Yuriy Ivaskevych, Feb 02 '17 at 18:33

score 0 · Answer 2 · answered Feb 02 '17 at 15:57

0

See Integer Overflow for why it is a negative number, as for why the value is always -8, well someone smarter than me will answer that one.

answered Feb 02 '17 at 15:57

Adam M.

1,023
1
10
21

Power function in C gives the same output for large numbers

2 Answers2