Class Project

Step 4: Time comparisons

• Deadline: Tuesday 25 November 2003, 11:59 PM
  
  
• In this step, compare the time efficiency of the precfunc, tristream, and wordstream implementations of xreal. I updated the testing and timing utilities from last year to work with MZScheme in the definitions file progutils-3.scm on the resources page. time displays run time, garbage-collection time, and real time to evaluate a given expression. timetest lets you list time tests in files to be processed with progtest.
  
  
• Experiment with time to get an idea of how it works, and how the timings can vary due to invisible influences. You might find the following spin procedure useful for trying out time

  
  (define (spin n)
  
    (cond ((= n 0) '())
          (else    (spin (- n 1)))))
  

• Find some interesting comparisons of the time efficiency of precfunc vs. tristream vs. wordstream. You may have to work a bit to come up with computations that are large enough to get meaningful numbers from time. Try to make the examples get at the heart of the structural effects that determine efficiency for each implementation. precfunc is vulnerable to waste from generating rationals that are unnecessarily complex, and from repeating computations unnecessarily. tristream is vulnerable to waste because it treats numbers approximately one bit at a time. wordstream performs sensible sized operations on integers, but it is vulnerable to requiring far more precision than necessary from intermediate steps, since the need for one more bit can create the demand for a whole word.
  
  
• You might get some good ideas from the 2002 discussion.
  
  
• Try to explain the timings that you observe in terms of the structures of the two implementations. You can figure things out for yourself, or find some analysis in the articles by Hans Boehm that I copied for you. In any case, you should present the explanations with insightful examples. You may decide to add output to some of your procedures to illuminate the structure of their computations.

What to hand in

• All of the definitions files required to run your timings, except the ones that I provided for you.
  
  
• All files of timing inputs, using my timetest from progutils-3.scm or test code of your own if you like it better.
  
  
• A file called README.txt containing very short and simple instructions how to execute your tests. If this takes more than 2 lines, you probably need to write a Scheme file to automate things more for the grader.
  
  
• A text file called comments.txt, or a variant in another format, containing a discussion of your observations.

---

Copyright Michael J. O'Donnell <michael_odonnell@acm.org>. Licensed for free use.
This page is generated from PHP source code, with supporting files.

Last modified: Thu Nov 20 21:46:53 CST 2003