src/sicp/ex4_37.rkt

   1 #lang racket
   2
   3 (require "amb-eli.rkt")
   4
   5 (define (a-pythagorean-triple-between low high)
   6   (let ((i (an-integer-between low high))
   7         (hsq (* high high)))
   8     (let ((j (an-integer-between i high)))
   9       (let ((ksq (+ (* i i) (* j j))))
  10         (assert (>= hsq ksq))
  11         (let ((k (sqrt ksq)))
  12           (assert (integer? k))
  13           (list i j k))))))
  14
  15 #|
  16
  17 Yes, Ben is correct. The above program prunes the search space by restricting the
  18 possible values of k.
  19
  20 k^2 <= high^2
  21
  22 and sqrt (i^2 + j^2) is an integer. This eliminates a large number of (i, j, k) triples
  23 and hence the search space is a lot less than the naive implementation in the text.
  24
  25 |#