Divide and Conquer: Exponentiation

      320
      = (3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3) ⋅
        (3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3)
      = (3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3)2
      = ((3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3) ⋅ (3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3))2
      = ((3 ⋅ 3 ⋅ 3 ⋅ 3 ⋅ 3)2)2
      = (((3 ⋅ 3) ⋅ (3 ⋅ 3) ⋅ 3)2)2
      = (((3 ⋅ 3)2 ⋅ 3)2)2
    

Applying that divide-and-conquer algorithm recursively reduces the number of multiplications from 19 to 5.

This isn't magic.

Solving a problem by recursively dividing each of its non-trivial subproblems into two parts does not, by itself, make the calculation simpler or more efficient.

The efficiency of divide-and-conquer algorithms comes from performing subcomputations only once instead of performing them two or more times. Dividing the problem in two helps only because it exposes repeated subcomputations to our notice, so we can avoid doing them more than once.

For debugging: Click here to validate.