sicp-ex-4.36

Here's an efficient method that iterates only over two of the numbers, not all three. We are able to do this here because of the lack of limitations that were present in exercise 4.35 (requiring k <= high) and exercise 3..69 (arbitrary input streams S, T, and U rather than just "all integers").

First, some helper functions:

 (define (hypotenuse-squared i j) 
   (+ (square i) (square j))) 
  
 (define (round-to-integer x)  
   (inexact->exact (round x))) 
  
 (define (perfect-square? i) 
   (= i (square (round-to-integer (sqrt i))))) 

Next, a function that finds all pythagorean triples with i <= j = middle, where middle is an argument.

 (define (a-pythagorean-triple-with-middle-fixed middle) 
   (let ((i (an-integer-between 1 middle))) 
     (let ((hypot2 (hypotenuse-squared i middle))) 
       (require (perfect-square? hypot2)) 
       (list i middle (sqrt hypot2))))) 

Finally, a function that generates all triples:

 (define (all-pythagorean-triples) 
   (let ((middle (an-integer-starting-from 1))) 
     (let ((triple (a-pythagorean-triple-with-middle-fixed middle))) 
       triple))) 

  
  
  
  
 (define (a-pythagorean-triple-greater-than low) 
         (let ((k (an-integer-starting-from low))) 
          (let ((i (an-integer-between low k))) 
           (let ((j (an-integer-between i k))) 
             (require (= (+ (* i i) (* j j)) (* k k))) 
                 (list i j k))))) 
  
  

 an improved solution with a uniform style from meteorgan

  (define (a-pythagorean-triple-greater-than low) 
    (let ((i (an-integer-starting-from low))) 
      (let ((j (an-integer-between low i))) 
        (let ((k (an-integer-between low j))) 
          (require (= (+ (* k k) (* j j)) (* i i))) 
          (list k j i))))) 

  
  
  
 ;shorter, but very inefficient! 
  
 (define (a-pythagorean-triple-greater-than low) 
         (let ((high (an-integer-starting-from low))) 
                 (a-pythagorean-triple-between 1 higher))) 

  
 ; using a helper procedure to generate integers smaller than a certain number 
  
 (define (an-integer-to n) 
   (require (> n 0)) 
   (amb n (an-integer-to (- n 1)))) 
  
 (define (a-pythagorean-triple) 
   (let ((k (an-integer-from 1))) 
     (let ((j (an-integer-to k))) 
       (let ((i (an-integer-to j))) 
         (require (= (+ (* i i) 
                        (* j j)) 
                     (* k k))) 
         (list i j k))))) 

This solution uses the triangle inequality (i.e. the sum of the lengths of any two sides is greater than the third length) to bound the potential values of k (along with the fact that k > j since it is the hypotenuse).

  
  
 (define (a-pythagorean-triple) 
   (let ((j (an-integer-starting-from 1))) 
     (let ((i (an-integer-between 1 j))) 
       (let ((k (an-integer-between (+ j 1) (+ i j -1)))) 
         (require (= (+ (* i i) (* j j)) (* k k))) 
         (list i j k)))))