-1

I have written a code to calculate a to the power of b and then calculate pow(a,b) % 1000000007

1000000007 = pow(10,9) + 7

a and b are integers in range 1 <= a,b <= 10000000

obviously, pow(a,b) is a very huge number so I think overflowing is happening in my code. how can i optimize and fix my code?

    #include <stdio.h>
    #include <math.h>
    unsigned long long int power(unsigned long long int a, unsigned long long int b)
    {
            if (power(a,b) < 1000000007)
            {
                if (b == 1)
                    return a;
                else
                    return a * power(a, b-1);
            }
            else if (power(a,b) == 1000000007)
                return 0;
            else 
                return a * power(a, b-1) % 1000000007;
    }
    int main()
    {
            unsigned long long int a, b;
            scanf("%llu %llu", &a, &b);
            printf("%llu", power(a,b));
            return 0;
    }
miken32
  • 42,008
  • 16
  • 111
  • 154
Fateme
  • 41
  • 4
  • What makes you think an overflow is happening? Please show us an example of the output you're seeing and what you expect. – Chris Apr 15 '23 at 21:22
  • Consider using the efficient [exponentiation](https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int) algorithm, with the modulus applied to each step of the operation. Your recursive solution is about the worst way imaginable. – Weather Vane Apr 15 '23 at 21:47

1 Answers1

2

Here is an efficient exponentiation solution:

#include <stdio.h>

unsigned long long power(unsigned long long base, unsigned long long exp, unsigned modulo)
{
    unsigned long long result = 1;
    base %= modulo;
    for (;;)
    {
        if (exp & 1)
            result = (result * base) % modulo;
        exp >>= 1;
        if (!exp)
            break;
        base = (base * base) % modulo;
    }

    return result;
}

int main(void) {
    unsigned long long int a, b;
    if(scanf("%llu %llu", &a, &b) != 2)
        return 1;
    printf("%llu\n", power(a, b, 1000000007));
    return 0;
}
Weather Vane
  • 33,872
  • 7
  • 36
  • 56
  • 1
    Some minor points. 1) Corner error: `power(2,0,1)` returns 1, when 0 expected: `result = 1;` --> `result %= modulo;` or the like. 2) To handle `unsigned long long module` or when `unsigned` is 64-bit is [work](https://codereview.stackexchange.com/q/187257/29485). 3) problem with 1000000007 when `unsigned` is 16-bit. – chux - Reinstate Monica Apr 15 '23 at 22:21
  • Since `modulo` is `unsigned`, function might as well return `unsigned` instead of `unsigned long long` and use `unsigned result`. – chux - Reinstate Monica Apr 16 '23 at 04:47
  • @chux-ReinstateMonica yes, it's just an example. OP used `long long` so I stayed with that. In the case of modulo 1, I would trap that earlier, since all results will be `0`. – Weather Vane Apr 16 '23 at 07:51