Algorithms in a Nutshell

(^36) | Chapter 2: The Mathematics of Algorithms
Benchmark Operations
The Scheme program in Example 2-7 computes 2n; a sample computation of 2^851
is shown.
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 2n has consistent behavior, regardless of the value ofn.
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.
There is clearly a linear relationship initially, as an increasing number of multiply-
by-2 operations are performed. However, oncexreaches about 30, a different
linear relationship takes place. For some reason, the computational performance
alters once powers of 2 greater than about 30 are used.
Table 2-6. Comparing operations from different implementations
Input Size op1 (ms) op2 (ms) # op1 # op2 Total (ms)
A on 1,000 0.008 0.001 2,000 3,000 19
A on 100,000 0.0016 0.003 200,000 300,000 1,220
B on 1,000 0.001 0.001 2,000 3,000 5
B on 100,000 0.1653 0.5619 200,000 300,000 201,630
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)
15015033657609400459942315391018513722623519187099007073355798781525263125238463
41589482039716066276169710803836941092523836538133260448652352292181327981032007
94538451818051546732566997782908246399595358358052523086606780893692342385292277
74479195332149248
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use