John Von Neumann was an Hungarian-born American mathematician that ...
If you are interested in learning more about Ada Lovelace’s story i...
#### Complex Number Calculator
The Complex Number Calculator desig...
### Delay lines
Delay lines are a form of computer memory. Delay l...
Here is a nicely formatted version of the [“First Draft of a Report...
The ENIAC was about 300 times faster than the Mark 1 at addition. A...
The sorting algorithm described by von Neumann would eventually be ...
Von Neumann's First Computer Program
DONALD E. KNUTH
Stanford University,* Stanford, California
An analysis of the two earliest sets of instruction codes planned for stored
program computers, and the earliest extant program for such a computer, gives
insight into the thoughts of John yon Neumann, the man who designed the
instruction sets and wrote the program, and shows how several important aspects
of computing have evolved. The paper is based on previously unpubhshed
documents from the files of Herman H. Goldstine.
Key words and phrases:
electronic computers, computer history, stored program
computers, machine organization and architecture, sorting, latency time, ENIAC,
EDVAC, order code, programming techniques
CR categories:
1.2, 6.0
INTRODUCTION
A handwritten document now in the posses-
sion of Dr. Herman H. Goldstine contains
what is probably the earliest extant program
for a stored program digital computer. Its
author, the remarkably talented mathema-
tician John von Neumann (1903-1957), was
in the process of refining the stored program
concept as he was writing this code; so his
program represents a significant step in the
evolution of computer organization as well
as of programming techniques. In this paper
we will therefore investigate the contents of
yon Neumann's manuscript in some detail,
attempting to relate its ideas to other de-
velopments in the early history of high
speed computing.
The program we will study is not what we
might expect an "ordinary" mathematician
to have written; it does not solve a partial
differential equation! Instead, it deals with
what was considered at that time to be the
principal example of a nonnumeric applica-
tion for computers, namely, the problem of
sorting data into nondecreasing order.
Von Neumann chose this application for
good reason. He had sketched out an order
* Computer Science Department
code for a stored program computer, with
numerical applications uppermost in his
mind; there was no question that his pro-
posed device could do the requisite arith-
metic operations. The key question was
whether or not the proposed instruction set
provided a satisfactory means of logical
control for complex processes, and so he felt
that a sorting program would be a most
instructive test case. Furthermore, the
existence of IBM's special purpose machines
for sorting gave him a standard against
which he could measure the proposed com-
puter's speed.
Before we start to study yon Neumann's
program, a few disclaimers are
in
order. In
the first place, he probably never intended to
have this program published and subjected
to such scrutiny; although his manuscript
is carefully documented, he probably wanted
only to circulate it among a few interested
colleagues. So when we find a few errors and
a few instances of clumsy coding, we should
realize that it was an early effort that was
not supposed to represent a polished product.
Second, we should realize that the histori-
cal interest of this program is in great
measure due to its connection with the de-
velopment of instruction codes for stored
Computing Surveys, Vol. 2, No. 4, December 1970
248
• D. E. Knuth
CONTENTS
Introduction 247-249
The Early
EDVAC
249-251
The Next EDVAC 252-253
The Sorting Program 253-257
Storage Allocation and Timing 257-258
The Sequel 258-259
References 259-260
Computing Surveys, Vol. 2, No. 4, December 1970
program computers; it is not the earliest in-
stance of a computer program. We have
Lady Lovelace's description of a program for
calculating Bernoulli numbers that Babbage
wrote for his Analytical Engine [1, Note G];
A. M. Turing's construction [16] of his
abstract Universal Machine, which involves
many important programming concepts;
Eckert and Mauchly's first sample program
for the ENIAC [4]; and a collection of
numerical programs, dating from 1944,
written by H. H. Aiken, G. M. Hopper,
R. V. D. Campbell, R. M. Bloch, B. J. Lock-
hart, and others, for the Harvard Mark I
[10, Chs. 4, 6].
A third precaution: The notation used in
this paper differs considerably from that
used by von Neumann, so that modern
readers can more easily understand what he
did. Where he would write, for instance,
15) c -}- (m' -- 1)(p ~- 1) ~-~ 14 [ p ~- 2,
we will use an equivalent assembly-like
language form,
MOVEIN PIK p~- 1, BUFFER, [YPTR].
This new notation isn't completely trans-
parent, but it seems to be an improvement
which doesn't go so far that the machine is
obscured. (For further information about
yon Neumann's original notation, see the
section on Storage Allocation and Timing.)
To set the stage for our story, let us con-
sider briefly the developments prior to 1945
when yon Neumann wrote his sorting pro-
gram. Several electromechanical calculators
were essentially operational in the late 1930s
and early 1940s: those of Stibitz [15] and
Aiken [10] in America, and Zuse [3] in
Germany. Another machine, which had
electronic circuitry for arithmetic although
it was slowed down by mechanical memory
elements, was also developed in the late
1930s at Iowa State College, by John V.
Atanasoff and Clifford E. Berry [see 12];
this machine was designed to solve sets of
simultaneous linear equations.
In August 1942, John W. Mauchly of the
Moore School of Electrical Engineering in
Philadelphia wrote a memorandum to his
colleagues summarizing briefly the ad-
Von Neumann's First Computer Program * 249
vantages which could be expected from an
electronic high speed computer such as he
felt could reasonably be developed. He was
familiar with previous American develop-
ments in computing, and he was also aware
of the extensive calculations needed by the
Ballistic Research Laboratory (BRL) in
connection with World War II; many of
these calculations were currently being done
on a Differential Analyzer at the Moore
School. It was by no means obvious that a
useful electronic computer could be built;
but Mauchly and a young electrical engineer
named J. P. Eckert, Jr., drew up a tentative
technical outline of a suitable machine, and
Prof. J. G. Brainerd decided it was worth the
risk of committing the Moore School to a
major effort in this direction. A technical
proposal was submitted to Col. Leslie E.
Simon, Col. Paul N. Gillon, and Lt. Herman
H. Goldstine of the BRL in the spring of
1943, and in a remarkably short time the US
government entered into a contract with the
Moore School for research and development
of high speed electronic calculating devices,
beginning July 1, 1943. The project, super-
vised by Brainerd, had Eckert as chief
engineer, Mauchly as principal consultant,
and Goldstine in charge of technical liaison
with BRL. A first machine, the ENIAC
(Electronic Numerical Integrator And Com-
puter), was soon designed, and its design was
frozen at an early stage so that future efforts
could be concentrated on its production and
testing; it was dedicated on February 15,
1946. (For further details about the develop-
ment of the ENIAC, see [6].)
The ENIAC was a highly parallel com-
puter; weighing over 30 tons, it involved
over 19,000 vacuum tubes, 1500 relays, etc.
Because of its electronic circuitry, it was
considerably faster than any computing
machine previously built. But it had only 20
words of internal memory, and it required
complicated manual operations for setting
up a program on plugboards. Long before
ENIAC was completed, it became clear to
the designers that they could utilize the
equipment more efficiently if they would
adopt serial methods instead of so much
parallelism; so in January 1944 they sketched
out a "magnetic calculating machine" in
which successive digits of numbers were
transmitted serially from a memory device
to central electronic computing circuits and
back again. Early in 1944, Eckert and
Mauchly invented an acoustic delay-line
memory device which made it possible to
obtain a fairly large storage capacity with
comparatively little hardware; so it became
evident that great improvements over
ENIAC could be made, at considerably less
cost. "Therefore, by July, 1944, it was
agreed that when work on the ENIAC
permitted, the development and construc-
tion of such a machine should be undertaken.
This machine has come to be known as the
EDVAC (Electronic Discrete VAriable
Computer)" [5].
In the latter part of 1944, John yon Neu-
mann (a consultant to BRL) became a
consultant to the EDVAC project. He con-
tributed to many discussions on logical
circuitry, and he designed the order code
which was to be used. In the spring of 1945,
he wrote a preliminary report [17] which
gives a detailed discussion of arithmetic
circuitry and the motivation for various
design decisions which were made as EDVAC
evolved. This takes us to the beginning of
our story.
THE EARLY EDVAC
VOD Neumann's first draft report [17, 18] on
the EDVAC proposed building a serial
computer with three 32-bit registers and
8192 32-bit words of auxiliary memory. The
three registers were called i and j (for inputs
to the arithmetic circuitry) and o (for out-
put) ; for convenience in what follows we will
denote these registers by the upper-case
letters I, J, and A. The EDVAC memory
was to be divided into 256 "tanks" of 32
words each, operating in a cyclic fashion.
Word 0 of each tank would pass a reading
station one bit at a time, then (32 bit-times
later) word 1 would be available,..., finally
word 31, then word 0 again, etc. Thus the
accessing of information from tanks is essen-
tially the same as we now have from drums
or head-per-track disks. A bit-time was to be
1 #sec, so the cycle time for each tank came
Computing Surveys, Vol 2, No. 4, December 1970