# 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)
{
// Test Case
}
}``````

#### 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()
{
// Test Case
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)
{
// Test Case
}
}``````

#### 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()
{
}
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() :
#  Test Case

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()
{
// Test Case
}
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()
#  Test Case

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()
{
// Test Case
}
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
}
}``````

#### 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
{
// Test Case
}``````

#### 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:

1. If the exponent is 0, the result is always 1.
2. If the exponent is even, the algorithm recursively calculates the power of the base divided by 2 (auxiliary) and returns the square of auxiliary.
3. 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.
4. 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.

## Comment

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.