Fast Exponentation

We need to compute the value of a^n, for some reasonable large value of n.

The simplest algorithm that we know is computing axaxax ... xa (up to n times). However we can do this better by observing that n = [n/2] * [n/2]. If n is even, then a^n = [a^n/2]^2. If n is odd, then a^n = a * [a^n/2]^2. In either case we have halved the size of our computation. so O(log n) multiplications suffice to compute the final value.

Code :

#include <stdio.h>
int power(int n, int e)
{
        int res;

        if(n == 0)
                return 0;
        if(e == 0)
                return 1;

        res = power(n, e/2);

        if( e%2 ) // ODD
        {
                return n * res * res;
        }
        else // Even
                return res * res;

}
int main()
{
        int number;
        int expon;
        int result;

        printf("Enter the number :");
        scanf("%d", &number);

        printf("Enter the exponent :");
        scanf("%d", &expon);
        result = power(number, expon);

        printf("%d ^ %d is : %d\n", number, expon, result);
        return 0;
}