Information Technology Reference
In-Depth Information
Now that we know that the formula used for successive squares
influences the end result, what role does the size of the chessboard
play? For example, suppose a board had 20 or 50 or 100 squares.
What payments would the king have owed Paul? (You will explore
these computations in the endofchapter exercises.)
Although it may seem a bit corny to consider such kernels in a
textbook about computing, similar issues arise in analyzing various
solutions to problems. In this fable, a plan for payment was chosen
that could never practically be completed. Similar difficulties arise
in many situations where computers are used as part of a proposed
solution to a problem. In computing applications, however, it is of
ten hard to appreciate the amount of work or the number of re
sources required to do a task, because computers seem to work at
such tremendous speeds and they can store such vast amounts of
data. For example, it can be hard to comprehend the significance of
such measures as a million (10
6
) instructions per second (MIPS) or
storage for 10
9
characters (a gigabyte).
In computing and mathematics, the term
combinatorial explo-
sion
is used to describe the situation when the work (or space) re
quired to solve a problem increases by a factor of two or three or
more for each successive value of
n
. Paul's original payment scheme
(doubling the number of corn kernels for each square) is one exam
ple of the combinatorial explosion. The two alternatives just given
provide further examples.
Although I have already noted that computer technology contin
ues to evolve at a rapid pace, this fable reminds us that some prob
lems require a remarkable level of resources. Even with extremely fast
computer speeds and large capacities, some problems require more
resources than computers have now or may ever have in our lifetimes.
With advancing technology, we may take for granted the amount of
computing power at our disposal, and this can cause us to overesti
mate the ability of computers to solve a problem efficiently. So, when
we look at new technology, we need to consider how well it will work
when dealing with huge amounts of information given that, in com
binatorial explosive situations, the computer may need to process
enormous amounts of information. Paul's scheme causes a problem
for the king when it mathematically explodes—so, too, do problems
