C Program to find the result of a Number raised to another Number in Modulo (10 ^ 9) + 7 (For Large Integers) (iterative approach)

 

// Program by Akash Tripathi (@proakash256) 

 

// The remainder obtained after the

// division (%) operation on two operands

// is known as Modulo Operation.

// The reason for taking mod is to prevent

// integer overflows.

// The number should be large enough to fit

// in the largest integer data type and it

// should be prime so as to compute 

// the modulo inverse.

// (10 ^ 9) + 7 fulfills both the criteria.

// Some properties of modulo are :

// 1. (a + b) % M = ((a % M) + (b % M)) % M;

// 2. (a * b) % M = ((a % M) * (b % M)) % M;

// 3. (a - b) % M = ((a % M) - (b % M) + M) % M;

// 4. (a / b) % M = ((a % M) * ((b ^ -1) % M)) % M;

// To find :- (a ^ b)

// Here both a and b are Integers

#include <stdio.h>

long long power(long long c , long long d , int M)

{

    if(d == 0) 

        return 1.0;

    if(d == 1)

        return c;

    long long res = 1;

    while(d > 0)

    {

        if((d & 1) != 0) // (d % 2) != 0 (Condition for Odd)

        {

            res = ((res % M) * (c % M)) % M;

        }

        d = d >> 1; // d = d / 2

        c = ((c % M) * (c % M)) % M;

    }

    return res;

}

int main()

{

    long long a;

    long long b;

    int M = 1000000007;

    printf("Enter the Number : ");

    scanf("%lli" , &a);

    printf("\nEnter the Power : ");

    scanf("%lli" , &b);

    long long res;

    if(b < 0)

    {

        res = power((1 / a) , (-b) , M);

    }

    else

    {

        res = power(a , b , M);           

    }

    printf("\n(%lli ^ %lli) is : %lli\n\n" , a , b , res);

    return 0;

}