sum-of-divisorsprocedure introduced in section 3.3.
run-timefor timing how long computations take, copy the following expression:
(load "~mc27/public/time.scm")into your definition window and execute it. (For those using other computers, here is a copy of time.scm.) To get the text's definitions of
divides?, copy the procedures in the following file into your definitions window and execute them:
~mc27/labs/sum-divisors/sum-of-divisors.scmNow you should time how long it takes to find the sum of divisors of 100, 1000, 10000, 100000, and 1000000. You should do the same timing repeatedly, at least for the smaller numbers, to get some idea how precisely repeatable the timings are. To illustrate how you would do a timing, here is a sample timing of the
The time is given in seconds; e.g., in the above example, the evaluation took a little less than eight ten-thousandths of a second (said another way, a little less than 0.8 milliseconds). The time reported will not agree well with your own impression of the time taken, because it doesn't include time the computer spends doing other things, and also because for fast evaluations (such as the above) the evaluation is repeated until at least a second has elapsed and an average time for the repetitions is reported.
Each time you increase the number by a factor of 10, by what multiple does your time measurement increase? (That is: What is the ratio of times for 1000 relative to 100? For 10000 relative to 1000? And so forth.) How does this compare with your expectation? (Note: When answering questions like these in your project write-up, be sure to back up your answers with adequate arguments. In other words, give reasons, probably in the form of big Theta arguments, which explain your expectations.)
sum-of-divisorsprocedure other than finding perfect numbers is to measure the relative frequency of abundant and deficient numbers. As mentioned in section 3.3, very few numbers are perfect. The remaining numbers either have a sum of divisors that is more than twice the number, in which case they are called abundant, or less than twice the number, in which case they are called deficient. The empirical question we'd like to ask is, are these two kinds of numbers equally common, or does one predominate? If so, by how much? The usual mathematical way to formulate this is to count how many numbers less than or equal to n are abundant and how many are deficient, and take the ratio. Then repeat this for larger and larger values of n. If the ratio approaches closer and closer to some limiting value as n increases, then this limiting ratio tells us the relative frequency of abundant and deficient numbers. For example, if the ratio approaches a limit of 1, then abundant and deficient numbers are equally frequent. On the other hand, a limiting value of 1/2 would mean that there are roughly twice as many deficient numbers as abundant numbers.
Write a procedure that generates an iterative process for computing this ratio, given n. Most of the work can be done by a subsidiary procedure that keeps count of how many abundant numbers it has found and how many deficient numbers it has found as it scans the range from 1 to n. Once the entire range has been scanned, one count can be divided by the other. Test your procedure to be sure that it works.
Suppose that you are using the text's definition of
with your procedure for computing the ratio, and double the size of the
range being tested. By roughly what factor do you expect the number of
tests (and hence time) to increase? How about if you use the
sum-of-divisors procedure from
exercise 3.6? (You can use the same general style of reasoning as on page
81 to produce a big Theta asymptotic order of growth.)
Now measure how long your procedure takes to find the ratio for n
equal to 200, 400, 800, 1600 and 3200, and calculate how many times
larger each time is than the previous one.
Do this with each of the two definitions for
How well do your measurements agree with your predictions? Do the abundant/deficient
ratios seem to approach some simple limiting value? If so, what?
You ought to use tables and/or graphs to more clearly show your results. Keep in mind that tables' headings and graphs' axes should be labeled with both the variable being measured and the unit it is being measured in, if any. Also, if your goal is to compare the results of two experiments, it's best if the data from both can be placed in the same table or graph. It's confusing for the reader if the data appear on separate pages.
You might also want to make some additional predictions that go beyond your measurements. Suppose you were interested in pursuing the abundant/deficient ratio study well beyond n=3200, perhaps to n=102400. How long would you expect each method to take? Would you want to experimentally verify this? A harder (optional) question is, how large an n would the computer be able to handle in a day? a week? a year?
When you write the project report, remember that your audience is generally knowledgeable about computer science and Scheme, but not about what you did.
As with project 1, you should also consult the document entitled Suggestions for clear reports in computer science courses.