SICP

Exercise 4.37. Ben Bitdiddle claims that the following method for generating Pythagorean triples is more efficient than the one in exercise 4.35. Is he correct? (Hint: Consider the number of possibilities that must be explored.)

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high))
        (hsq (* high high)))
    (let ((j (an-integer-between i high)))
      (let ((ksq (+ (* i i) (* j j))))
        (require (>= hsq ksq))
        (let ((k (sqrt ksq)))
          (require (integer? k))
          (list i j k))))))

Ben 写的程序的确要更优化一些。在范围为 n 的情况下，前一个最多需要 $n^3$ 次选择，而这里只需要 $n^2$ 次选择即可找到。

因为我们的 amb 使用的是深度优先的回溯方式，要比较的两个程序实际可以写为下面的等同的形式：

for i in range(low, high+1):
    for j in range(i, high+1):
        for k in range(j, high+1):
            if i*i + j*j == k*k:
                return (i, j, k)

与

hsq = high * high
for i in range(low, high+1):
    for j in range(i, high+1):
        ksq = i*i + j*j
        if hsq >= ksq and is_integer(sqrt(ksq)):
           return (i, j, k)

其比较结果是可以想到的。

TODO：How to Prove in Math?

SICP 全笔记