We need to compute the value of a^

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

*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;

}

## No comments:

## Post a Comment