Skip to main content

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:

  1. Base case: If the power is 0, return 1. If the power is 1, return the number.

  2. Divide the power by 2 and compute the result recursively for the two halves.

  3. 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
Last updated on by Kalkicode




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.

New Comment