Calculation of power of a number i.e. a^n or also called as exponent of a number - which means how many times to use a number in multiplication
Example :
7^4 - means 7 to fourth power
- means use 7 four times in multiplication
- means 7x7x7x7
A negative exponent on the other hand means, how many times to divide a number.
So a^-n = 1/a^n
There are different ways to implement. We will discuss about each algorithm and then write appropriate function for the same.
Algorithm 1 :
Let us talk about the simplest of the algorithm. power(a,n) literally means n times a
1. Accept number and power.
2. Multiply number with number itself power number of times.
3. Display final result.
Example : Power (3,5) = 3*3*3*3*3
So using this approach takes n-1 calculations to be performed.
float result = 1; // result value
for (powerItr = 1; powerItr <= tempPower; powerItr++)
{
result *= f_number;
}
Algorithm 2 :
So far above method looks simple and logical. But, there is an optimisation for the above method.
Let us take the same example from above algorithm 1
Power (3,5) = 3*3^4 // have to perform only one operation.
= 3*3^2*3^2 // have to perform only 2 operations.
= 3*3*3*3*3 // usual method where n-1 operations were performed.
So the steps for the algorithm would be as follows :
1. If the power of a number is even call power(a,n/2)*power(a,n/2).
2. else if power is odd call a*power(n/2)*power(n/2)
3. repeat steps 1 and 2 until power becomes 0. For power 0, return 1.
So using above approach takes O(logn) calculations.
Algorithm 3 :
We can achieve somewhat performance improvement in above algorithm by using bitwise operator. The number of iterations that are performed are decreasing as the power increases. This is what we do to achieve power for a number using bitwise operator
1. We take the number
2. If the last bit of power is 1 - then we multiply result with number
3. Right shift power by 1.
4. multiply number by itself.
5. Repeat steps 2-4 unless power becomes 0.
Test function
Example :
7^4 - means 7 to fourth power
- means use 7 four times in multiplication
- means 7x7x7x7
A negative exponent on the other hand means, how many times to divide a number.
So a^-n = 1/a^n
There are different ways to implement. We will discuss about each algorithm and then write appropriate function for the same.
Algorithm 1 :
Let us talk about the simplest of the algorithm. power(a,n) literally means n times a
1. Accept number and power.
2. Multiply number with number itself power number of times.
3. Display final result.
Example : Power (3,5) = 3*3*3*3*3
So using this approach takes n-1 calculations to be performed.
/* simplePower
* Description : A function that calculates power of number by using multplication.
* Parameters : f_number - number for which power needs to be calculated
* i_power - power of a number
* Returns : float - power of number.
*/
float simplePower(float f_number, int i_power)
{
// Initialisation
register int powerItr; // Variable to traverse from 1 to n-1
register int tempPower = abs(i_power); // Take positive power.float result = 1; // result value
{
result *= f_number;
}
// If power is negative number - we need to divide 1 by the final result
return i_power<0 ? 1.0/result : result;
}
Algorithm 2 :
So far above method looks simple and logical. But, there is an optimisation for the above method.
Let us take the same example from above algorithm 1
Power (3,5) = 3*3^4 // have to perform only one operation.
= 3*3^2*3^2 // have to perform only 2 operations.
= 3*3*3*3*3 // usual method where n-1 operations were performed.
So the steps for the algorithm would be as follows :
1. If the power of a number is even call power(a,n/2)*power(a,n/2).
2. else if power is odd call a*power(n/2)*power(n/2)
3. repeat steps 1 and 2 until power becomes 0. For power 0, return 1.
So using above approach takes O(logn) calculations.
/* recursivePower
* Description : Calculates power of number by using recursive function call.
* Parameters : f_number - number for which power needs to be calculated
* i_power - power of a number
* Returns : float - power of number.
*/
float recursivePower(float f_number, int i_power)
{
float tempPower;
// Power 0 results in 1
if (0 == i_power)
{
return 1;
}
// Calculate f_number^(i_power/2)
tempPower = recursivePower(f_number, i_power/2);
// Check if power is even -
// multiply temp power to itself to calculate f_number^i_power
if (0 == (i_power%2))
{
return tempPower*tempPower;
}
// Otherwise multiply f_number once again.
else
{
// If power is negative - divide by number
if (i_power<0)
return (tempPower*tempPower)/f_number;
else
return f_number*tempPower*tempPower;
}
}
We can achieve somewhat performance improvement in above algorithm by using bitwise operator. The number of iterations that are performed are decreasing as the power increases. This is what we do to achieve power for a number using bitwise operator
1. We take the number
2. If the last bit of power is 1 - then we multiply result with number
3. Right shift power by 1.
4. multiply number by itself.
5. Repeat steps 2-4 unless power becomes 0.
/* bitwisePower
* Description : Calculates power of number by using bitwise operator.
* Parameters : f_number - number for which power needs to be calculated
* i_power - power of a number
* Returns : float - power of number.
*/
float bitwisePower(float f_number, int i_power)
{
// Initialise
register int tempPower = abs(i_power); // Take positive power.
float result = 1; // result value
// Until power becomes 0
while (tempPower)
{
// Check if last bit of power is 1.
// If yes, update the result.
if (tempPower&1)
{
result *= f_number;
}
// Move on to next bit
tempPower >>=1 ;
// update number
f_number *= f_number;
}
return i_power<0 ? 1/result : result;
}
Test function
int main()
{
// Initialisation
float f_number;
int i_power;
// Accept values
printf("Enter number and its power to be calculated : ");
scanf("%f %d",&f_number,&i_power);
// Calculate power
printf("Simple %g^%d: %g\n",f_number,i_power,simplePower(f_number,i_power));
printf("Recursive %g^%d: %g\n",f_number,i_power,recursivePower(f_number,i_power));
printf("Bitwise %g^%d: %g\n",f_number,i_power,bitwisePower(f_number,i_power));
}
Sample Output :
Enter number and its power to be calculated : 2 4
Simple 2^4: 16
Recursive 2^4: 16
Bitwise 2^4: 16
Enter number and its power to be calculated : 2 -4
Simple 2^-4: 0.0625
Recursive 2^-4: 0.0625
Bitwise 2^-4: 0.0625
Enter number and its power to be calculated : 3.2 3
Simple 3.2^3: 32.768
Recursive 3.2^3: 32.768
Bitwise 3.2^3: 32.768
No comments:
Post a Comment