sicp-e1.16.rkt.md

;; SICP p.46 Exercise 1.16

#lang racket

;; The recursive procedure of power.  Both the
;; space and computation cost are O(n).
(define (power-rec b n)
  (if (= n 0)
      1
      (* b (power-rec b (- n 1)))))

(power-rec 10 7)

;; The iterative procedrue of power.  The space
;; cost is O(1), and the computation cost is O(n).
(define (power-iter b n)
  (define (loop b n p)
    (if (= n 0)
        p
        (loop b (- n 1) (* b p))))
  (loop b n 1))

(power-iter 10 7)

;; The recursive procedure that takes O(log n)
;; computation cost and O(n) space cost.
(define (power-fast b n)
  (cond ((= n 0) 1)
        ((odd? n) (let* ((n (/ (- n 1) 2))
                         (t (power-fast b n)))
                    (* t t b)))
        (else (let ((t (power-fast b (/ n 2))))
                (* t t)))))

(power-fast 10 7)

;; The iterative procedure that takes O(log n)
;; computation cost and O(1) space cost.
(define (power-fast-iter b n)
  (define (loop b n a)
    (cond ((= n 0) a)
          ((even? n) (loop (* b b) (/ n 2) a))
          (else (loop b (- n 1) (* b a)))))
  (loop b n 1))

(power-fast-iter 10 7)

;;; The corresponding Python implementation
; def power(b: int, n: int) -> int:
;   a: int = 1
;   while n > 0:
;     if n % 2 == 1:
;       a = a * b
;       n = n - 1
;     else:
;       b = b * b
;       n = n / 2
;   return a
; 
; power(10, 7)