4.37 Exercise 4.37

Consider the two following procedures for computing Pythagorean triples with high and low bounds:

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

(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))))))

The former method is naive and straightforward, iterating through all of the possibilities for i, j, and k and testing whether the equality holds. This is very inefficient, requiring on the order of O(n^3) operations.

The alternative solution is more clever. First, it acts on the fact that it isn’t necessary to test more than a single potential k value after i and j are fixed – there’s only one sum to their squares, and the square root of that is either an integer or not. Doing this cuts a power of n off of the time complexity.

However, in order for this to work, you need to know when to stop testing values. However, this is also easily done – we know that the maximum value of k cannot be greater than the square root of the high bound. Alternatively, as expressed in the algorithm above, k^2 cannot be greater than high^2. (My only complaint about the above is that I would calculate hsq before i). Then, all that needs to be done is checking whether the potential k^2 values are no greater than this upper bound.

We can see that the second algorithm does test every valid i and j, and that this means that all possible triples with i and j within bounds are checked. We can also see that no possible triples outside of the bounds will be considered – any value of k such that k^2 is greater than high^2 is not accepted. Therefore, we can trust that the second algorithm is correct, while also being significantly more efficient than the first.

← prev up next →

1	Chapter 1
2	Chapter 2
3	Chapter 3
4	Chapter 4
5	Chapter 5

4.1	Exercise 4.1
4.2	Exercise 4.2
4.3	Exercise 4.3
4.4	Exercise 4.4
4.5	Exercise 4.5
4.6	Exercise 4.6
4.7	Exercise 4.7
4.8	Exercise 4.8
4.9	Exercise 4.9
4.10	Exercise 4.10
4.11	Exercise 4.11
4.12	Exercise 4.12
4.13	Exercise 4.13
4.14	Exercise 4.14
4.15	Exercise 4.15
4.16	Exercise 4.16
4.17	Exercise 4.17
4.18	Exercise 4.18
4.19	Exercise 4.19
4.20	Exercise 4.20
4.21	Exercise 4.21
4.22	Exercise 4.22
4.23	Exercise 4.23
4.24	Exercise 4.24
4.25	Exercise 4.25
4.26	Exercise 4.26
4.27	Exercise 4.27
4.28	Exercise 4.28
4.29	Exercise 4.29
4.30	Exercise 4.30
4.31	Exercise 4.31
4.32	Exercise 4.32
4.33	Exercise 4.33
4.34	Exercise 4.34
4.35	Exercise 4.35
4.36	Exercise 4.36
4.37	Exercise 4.37
4.38	Exercise 4.38
4.39	Exercise 4.39
4.40	Exercise 4.40
4.41	Exercise 4.41
4.42	Exercise 4.42
4.43	Exercise 4.43
4.44	Exercise 4.44
4.45	Exercise 4.45
4.46	Exercise 4.46
4.47	Exercise 4.47
4.48	Exercise 4.48
4.49	Exercise 4.49
4.50	Exercise 4.50
4.51	Exercise 4.51
4.52	Exercise 4.52
4.53	Exercise 4.53
4.54	Exercise 4.54
4.55	Exercise 4.55
4.56	Exercise 4.56
4.57	Exercise 4.57
4.58	Exercise 4.58
4.59	Exercise 4.59
4.60	Exercise 4.60
4.61	Exercise 4.61
4.62	Exercise 4.62
4.63	Exercise 4.63
4.64	Exercise 4.64
4.65	Exercise 4.65
4.66	Exercise 4.66
4.67	Exercise 4.67
4.68	Exercise 4.68
4.69	Exercise 4.69
4.70	Exercise 4.70
4.71	Exercise 4.71