Skip to main content

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:

  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.

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