Power(base, exponent)
by Isai Damier, Android Engineer @ Google

/*********************************************************************
 * Author: Isai Damier
 * Title: Power(base, exponent)
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement: Compute base x raised to exponent n: x^n
 *
 * Sample Input: 3^11
 * Sample Output: 177147
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(Time) = O(log n),
 *
 * Technical Details:
 *   Instead of multiplying x by itself n times using a for-loop,
 *   we continually divide the exponent by two (think binary search)
 *   hence reducing the time complexity to O(log n) instead of O(n).
 *   We demonstrate by manually solving for 3^11.
 *
 *   3^11 = 3^5 * 3^5 * 3
 *   3^5 = 3^2 * 3^2 * 3
 *   3^2 = 3 * 3 = 9
 *
 *  Therefore, we perform five multiplications instead of eleven:
 *  3*3=9; 9*9*3 = 243; 243*243*3 = 177147
 *
 ********************************************************************/ 
 public int pow(int base, int exponent) {
	if (1 == exponent) {
		return base;
	}
	int result = pow(base, exponent / 2);
	if (0 == (exponent & 1)) {
		return result * result;
	}
	return result * result * base;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class NumbersTest {

	/**
	 * Test of pow method, of class Numbers.
	 */
	@Test
	public void testPow() {
		System.out.println("pow");
		Numbers exponent = new Numbers();
		int x = 2;
		int n = 11;
		assertEquals((int) Math.pow(x, n), exponent.pow(x, n));
		x = 3;
		n = 7;
		assertEquals((int) Math.pow(x, n), exponent.pow(x, n));
		x = 5;
		n = 4;
		assertEquals((int) Math.pow(x, n), exponent.pow(x, n));
		x = 4;
		n = 6;
		assertEquals((int) Math.pow(x, n), exponent.pow(x, n));
	}
}