Efficiently find the power of number
Finding the power of a number using divide and conquer is an efficient way to calculate the power of a number without doing multiple multiplications. The basic idea is to recursively break down the power into smaller powers until we reach a base case where we can directly compute the result.
The algorithm for finding the power of a number using divide and conquer can be described as follows:
Base case: If the power is 0, return 1. If the power is 1, return the number.
Divide the power by 2 and compute the result recursively for the two halves.
If the power is even, return the product of the two halves. If the power is odd, return the product of the two halves multiplied by the number.
This algorithm has a time complexity of O(log n) since we are halving the power at each recursive step. This is much faster than the naive approach of computing the power using n multiplications, which has a time complexity of O(n).
Here given code implementation process.
// 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
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