C implementation of exponentiation by squaring

Question

I tried to implement the "exponentiation by squareing" algorithmn in C but my program has an odd behaviour. First, here is a small code snippet:

long long fast_power_1(long long base, long long power){
    long long result = 1;
    while (power > 0)
    {
        if (power % 2 == 0)
        {
            power = power / 2;
            base = base * base;
        }
        else
        {
            power = power - 1;
            result = (result*base);
            power = power / 2;
            base = (base * base);
        }
    }
return result;}

If I call the function with:

printf("%d\n",fast_power_1(2,100));

I expect the output to be something like 976371285, but the result is 0 and i don't quite understand why.

Answer 1

long long should be printed using %lld format specifier otherwise it's Undefined Behavior. Also this method already has overflow within for large values of power - because long long cant hold 2^100(as of now in 32 or 64 bit systems- when it is 128 bit system of course it can).

As of now in your code if you provide not too large value of the exponent and use printf("%lld",..) then it would give you a valid result.

Maybe you wanted to have modular arithmetic with it. (In general requirements stop at that - like modulo some large prime i.e, 10^9+7 ).