The Scheme program in Example 2-7 computes 2n; a sample computation of 2851 is shown.
Example 2-7. Expensive computations
;; TwoToTheN: number -> number (define (TwoToTheN n) (let loop ([i n] [result 1]) (if (= i 0) result (loop (sub1 i) (* 2 result))))) ;; the result of a sample computation (TwoToTheN 851) 15015033657609400459942315391018513722623519187099007073355798781525263125238463415894820397160662761697108038369410925238365381332604486523522921813279810320079453845181805154673256699778290824639959535835805252308660678089369234238529227774479195332149248
In Scheme, computations are relatively independent of the underlying platform. That is, computing 2851 in Java or C on most platforms would cause a numeric overflow. But a fast computation in Scheme yields the result shown in the example. Is it an advantage or a disadvantage that the underlying architecture is hidden from us, abstracted away? Consider the following two hypotheses:
- Hypothesis H1
Computing 2n has consistent behavior, regardless of the value of n.
- Hypothesis H2
Large numbers (such as shown previously in expanded form) can be treated in the same way as any other number, such as 123,827 or 997.
To refute hypothesis H1, we conduct 50 trials that performed 10,000 evaluations of 2n. We discarded the best and worst performers, leaving 48 trials. The average time of these 48 trials is shown in Figure 2-8.
Figure 2-8. Execution times for computing 2x
There is clearly a linear relationship initially, as ...