Efficiently find the power of number
Calculating the power of a number is a common mathematical operation used in various applications. It involves multiplying a number (base) by itself a certain number of times (exponent). While this can be achieved through iterative multiplication, an efficient approach can significantly reduce computation time.
Problem Statement:
The goal is to develop an efficient algorithm to calculate the power of a number given the base and exponent. The algorithm should handle positive, negative, and zero exponents correctly and provide accurate results.
Pseudocode Algorithm:
function power(base, exponent):
if exponent equals 0:
return 1
auxiliary = power(base, exponent / 2)
if exponent is even:
return auxiliary * auxiliary
else if exponent is greater than 0:
return base * auxiliary * auxiliary
else:
return (auxiliary * auxiliary) / base
function calculatePow(base, exponent):
print "Given Base: " + base
print "Given Exponent: " + exponent
print "Result: " + power(base, exponent)
Code Solution
// C program for
// Efficiently find the power of number
#include <stdio.h>
// Find the power of given base and exponent
float power(float base, int exponent)
{
if (exponent == 0)
{
// When exponent zero
return 1;
}
// finding the power using recursion
float auxiliary = power(base, exponent / 2);
if (exponent % 2 == 0)
{
return auxiliary *auxiliary;
}
else if (exponent > 0)
{
// When exponent greater than zero
return base *auxiliary *auxiliary;
}
else
{
// When exponent less than zero
return (auxiliary *auxiliary) / base;
}
}
// Handle request to display calculate power result
void calculatePow(float base, int exponent)
{
// Display given data
printf("\n Given Base : %f", base);
printf("\n Given exponent : %d", exponent);
// Display calculated result
printf("\n Result : %f\n", power(base, exponent));
}
int main()
{
// Test Case
calculatePow(3.5, 4);
calculatePow(5, -3);
calculatePow(5, 3);
return 0;
}
Output
Given Base : 3.500000
Given exponent : 4
Result : 150.062500
Given Base : 5.000000
Given exponent : -3
Result : 0.008000
Given Base : 5.000000
Given exponent : 3
Result : 125.000000
// Java Program
// Efficiently find the power of number
public class PowerNumber
{
// Find the power of given base and exponent
public float power(float base, int exponent)
{
if (exponent == 0)
{
// When exponent zero
return 1;
}
// finding the power using recursion
float auxiliary = power(base, exponent / 2);
if (exponent % 2 == 0)
{
return auxiliary * auxiliary;
}
else if (exponent > 0)
{
// When exponent greater than zero
return base * auxiliary * auxiliary;
}
else
{
// When exponent less than zero
return (auxiliary * auxiliary) / base;
}
}
// Handle request to display calculate power result
public void calculatePow(float base, int exponent)
{
// Display given data
System.out.print("\n Given Base : " + base);
System.out.print("\n Given exponent : " + exponent);
// Display calculated result
System.out.print("\n Result : " + power(base, exponent) + "\n");
}
public static void main(String[] args)
{
PowerNumber task = new PowerNumber();
// Test Case
task.calculatePow(3.5f, 4);
task.calculatePow(5, -3);
task.calculatePow(5, 3);
}
}
Output
Given Base : 3.5
Given exponent : 4
Result : 150.0625
Given Base : 5.0
Given exponent : -3
Result : 0.008
Given Base : 5.0
Given exponent : 3
Result : 125.0
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Efficiently find the power of number
class PowerNumber
{
public:
// Find the power of given base and exponent
float power(float base, int exponent)
{
if (exponent == 0)
{
// When exponent zero
return 1;
}
// finding the power using recursion
float auxiliary = this->power(base, exponent / 2);
if (exponent % 2 == 0)
{
return auxiliary *auxiliary;
}
else if (exponent > 0)
{
// When exponent greater than zero
return base *auxiliary *auxiliary;
}
else
{
// When exponent less than zero
return (auxiliary *auxiliary) / base;
}
}
// Handle request to display calculate power result
void calculatePow(float base, int exponent)
{
// Display given data
cout << "\n Given Base : " << base;
cout << "\n Given exponent : " << exponent;
// Display calculated result
cout << "\n Result : " << this->power(base, exponent) << "\n";
}
};
int main()
{
PowerNumber task = PowerNumber();
// Test Case
task.calculatePow(3.5f, 4);
task.calculatePow(5, -3);
task.calculatePow(5, 3);
return 0;
}
Output
Given Base : 3.5
Given exponent : 4
Result : 150.062
Given Base : 5
Given exponent : -3
Result : 0.008
Given Base : 5
Given exponent : 3
Result : 125
// Include namespace system
using System;
// C# Program
// Efficiently find the power of number
public class PowerNumber
{
// Find the power of given base and exponent
public float power(float b, int exponent)
{
if (exponent == 0)
{
// When exponent zero
return 1;
}
// finding the power using recursion
float auxiliary = power(b, exponent / 2);
if (exponent % 2 == 0)
{
return auxiliary * auxiliary;
}
else if (exponent > 0)
{
// When exponent greater than zero
return b * auxiliary * auxiliary;
}
else
{
// When exponent less than zero
return (auxiliary * auxiliary) / b;
}
}
// Handle request to display calculate power result
public void calculatePow(float b, int exponent)
{
// Display given data
Console.Write("\n Given Base : " + b);
Console.Write("\n Given exponent : " + exponent);
// Display calculated result
Console.Write("\n Result : " + power(b, exponent) + "\n");
}
public static void Main(String[] args)
{
PowerNumber task = new PowerNumber();
// Test Case
task.calculatePow(3.5f, 4);
task.calculatePow(5, -3);
task.calculatePow(5, 3);
}
}
Output
Given Base : 3.5
Given exponent : 4
Result : 150.0625
Given Base : 5
Given exponent : -3
Result : 0.008
Given Base : 5
Given exponent : 3
Result : 125
<?php
// Php Program
// Efficiently find the power of number
class PowerNumber
{
// Find the power of given base and exponent
public function power($base, $exponent)
{
if ($exponent == 0)
{
// When exponent zero
return 1;
}
// finding the power using recursion
$auxiliary = $this->power($base, ($exponent / 2));
if ($exponent % 2 == 0)
{
return $auxiliary * $auxiliary;
}
else if ($exponent > 0)
{
// When exponent greater than zero
return $base * $auxiliary * $auxiliary;
}
else
{
// When exponent less than zero
return (($auxiliary * $auxiliary) / $base);
}
}
// Handle request to display calculate power result
public function calculatePow($base, $exponent)
{
// Display given data
echo "\n Given Base : ". $base;
echo "\n Given exponent : ". $exponent;
// Display calculated result
echo "\n Result : ". $this->power($base, $exponent) ."\n";
}
}
function main()
{
$task = new PowerNumber();
$task->calculatePow(3.5, 4);
$task->calculatePow(5, -3);
$task->calculatePow(5, 3);
}
main();
Output
Given Base : 3.5
Given exponent : 4
Result : 150.0625
Given Base : 5
Given exponent : -3
Result : 0.008
Given Base : 5
Given exponent : 3
Result : 125
# Python 3 Program
# Efficiently find the power of number
class PowerNumber :
# Find the power of given base and exponent
def power(self, base, exponent) :
if (exponent == 0) :
# When exponent zero
return 1
# finding the power using recursion
auxiliary = self.power(base, int(exponent / 2))
if (exponent % 2 == 0) :
return auxiliary * auxiliary
elif(exponent > 0) :
# When exponent greater than zero
return base * auxiliary * auxiliary
else :
# When exponent less than zero
return ((auxiliary * auxiliary) / base)
# Handle request to display calculate power result
def calculatePow(self, base, exponent) :
# Display given data
print("\n Given Base : ", base, end = "")
print("\n Given exponent : ", exponent, end = "")
# Display calculated result
print("\n Result : ", self.power(base,exponent) )
def main() :
task = PowerNumber()
# Test Case
task.calculatePow(3.5, 4)
task.calculatePow(5, -3)
task.calculatePow(5, 3)
if __name__ == "__main__": main()
Output
Given Base : 3.5
Given exponent : 4
Result : 150.0625
Given Base : 5
Given exponent : -3
Result : 0.008000000000000002
Given Base : 5
Given exponent : 3
Result : 125
// Node Js Program
// Efficiently find the power of number
class PowerNumber
{
// Find the power of given base and exponent
power(base, exponent)
{
if (exponent == 0)
{
// When exponent zero
return 1;
}
// finding the power using recursion
var auxiliary = this.power(base, parseInt(exponent / 2));
if (exponent % 2 == 0)
{
return auxiliary * auxiliary;
}
else if (exponent > 0)
{
// When exponent greater than zero
return base * auxiliary * auxiliary;
}
else
{
// When exponent less than zero
return ((auxiliary * auxiliary) / base);
}
}
// Handle request to display calculate power result
calculatePow(base, exponent)
{
// Display given data
process.stdout.write("\n Given Base : " + base);
process.stdout.write("\n Given exponent : " + exponent);
// Display calculated result
process.stdout.write("\n Result : " + this.power(base, exponent) + "\n");
}
}
function main()
{
var task = new PowerNumber();
// Test Case
task.calculatePow(3.5, 4);
task.calculatePow(5, -3);
task.calculatePow(5, 3);
}
main();
Output
Given Base : 3.5
Given exponent : 4
Result : 150.0625
Given Base : 5
Given exponent : -3
Result : 0.008000000000000002
Given Base : 5
Given exponent : 3
Result : 125
# Ruby Program
# Efficiently find the power of number
class PowerNumber
# Find the power of given base and exponent
def power(base, exponent)
if (exponent == 0)
# When exponent zero
return 1
end
# finding the power using recursion
auxiliary = self.power(base, (exponent / 2).ceil)
if (exponent % 2 == 0)
return auxiliary * auxiliary
elsif(exponent > 0)
# When exponent greater than zero
return base * auxiliary * auxiliary
else
# When exponent less than zero
return (auxiliary * auxiliary) / base
end
end
# Handle request to display calculate power result
def calculatePow(base, exponent)
# Display given data
print("\n Given Base : ", base)
print("\n Given exponent : ", exponent)
# Display calculated result
print("\n Result : ", self.power(base, exponent) ,"\n")
end
end
def main()
task = PowerNumber.new()
# Test Case
task.calculatePow(3.5, 4)
task.calculatePow(5, 3)
end
main()
Output
Given Base : 3.5
Given exponent : 4
Result : 150.0625
Given Base : 5
Given exponent : 3
Result : 125
// Swift 4 Program
// Efficiently find the power of number
class PowerNumber
{
// Find the power of given base and exponent
func power(_ base: Double, _ exponent: Int)->Double
{
if (exponent == 0)
{
// When exponent zero
return 1;
}
// finding the power using recursion
let auxiliary: Double = self.power(base, exponent / 2);
if (exponent % 2 == 0)
{
return auxiliary * auxiliary;
}
else if (exponent > 0)
{
// When exponent greater than zero
return base * auxiliary * auxiliary;
}
else
{
// When exponent less than zero
return (auxiliary * auxiliary) / base;
}
}
// Handle request to display calculate power result
func calculatePow(_ base: Double, _ exponent: Int)
{
// Display given data
print("\n Given Base : ", base, terminator: "");
print("\n Given exponent : ", exponent, terminator: "");
// Display calculated result
print("\n Result : ", self.power(base,exponent) );
}
}
func main()
{
let task: PowerNumber = PowerNumber();
// Test Case
task.calculatePow(3.5, 4);
task.calculatePow(5, -3);
task.calculatePow(5, 3);
}
main();
Output
Given Base : 3.5
Given exponent : 4
Result : 150.0625
Given Base : 5.0
Given exponent : -3
Result : 0.008
Given Base : 5.0
Given exponent : 3
Result : 125.0
// Scala Program
// Efficiently find the power of number
class PowerNumber
{
// Find the power of given base and exponent
def power(base: Float, exponent: Int): Float = {
if (exponent == 0)
{
// When exponent zero
return 1;
}
// finding the power using recursion
var auxiliary: Float = this.power(base, (exponent / 2));
if (exponent % 2 == 0)
{
return auxiliary * auxiliary;
}
else if (exponent > 0)
{
// When exponent greater than zero
return base * auxiliary * auxiliary;
}
else
{
// When exponent less than zero
return ((auxiliary * auxiliary) / base);
}
}
// Handle request to display calculate power result
def calculatePow(base: Float, exponent: Int): Unit = {
// Display given data
print("\n Given Base : " + base);
print("\n Given exponent : " + exponent);
// Display calculated result
print("\n Result : " + this.power(base, exponent) + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PowerNumber = new PowerNumber();
// Test Case
task.calculatePow(3.5f, 4);
task.calculatePow(5, -3);
task.calculatePow(5, 3);
}
}
Output
Given Base : 3.5
Given exponent : 4
Result : 150.0625
Given Base : 5.0
Given exponent : -3
Result : 0.008
Given Base : 5.0
Given exponent : 3
Result : 125.0
// Kotlin Program
// Efficiently find the power of number
class PowerNumber
{
// Find the power of given base and exponent
fun power(base: Float, exponent: Int): Float
{
if (exponent == 0)
{
// When exponent zero
return 1.0f;
}
// finding the power using recursion
var auxiliary: Float = this.power(base, exponent / 2);
if (exponent % 2 == 0)
{
return auxiliary * auxiliary;
}
else if (exponent > 0)
{
// When exponent greater than zero
return base * auxiliary * auxiliary;
}
else
{
// When exponent less than zero
return (auxiliary * auxiliary) / base;
}
}
// Handle request to display calculate power result
fun calculatePow(base: Float, exponent: Int): Unit
{
// Display given data
print("\n Given Base : " + base);
print("\n Given exponent : " + exponent);
// Display calculated result
print("\n Result : " + this.power(base, exponent) + "\n");
}
}
fun main(args: Array < String > ): Unit
{
var task: PowerNumber = PowerNumber();
// Test Case
task.calculatePow(3.5f, 4);
task.calculatePow(5f, -3);
task.calculatePow(5f, 3);
}
Output
Given Base : 3.5
Given exponent : 4
Result : 150.0625
Given Base : 5.0
Given exponent : -3
Result : 0.008
Given Base : 5.0
Given exponent : 3
Result : 125.0
Explanation:
The algorithm for calculating the power of a number efficiently uses recursion and the concept of halving the exponent. By repeatedly dividing the exponent by 2, the number of multiplications required is significantly reduced. The algorithm has three main cases:
- If the exponent is 0, the result is always 1.
- If the exponent is even, the algorithm recursively calculates the power of the base divided by 2 (auxiliary) and returns the square of auxiliary.
- If the exponent is odd, the algorithm recursively calculates the power of the base divided by 2 (auxiliary) and returns the product of base, auxiliary, and auxiliary.
- If the exponent is negative, the algorithm calculates the power with a positive exponent and then divides 1 by the result.
The algorithm handles both positive and negative exponents efficiently by reducing the number of multiplications required.
Resultant Output Explanation:
The provided code demonstrates the usage of the algorithm by calculating the power of different numbers with varying exponents:
- For the input base 3.5 and exponent 4, the result is 150.062500.
- For the input base 5 and exponent -3, the result is 0.008000.
- For the input base 5 and exponent 3, the result is 125.000000.
The output matches the expected results for each test case, indicating that the algorithm is correctly implemented.
Time Complexity
The time complexity of the algorithm is logarithmic, specifically O(log n), where n is the exponent. The algorithm reduces the exponent by half in each recursive call, resulting in a more efficient computation compared to iterative multiplication, which would have a time complexity of O(n).
Finally:
In this article, we discussed an efficient algorithm to calculate the power of a number. By leveraging recursion and halving the exponent, the algorithm significantly reduces the number of multiplications required. We provided a step-by-step explanation of the algorithm, demonstrated its usage through sample code, and explained the output. Additionally, we highlighted the logarithmic time complexity of the algorithm, making it a favorable approach for computing the power of a number.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment