sicp-ex-3.69



<< Previous exercise (3.68) | Index | Next exercise (3.70) >>


meteorgan + adams

I've made a small cleanup to meteorgan's code.  Cons is much more appropriate than append. -- adams



(define (triples s t u)
        (cons-stream (list 
                                        (stream-car s)
                                        (stream-car t) 
                                        (stream-car u))
                                 (interleave
                                        (stream-map (lambda (x) (cons (stream-car s) x))
                                                               (stream-cdr (pairs t u)))
                                        (triples (stream-cdr s)
                                                     (stream-cdr t)
                                                     (stream-cdr u)))))
(define (phythagorean-numbers)
        (define (square x) (* x x))
        (define numbers (triples integers integers integers))
        (stream-filter (lambda (x) 
                                                (= (square (caddr x)) 
                                                (+ (square (car x)) (square (cadr x)))))
                                numbers))

xdavidliu

The above solution requires many redundant computations of (pairs t u). Here's an alternative implementation that only computes (pairs t u) once. We construct the triples by consing all elements of s up to the corresponding first element in (pairs t u). For the case that t is not the integers, we compute (pairs integers integers) in order to keep track of how many elements of s "fit".

 (define first-of-integer-pair 
   (stream-map car (pairs integers integers))) 
  
 (define (triples s t u) 
   (let ((pairs-tu (pairs t u))) ;; compute pairs only *once* 
     (define (rec si i ptu top-i) 
       (cons-stream 
        (cons (stream-car si) (stream-car ptu)) 
        (if (= i (stream-car top-i)) 
            (rec s 1 (stream-cdr ptu) (stream-cdr top-i)) 
            ;; restart s cycle with next ptu 
            (rec (stream-cdr si) (1+ i) ptu top-i)))) 
     (rec s 1 pairs-tu first-of-integer-pair))) 
  
 ;; example: pythagorean triples 
  
 (define triples-integers 
   (triples integers integers integers)) 
  
 (define (pythagorean? a b c) 
   (= (square c) 
      (+ (square a) (square b)))) 
  
 (define pythagorean-triples 
   (stream-filter 
    (lambda (triple) 
      (apply pythagorean? triple)) 
    triples-integers)) 
  
 (stream-ref pythagorean-triples 0) ; (3 4 5) 
 (stream-ref pythagorean-triples 1) ; (6 8 10) 
 (stream-ref pythagorean-triples 2) ; (5 12 13) 
 (stream-ref pythagorean-triples 3) ; (9 12 15) 
 (stream-ref pythagorean-triples 4) ; (8 15 17) 
  

Note even with the above optimization of computing (pairs t u) only once, finding pythagorean triples is very slow: (8 15 17) is the 163813th item in the triples-integers stream.

Note also that it may be possible to skip computing first-of-integer-pair entirely, by inverting the result from exercise 3.66: z = (n-m+1/2) 2^m - 2, solving for m in terms of z; this would reduce complexity by a factor of 2