Information Technology Reference
In-Depth Information
B.5.2. Donald Knuth with his series of topics called The Art of Computer Programming has made a
major contribution to the cataloging and systematic analysis of algorithms. This topic is generally
accepted as the “gold standard” in the field. Knuth offered a prize of one hexadecimal dollar, that
is, $2.56, for each error found in his topics. These checks are considered to be trophies in aca-
demic circles. While writing his topic, Knuth also developed the TeX typesetting software that is
still very widely used. After winning a programming competition in the 1960s, Knuth was asked
how he managed it. He replied: “When I learned how to program, you were lucky if you got five
minutes with the machine a day. If you wanted to get the program going, it just had to be written
right. So people just learned to program like it was carving in stone. You have to sidle up to it.
That's how I learned to program.” B1
Numerical algorithms
In Chapter 1 we saw that the ENIAC computer was originally built to cal-
culate the trajectories of shells for artillery tables. In mathematics, the solu-
tion to this trajectory problem is obtained by solving the differential equation
that arises from an application of Newton's laws of motion. On a computer,
such differential equations must be approximated using some numerical
method.
Let's look at a simple example. Suppose we have an object falling under
the force of gravity. To find the velocity of the object at any given time, we need
to solve Newton's law for the rate of change of velocity with time. If we assume
that the object is dropped from rest, we can calculate the velocity at any later
time using Newton's law in the form of a differential equation. Mathematically
we can treat the velocity and time values as varying “continuously.” However,
computers can only store individual “discrete” values of the velocities and
time - such as the velocity after one second, the velocity after two seconds and
so on. We need to approximate the differential equation by splitting up the
time variable into very small increments. We can then calculate the approxi-
mate incremental change of velocity for each small increment of time. There
are many different “numerical methods” that can be used to find such approx-
imate solutions to differential equations on a computer. The simplest numeri-
cal approximation is a method devised by the Swiss mathematician Leonhard
Euler ( B.5.4 ). In practice, Euler's method is not very precise and there are more
accurate numerical methods available to solve such differential equations.
Figure 5.3 shows how Euler's method compares to the exact solution for the
problem of finding the velocity of an object falling under gravity through a
fluid, and subject to a resistance proportional to the square of the velocity. It
was the FORTRAN programming language that first gave scientists the capabil-
ity of writing their programs as a relatively straightforward translation of their
mathematical equations, instead of having to program the solutions to these
problems using low-level machine language or assembly language.
Another important numerical technique for simulations goes by the name
of the “Monte Carlo” method. In 1946, physicists at Los Alamos Laboratory
were investigating the distance that neutrons can travel through various
B.5.3. David Harel gave a series of
lectures on Israeli radio in 1984
explaining computer algorithms to
a general audience. This led to his
famous topic Algorithmics: The Spirit
of Computing and to his more recent
topic on computability entitled
Computers Ltd: What they really can't do .
Search WWH ::




Custom Search