What should I know about the sizes and speeds of computers? - The Tao of Computing - page 147

or 963,040 corn kernels, which is about 13 1 4 bushels. Although this amount was still
relatively small, the numbers were getting larger, and only three of the eight rows of the
board had been considered.
During the counting for the next row, the king thought ahead to the last (64th) square.
Following the pattern he now understood, this last square alone would cost 2 63 kernels
of corn—roughly 8 10 18 kernels or about 110,000 billion bushels! The obligation could
never be met. With a staggering debt, the king abdicated his throne, and the mathemat
ically sophisticated Paul became monarch of the kingdom.*
* To put this number in perspective, the world's annual production for corn in the mid
1980s was roughly 17.7 billion bushels a year. Thus, even in modern times, it would
take roughly 6,215 years for the world to grow enough corn for payment for this last
square. Paul's entire payment would take about twice this long, or about 12,430 years,
using modern technology.
What made Paul's Option 2 payments so huge?
In reviewing the fable, the key to the huge payments involves the
doubling of the kernels of corn for each square. If, instead, the num
ber of kernels was increased by two for each square, then the pay
ments would have been much more modest.
Square 1 requires 1 kernel.
Square 2 requires 3 kernels.
Square 3 requires 5 kernels.
Square 4 requires 7 kernels.
Square i requires 2 i 1 kernels.
Square 64 requires 127 kernels.
Overall, this amounts to
1 3 5 . . . 127 4096
kernels of corn (about 0.056 bushels). Such an amount is quite
small indeed. The difficulty with the payment in the fable, therefore,
is not that the payment increased for each square; rather, it is that
the huge numbers came about because payments doubled.
How would other payment schemes affect the overall size of
payments? For example, what would happen if payments depended
upon a power of the number of squares considered? Suppose the