Posted on by Kalkicode
Code Mathematics

Calculate power without using division and multiplication

Calculating the power of a number is a fundamental mathematical operation. This involves multiplying a base number by itself a certain number of times (the exponent). In some scenarios, you might want to perform this calculation without using the division and multiplication operations explicitly. This can be useful in situations where these operations are not readily available or are relatively expensive in terms of computational resources.

Problem Statement

The problem is to calculate the power of a given base number to a given exponent without using the division and multiplication operations. Instead, we need to come up with an alternative method that achieves the same result.

Idea to Solve the Problem

One way to solve this problem is by utilizing the property that any exponentiation can be expressed as a series of multiplications. For instance, if we want to calculate 2^6, we can represent it as:

2^6 = 2 * 2 * 2 * 2 * 2 * 2

In this approach, we need to find an alternative way to perform these multiplications without using the * operator. The code you've provided attempts to achieve this goal.

Pseudocode

function power(base, exponent)
    result = base
    update = base
    
    loop from 1 to exponent - 1
        loop from 1 to base - 1
            result = result + update
        update = result
    
    return result

Algorithm Explanation

  1. Initialize two variables, result and update, both set to the given base value. These variables will be used to keep track of the ongoing calculation.

  2. Start a loop that iterates exponent - 1 times. This is because the first multiplication is already accounted for in the initialization.

  3. Inside the outer loop, start another loop that iterates base - 1 times. This simulates the process of multiplication by repeatedly adding the update value to the result.

  4. After the inner loop completes, the result holds the accumulated value as if we performed multiplication base times. Update the update variable with the new result.

  5. Repeat the above steps until the outer loop finishes, effectively raising the base to the given exponent.

  6. Finally, return the result as the calculated value of base raised to the power of exponent.

Code Solution

// C program for 
// Calculate power without using division and multiplication
#include <stdio.h>

// This is calculating the power of given positive integers
void power(int base, int pow)
{
	// Define some resultant variable
	int result = base;
	int update = base;
	// Execute loop through by given power
	for (int i = 1; i < pow; ++i)
	{
		//  Execute loop through by given base number
		for (int j = 1; j < base; ++j)
		{
			// Calculate power
			result = result + update;
		}
		// Change
		update = result;
	}
	// Display calculated result
	printf(" (%d ^ %d) = %d\n", base, pow, result);
}
int main(int argc, char
	const *argv[])
{
	// Test Case
	power(2, 6);
	power(4, 5);
	power(1, 5);
	return 0;
}

input

 (2 ^ 6) = 64
 (4 ^ 5) = 1024
 (1 ^ 5) = 1
/*
  Java Program for
  Calculate power without using division and multiplication
*/
public class PowerOfNumber
{
	// This is calculating the power of given positive integers
	public void power(int base, int pow)
	{
		// Define some resultant variable
		int result = base;
		int update = base;
		// Execute loop through by given power
		for (int i = 1; i < pow; ++i)
		{
			//  Execute loop through by given base number
			for (int j = 1; j < base; ++j)
			{
				// Calculate power
				result = result + update;
			}
			// Change
			update = result;
		}
		// Display calculated result
		System.out.println(" (" + base + " ^ " + pow + ") = " + result);
	}
	public static void main(String[] args)
	{
		PowerOfNumber task = new PowerOfNumber();
		// Test Case
		task.power(2, 6);
		task.power(4, 5);
		task.power(1, 5);
	}
}

input

 (2 ^ 6) = 64
 (4 ^ 5) = 1024
 (1 ^ 5) = 1
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for
  Calculate power without using division and multiplication
*/
class PowerOfNumber
{
	public:
		// This is calculating the power of given positive integers
		void power(int base, int pow)
		{
			// Define some resultant variable
			int result = base;
			int update = base;
			// Execute loop through by given power
			for (int i = 1; i < pow; ++i)
			{
				//  Execute loop through by given base number
				for (int j = 1; j < base; ++j)
				{
					// Calculate power
					result = result + update;
				}
				// Change
				update = result;
			}
			// Display calculated result
			cout << " (" << base << " ^ " << pow << ") = " << result << endl;
		}
};
int main()
{
	PowerOfNumber *task = new PowerOfNumber();
	// Test Case
	task->power(2, 6);
	task->power(4, 5);
	task->power(1, 5);
	return 0;
}

input

 (2 ^ 6) = 64
 (4 ^ 5) = 1024
 (1 ^ 5) = 1
// Include namespace system
using System;
/*
  Csharp Program for
  Calculate power without using division and multiplication
*/
public class PowerOfNumber
{
	// This is calculating the power of given positive integers
	public void power(int baseValue, int pow)
	{
		// Define some resultant variable
		int result = baseValue;
		int update = baseValue;
		// Execute loop through by given power
		for (int i = 1; i < pow; ++i)
		{
			//  Execute loop through by given base number
			for (int j = 1; j < baseValue; ++j)
			{
				// Calculate power
				result = result + update;
			}
			// Change
			update = result;
		}
		// Display calculated result
		Console.WriteLine(" (" + baseValue + " ^ " + pow + ") = " + result);
	}
	public static void Main(String[] args)
	{
		PowerOfNumber task = new PowerOfNumber();
		// Test Case
		task.power(2, 6);
		task.power(4, 5);
		task.power(1, 5);
	}
}

input

 (2 ^ 6) = 64
 (4 ^ 5) = 1024
 (1 ^ 5) = 1
<?php
/*
  Php Program for
  Calculate power without using division and multiplication
*/
class PowerOfNumber
{
	// This is calculating the power of given positive integers
	public	function power($base, $pow)
	{
		// Define some resultant variable
		$result = $base;
		$update = $base;
		// Execute loop through by given power
		for ($i = 1; $i < $pow; ++$i)
		{
			//  Execute loop through by given base number
			for ($j = 1; $j < $base; ++$j)
			{
				// Calculate power
				$result = $result + $update;
			}
			// Change
			$update = $result;
		}
		// Display calculated result
		echo " (".$base.
		" ^ ".$pow.
		") = ".$result.
		"\n";
	}
}

function main()
{
	$task = new PowerOfNumber();
	// Test Case
	$task->power(2, 6);
	$task->power(4, 5);
	$task->power(1, 5);
}
main();

input

 (2 ^ 6) = 64
 (4 ^ 5) = 1024
 (1 ^ 5) = 1
/*
  Node JS Program for
  Calculate power without using division and multiplication
*/
class PowerOfNumber
{
	// This is calculating the power of given positive integers
	power(base, pow)
	{
		// Define some resultant variable
		var result = base;
		var update = base;
		// Execute loop through by given power
		for (var i = 1; i < pow; ++i)
		{
			//  Execute loop through by given base number
			for (var j = 1; j < base; ++j)
			{
				// Calculate power
				result = result + update;
			}
			// Change
			update = result;
		}
		// Display calculated result
		console.log(" (" + base + " ^ " + pow + ") = " + result);
	}
}

function main()
{
	var task = new PowerOfNumber();
	// Test Case
	task.power(2, 6);
	task.power(4, 5);
	task.power(1, 5);
}
main();

input

 (2 ^ 6) = 64
 (4 ^ 5) = 1024
 (1 ^ 5) = 1
#  Python 3 Program for
#  Calculate power without using division and multiplication
class PowerOfNumber :
	#  This is calculating the power of given positive integers
	def power(self, base, pow) :
		result = base
		update = base
		#  Execute loop through by given power
		i = 1
		while (i < pow) :
			#   Execute loop through by given base number
			j = 1
			while (j < base) :
				#  Calculate power
				result = result + update
				j += 1
			
			#  Change
			update = result
			i += 1
		
		#  Display calculated result
		print(" (", base ," ^ ", pow ,") = ", result)
	

def main() :
	task = PowerOfNumber()
	#  Test Case
	task.power(2, 6)
	task.power(4, 5)
	task.power(1, 5)

if __name__ == "__main__": main()

input

 ( 2  ^  6 ) =  64
 ( 4  ^  5 ) =  1024
 ( 1  ^  5 ) =  1
#  Ruby Program for
#  Calculate power without using division and multiplication
class PowerOfNumber 
	#  This is calculating the power of given positive integers
	def power(base, pow) 
		#  Define some resultant variable
		result = base
		update = base
		#  Execute loop through by given power
		i = 1
		while (i < pow) 
			#   Execute loop through by given base number
			j = 1
			while (j < base) 
				#  Calculate power
				result = result + update
				j += 1
			end

			#  Change
			update = result
			i += 1
		end

		#  Display calculated result
		print(" (", base ," ^ ", pow ,") = ", result, "\n")
	end

end

def main() 
	task = PowerOfNumber.new()
	#  Test Case
	task.power(2, 6)
	task.power(4, 5)
	task.power(1, 5)
end

main()

input

 (2 ^ 6) = 64
 (4 ^ 5) = 1024
 (1 ^ 5) = 1
/*
  Scala Program for
  Calculate power without using division and multiplication
*/
class PowerOfNumber()
{
	// This is calculating the power of given positive integers
	def power(base: Int, pow: Int): Unit = {
		// Define some resultant variable
		var result: Int = base;
		var update: Int = base;
		// Execute loop through by given power
		var i: Int = 1;
		while (i < pow)
		{
			//  Execute loop through by given base number
			var j: Int = 1;
			while (j < base)
			{
				// Calculate power
				result = result + update;
				j += 1;
			}
			// Change
			update = result;
			i += 1;
		}
		// Display calculated result
		println(" (" + base + " ^ " + pow + ") = " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: PowerOfNumber = new PowerOfNumber();
		// Test Case
		task.power(2, 6);
		task.power(4, 5);
		task.power(1, 5);
	}
}

input

 (2 ^ 6) = 64
 (4 ^ 5) = 1024
 (1 ^ 5) = 1
/*
  Swift 4 Program for
  Calculate power without using division and multiplication
*/
class PowerOfNumber
{
	// This is calculating the power of given positive integers
	func power(_ base: Int, _ pow: Int)
	{
		// Define some resultant variable
		var result: Int = base;
		var update: Int = base;
		// Execute loop through by given power
		var i: Int = 1;
		while (i < pow)
		{
			//  Execute loop through by given base number
			var j: Int = 1;
			while (j < base)
			{
				// Calculate power
				result = result + update;
				j += 1;
			}
			// Change
			update = result;
			i += 1;
		}
		// Display calculated result
		print(" (", base ," ^ ", pow ,") = ", result);
	}
}
func main()
{
	let task: PowerOfNumber = PowerOfNumber();
	// Test Case
	task.power(2, 6);
	task.power(4, 5);
	task.power(1, 5);
}
main();

input

 ( 2  ^  6 ) =  64
 ( 4  ^  5 ) =  1024
 ( 1  ^  5 ) =  1
/*
  Kotlin Program for
  Calculate power without using division and multiplication
*/
class PowerOfNumber
{
	// This is calculating the power of given positive integers
	fun power(base: Int, pow: Int): Unit
	{
		// Define some resultant variable
		var result: Int = base;
		var update: Int = base;
		var i: Int = 1;
		while (i < pow)
		{
			var j: Int = 1;
			while (j < base)
			{
				// Calculate power
				result = result + update;
				j += 1;
			}
			// Change
			update = result;
			i += 1;
		}
		// Display calculated result
		println(" (" + base + " ^ " + pow + ") = " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: PowerOfNumber = PowerOfNumber();
	// Test Case
	task.power(2, 6);
	task.power(4, 5);
	task.power(1, 5);
}

input

 (2 ^ 6) = 64
 (4 ^ 5) = 1024
 (1 ^ 5) = 1

Resultant Output Explanation

Let's analyze the output of the provided code:

(2 ^ 6) = 64
(4 ^ 5) = 1024
(1 ^ 5) = 1

The output consists of three sections: (base ^ exponent) = result, where base and exponent are the input values provided to the power function, and result is the calculated value of base raised to the power of exponent using the alternative method.

For example, when calculating 2^6, the code simulates the process of multiplication by repeatedly adding 2 to itself a total of 5 times. The result is 64, which is the correct value of 2^6.

Time Complexity

The time complexity of this approach is primarily determined by the two nested loops in the algorithm. The outer loop runs exponent - 1 times, and the inner loop runs base - 1 times for each iteration of the outer loop. As a result, the overall time complexity can be approximated as O(exponent * base).

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