sicp 1.2.6 费马小定理 核心代码的 尾递归优化版实现 与 实现正确性的证明(with todo)

expmode-better.scm

; 书上的初版实现
(define (expmode base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
            (remainder (square (expmode base (/ exp 2) m)) m))
          (else 
            (remainder (* base (expmode base (- exp 1) m)) m))
    )
)

; 优化版实现
(define (expmode-better base exp m product)
    (cond ((= exp 0) product)
          ((even? exp)
            (expmode-better (square base) (/ exp 2) m product))
          (else 
            (expmode-better base (- exp 1) m (remainder (* base product) m)))
    )
)

可以使用 trace 函数跟踪调用栈. 可以发现:

• expmode-better 的调用栈始终是1, 即空间复杂度, 始终是 θ(1)
• expmode-better 和 expmode, 并不是 镜像 实现. 因为两个 函数的 含义是有差别的.

> (expmode 8 31 23)
|(expmode 8 31 23)
| (expmode 8 30 23)
| |(expmode 8 15 23)
| | (expmode 8 14 23)
| | |(expmode 8 7 23)
| | | (expmode 8 6 23)
| | | |(expmode 8 3 23)
| | | | (expmode 8 2 23)
| | | | |(expmode 8 1 23)
| | | | | (expmode 8 0 23)
| | | | | 1
| | | | |8
| | | | 18
| | | |6
| | | 13
| | |12
| | 6
| |2
| 4
|9
9
> (expmode-better 8 31 23 1)
|(expmode-better 8 31 23 1)
|(expmode-better 8 30 23 8)
|(expmode-better 64 15 23 8)
|(expmode-better 64 14 23 6)
|(expmode-better 4096 7 23 6)
|(expmode-better 4096 6 23 12)
|(expmode-better 16777216 3 23 12)
|(expmode-better 16777216 2 23 2)
|(expmode-better 281474976710656 1 23 2)
|(expmode-better 281474976710656 0 23 9)
|9
9

(define (expmode-better base exp m product)
    (cond ((= exp 0) product)
          ((even? exp)
            (expmode-better (square base) (/ exp 2) m product))
          (else 
            (expmode-better base (- exp 1) m (remainder (* base product) m)))
    )
)

断言

(expmode-better base exp m product) = base^exp % m * product

证明

case 1: exp = 0.

(expmode-better base exp m product)
= (expmode-better base 0 m product)
= product
= base^0 % m * product
= base^exp % m * product

case 2: exp > 0 and exp is even.

(expmode-better base exp m product)
= (expmode-better base^2 exp/2 m product)
= ((base^2) ^ (exp/2)) % m * product
= base^exp % m * product

case 3: exp > 0 and exp is odd.

(expmode-better base exp m product)
= (expmode-better base exp-1 m (base*product)%m)
= (base^(exp-1) % m) * ((base*product) % m) 
= base^exp % m * product

TODO:

case 2 最后两步, 缺乏严谨的数学证明. 从逻辑上看, 最终保留的 只有 product, 所以应能保证结果是符合预期的.

• 可能有用的信息: 奇数时, 更像是在计算 a^0 -- a^1 -- a^2 -- a^3