=begin
거듭제곱 의 점화식

  c^n = c^(n/2) * c^(n/2), n is even
        c^((n-1)/2) * c^((n-1)/2) * c, n is odd
        c, n == 1
        1, n == 0

이를 이용하여 divide and conquer 로 c를 n 번 곱하지 않고 c^n 을 구한다
=end

def power(number, exponent)
  return 1 if 0 == exponent
  return number if 1 == exponent

  temp = 0
  if 0 == exponent & 1
    temp = power(number, exponent / 2)
    temp *= temp
  else
    temp = power(number, (exponent - 1) / 2)
    temp *= (temp * number)
  end

  temp
end

puts "2^200 = " + power(2, 200).to_s

2^200 = 1606938044258990275541962092341162602522202993782792835301376