Benchmark Operations
The Scheme program in Example 2-7 computes 2^{n}; a sample computation of 2^{851} 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 2^{851} 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 2^{n} 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 2^{n}. 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 2^{x}
There is clearly a linear relationship initially, as ...
Get Algorithms in a Nutshell now with O’Reilly online learning.
O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.