Implement power function without using multiplication

In this post I am going to discuss one interesting  programming question. You are supposed to write power function without using multiply operator. You are allowed to use division operator but not multiply.

This is a good question to show your skill at optimizing code and showing that you don't miss the corner cases. You can use multiple additions to simulate multiplication. You need to make sure that you use lest number of additions. For example if you are multiplying 5 with 5 then you don't add 5 four time, you can do it by adding three times. You add 5 with 5 to get 10 in one addtion, You add 10 with 10 in second addition and after that you add 5 in third addition to get answer as 25.

You can implement one function for multiplying two numbers and use that function in your power function. Here again you need to make least number of calls to multiply function. For example if you are calculating 5^5 then we can do it with three calls to multiply functions instead of 4 calls. You multiply 5 with 5 in first call to get 25. You multiply 25 with 25 in second call and multiply 625 with 5 in third call.

Following is the java code for this question:

public class PowerWithoutMul {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int m = 4;
		int n = 4;
		
		System.out.println(pow(m, n));
		

	}
	
	static int pow(int m, int n) {
		int res = 1;
		if(n/2>0) {
			int temp = pow(m, n/2);
			res = mul(temp, temp);
		}
		if(n%2==1) {
			res = mul(res, m);
		}
		return res;		
	}
	
	static int mul (int m, int k) {
		int res = 0;
		if(k/2>0) {
			int temp = mul(m, k/2);
			res =  temp + temp;
		}
		
		if(k%2 == 1) {
			res = res + m;
		}
		return res;
	}

}