Tuesday, June 10, 2008

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;

No comments:

Post a Comment