(^304) | Chapter 10: When All Else Fails
The expected execution time of this algorithm is
That is, the expected number of executions of thewhile loop is
This algorithm is similar to the mark-and-release experiments biologists use to
estimate the size of a spatially limited population of organisms. Clearly the algo-
rithm can never give the exact value ofn, since 2k^2 /πcan never be an integer. But
the value 2k^2 /πis an unbiased estimate ofn; that is, the expected value of 2*k^2 /π
equalsn.
In Table 10-1 we show a sample run of the algorithm that records the results of
the computations of a number of separate trials. The probabilistic algorithm
generated an estimate fornwithttrials (32, 64, 128, and 256). From these trials,
the lowest and highest estimates were discarded, and the average of the remaining
t–2 trials is shown in the respective column. The final three rows show the accu-
racy of these “average of estimations” by computing (a) the minimum ratio of
estimation/target, (b) the maximum ratio of estimation/target, and (c) the range
from minimum to maximum. For example, for 32 trials, the estimate of 353,998
for the target 524,288 exhibited the lowest ratio (.68), whereas the estimate
1,527,380 for 1,048,576 exhibited the highest ratio (1.46).
Table 10-1. Sample execution of probabilistic counting algorithm
n Average for 32 Average for 64 Average for 128 Average for 256
256 314 210 296 362
512 511 684 643 664
1,024 941 905 1,150 1,314
2,048 2,611 3,038 2,405 2,532
4,096 3,779 6,068 4,812 5,378
8,192 7,858 10,656 8,435 10,860
16,384 22,786 21,617 19,169 19,809
32,768 33,509 40,549 36,395 38,863
65,536 85,421 77,335 80,119 93,807
131,072 131,728 172,175 148,549 160,750
262,144 270,187 421,345 375,442 299,551
524,288 353,998 463,923 736,396 642,986
1,048,576 1,527,380 1,417,047 1,299,312 1,334,487
2,097,152 2,291,903 2,106,072 2,615,379 2,445,086
4,194,304 5,348,730 4,565,833 5,653,524 5,132,245
8,388,608 8,017,734 9,791,002 12,220,879 10,064,671
16,777,216 23,006,070 28,363,383 20,316,904 19,470,289
Accuracy Low: .68 Low: .82 Low: 1.03 Low: 1.14
High: 1.46 High: 1.69 High: 1.46 High: 1.43
Range: .78 Range: 0.87 Range: 0.43 Range: 0.29
O()n
πn
2
-------
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