Power Splitter

pow(a, n):

  if n == 0: return 1

  half = pow(a, n/2)

  result = half × half

  if n is odd: result *= a

  return result

Key insight: a^n = (a^(n/2))² when n is even

And a^n = a × (a^(n/2))² when n is odd