Quirksand

SICP

SICP 1.2.6 Exercises

November 9, 2012 20:46

This section’s questions get into the details of the time taken by a computation. As one might expect, it’s going to be something that’s very processor-dependent. It also will end up being slightly different for different flavors of Scheme, because they may have different ways of reporting the time taken.

Recall that in Racket, there is the time function, which I first mentioned when examining results in Section 1.2.4 a little while back. This time it’s going to be the main time-reporting function used. If you don’t have such a function, the ones given in the book might be what you need. Or figure out what will work in its place.

These are the functions I defined to use time that will still look mostly like the results in the book.

(define (timed-prime-test n)  
  (display n)
  (if (prime? n) 
      (report-prime n)
      (newline)
      )
  )

(define (report-prime p)
  (display " *** ")
  (time (prime? p))
  (void)
  )

There is no need for separate functions to mark the start and end of the test, as time accounts for the whole computation.

However, the other thing to contend with is that since this book was written, processor speeds are several orders of magnitude faster. Calculating these results once took an appreciable amount of time; now it happens in less than a millisecond. Yet another set of procedures are needed to get usable results.

(define (timed-prime-test-with-cycles n count)
  (display n)
  (if (prime? n) 
      (report-prime-with-cycles n count)
      (newline)
      )
  )

(define (report-prime-with-cycles p count)
  (display " *** ")
  (time (test-prime-iter p count))
  (void)
  )

(define (test-prime-iter p count)
  (prime? p)
  (if (> count 1)
      (test-prime-iter p (- count 1))
      )
  )

The first two procedures are exactly the same as for the regular prime test, aside from the names. There is simply the last one thrown in that repeats the prime test as many times as are requested. I used 1000 cycles at the start to get a good balance of speed and usable numbers, but you can change it as you need.

In the testing section of some of the exercises, the timing method is left blank to allow for either one to be used. This time you will need to pick which test you prefer that gives a useful answer for them. As always, I encourage you to add in your own tests or change them as you see fit.

Exercises 1.2.6