Algorithms in a Nutshell

Benchmark Operations

The Scheme program in Example 2-7 computes 2ⁿ; a sample computation of 2⁸⁵¹ 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⁸⁵¹ 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ⁿ 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ⁿ. 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 ...