Benchmark Operations

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 ...

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.