求幂、快速幂运算

对一个给定的数计算乘幂。这一过程的参数是一个基数b和一个正整数的指数n，过程计算出b ^ n。
一种方式是通过下面这个递归定义：

b ^ n = b * b ^ (n - 1)
b ^ 0 = 1

线性递归：
【时间复杂度：O(n)，空间复杂度：O(n)】

(define (expt b n)
  (if (= n 0) 1
      (* b (expt b (- n 1)))))

线性迭代：
【时间复杂度：O(n)，空间复杂度：O(1)】

(define (expt b n)
  (define (expt-iter n product)
    (if (= n 0) product
        (expt-iter (- n 1) (* product b))))

  (expt-iter n 1))

快速幂运算
我们可以通过连续求平方，以更少的步骤完成乘幂运算。
例如，不是采用这种方式计算b ^ 8：

b * (b * (b * (b * (b * (b * (b * b)))))) 

而是用三次乘法算出它来：

b ^ 2 = b * b
b ^ 4 = b ^ 2 * b ^ 2
b ^ 8 = b ^ 4 * b ^ 4

如果采用下面规则，我们就可以借助于连续求平方，去完成一般的乘幂运算：

b ^ n = (b ^ (n / 2)) ^ 2     若n是偶数
b ^ n = b * b ^ (n - 1)       若n是奇数

递归算法：
【时间复杂度：O(log n)，空间复杂度：O(log n)】

(define (fast-expt b n)
  (define (even?) (= (remainder n 2) 0))
  (define (square x) (* x x))

  (cond ((= n 0) 1)
        ((even?) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

迭代算法：
【利用关系(b ^ (n / 2)) ^ 2 = (b ^ 2) ^ (n / 2)。
另外维持一个附加的状态变量ret，并定义好状态变换，使得从一个状态转到另一状态时乘积a * (b ^ n)保持不变。
重要思想：定义一个不变量，要求它在状态之间保持不变】
【时间复杂度：O(log n)，空间复杂度：O(1)】

(define (even? x) (= (remainder x 2) 0))    // racket实现了此函数，可省略
(define (square x) (* x x))

(define (fast-expt b n)
  (define (fei b n ret)
    (cond ((= n 0) ret)
          ((even? n) (fei (square b)
                          (/ n 2)
                          ret))
          (else (fei b
                     (- n 1)
                     (* ret b)))))

  (fei b n 1))

// 测试
(fast-expt 2 4)
(fast-expt 3 3)
(fast-expt 4 5)
(fast-expt 5 3)
// 输出
16
27
1024
125

应用
通过反复做加法的方式求乘积，只用对数（O(log n)）的计算步数。

a * b = (a * (b / 2)) * 2
a * b = a + a * (b - 1)

【原理与快速幂运算求乘幂类似】

递归

(define (double x) (* x 2))
(define (halve x) (/ x 2))

(define (multi a b)
  (cond ((= b 0) 0)
        ((even? b) (double (multi a
                                  (halve b))))
        (else (+ a
                 (multi a (- b 1))))))

迭代

(define (double x) (* x 2))
(define (halve x) (/ x 2))

(define (mul a b)
  (define (mul-iter a b ret)
    (cond ((= b 0) ret)
          ((even? b) (mul-iter (double a)
                               (halve b)
                               ret))
          (else (+ a
                   (mul-iter a
                             (- b 1)
                             (* a ret))))))

  (mul-iter a b 0))

------------------------------------
// else 语句里面的写法可替换成：
(else (mul-iter a
                (- b 1)
                (+ a ret)))

// 测试
(mul 2 4)
(mul 5 20)
(mul 33 88)
(mul 99 11)
// 输出
8
100
2904
1089