Mathematical Example
Find an algorithm for raising a number X to the power N, where N is a
positive integer, using only multiplication and subtraction. The
problems we can solve directly are:
- raise X to the power 1: answer = X.
- raise X to the power 2: answer = X*X.
For N > 2, we split the original problem into two subproblems:
- P1: raise X to the power I. The answer to this is S1.
- P2: raise X to the power N-I. The answer to this is S2.
- To get the final answer, S, combine S1 and S2: S = S1*S2.
If I=1 or I=2 we can solve P1 directly, otherwise we solve it
recursively as described. If N-I=1 or N-I=2 we can solve P2 directly,
otherwise we solve it recursively too.