SICP 1.2.4 ExponentiationをPythonでやってみた

SICPの1.2.4 ExponentiationあたりをPythonでやってみた

scheme

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))
(expt 2 4) ;16

;iterative
(define (expt b n)
  (expt-iter b n 1))
(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product)))) 
(expt 2 4) ;16

;fast exptiation
(define (square x)(* x x))
(define (even? n)
  (= (remainder n 2) 0))
(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))
(fast-expt 2 4) ;16

python

# recursive
def expt(b, n):
    if n == 0:
        return 1
    return b * expt(b, (n - 1))
print expt(2,4) #16

# iterative
def expt(b,n):
    return expt_iter(b,n,1)
def expt_iter(b, counter, product):
    if counter == 0:
        return product
    return expt_iter(b, counter - 1, b * product)
print expt(2,4) #16

#fast exptiation
def square(x):
    return x * x
def fast_expt(b, n):
    if n == 0:
        return 1
    elif even(n):
        return square(fast_expt(b, n / 2))
    else:
        return b * fast_expt(b, n - 1)
def even(n):
    if n % 2 == 0:
        return True
    
print fast_expt(2, 4) #16
print fast_expt(2, 5) #32