Giudoku Official Site
Efficient powering technique

Input: two integers, x and n, with n >= 0
Output: x^n

The most immediate method of powering a number is clear to everyone: you multiply x by itself n times. This will have linear time Theta(n).

Using the divide et impera technique, a more efficient method has been found.
If n is even, then x^n = x^(n/2) * x^(n/2). We compute pow(x, n/2) just once and then return the result multiplied by itself.
If n is odd, then x^n = x ^ ((n-1)/2) * x ^ ((n-1) / 2) * x. The same as above, paying attention to the last factor x.
The base case of the recursion appears when n is 0 or 1: respectively, 1 and n is returned.

Recurrence: T(n) = T(n/2) + Theta(1) = Theta(logn) for the master theorem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Random;

public class Powering
{
	public static void main(String[] args)
	{
		Random gen = new Random();
		int x = gen.nextInt(11);
		int n = gen.nextInt(4);

		System.out.println(x + "^" + n + " = " + RecursivePower(x, n));
	}

	public static int RecursivePower(int x, int n)
	{
		if (n == 0)
		{
			return 1;
		}

		if (n == 1)
		{
			return x;
		}

		if (n % 2 == 0)
		{
			int y = RecursivePower(x, n/2);
			return y*y;
		}

		int y = RecursivePower(x, (n-1)/2);
		return y*y*x;
	}
}