O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required