solutions to 4.35, 4.36 and 4.37

[sicp.git] / src / sicp / ex4_37.rkt

diff --git a/src/sicp/ex4_37.rkt b/src/sicp/ex4_37.rkt
new file mode 100644 (file)
index 0000000..a4528a0
--- /dev/null
+++ b/src/sicp/ex4_37.rkt
@@ -0,0 +1,25 @@
+#lang racket
+
+(require "amb-eli.rkt")
+
+(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))))
+        (assert (>= hsq ksq))
+        (let ((k (sqrt ksq)))
+          (assert (integer? k))
+          (list i j k))))))
+
+#|
+
+Yes, Ben is correct. The above program prunes the search space by restricting the
+possible values of k.
+
+k^2 <= high^2
+
+and sqrt (i^2 + j^2) is an integer. This eliminates a large number of (i, j, k) triples
+and hence the search space is a lot less than the naive implementation in the text.
+
+|#