Efficient exponentiation

efficient_exponentiation.py

def exp(x,n):
  """Returns x^n, for integers x,n and n>=0
  This is done more intelligently, as we can use the definition
  that x^(a/2)^2 == x^a to make many less multiplications"""
  
  # count is the amount of multiplications.
  count = 0
  result = 1
  x_raised = x
  # On each iteration, multiply our result by x^a if x^a is needed to compute x^n.
  # For example, x^4 is in x^7, since 4 is the largest power of 2 that goes into 7.
  while n>0:
    if n % 2:
      count += 1
      result *= x_raised
    x_raised = x_raised*x_raised
    count +=1
    n /= 2
  return result, count

def naive(x,n):
  """Returns x^n, for integers x,n and n>=0
  This is done by naively doing n multiplications"""
  result = 1
  count = 0
  for i in range(n):
    result *= x
    count +=1
  return result, count
    
def main():
  result, count = exp(50,1024)
  print count

  result, count = naive(50,1024)
  print count

if __name__ == '__main__':
  main()