PDF Download

[Link]
30 January 2026
Total Citations: 41
Total Downloads:
.
.
12070
Latest updates: hps://[Link]/doi/10.1145/356580.356581

.
.
.
Published: 01 December
.
ARTICLE 1970
Von Neumann's First Computer Program

.
.
Citation in BibTeX format

.
DONALD E. KNUTH, Stanford University, Stanford, CA, United

.
States
.
.
.
Open Access Support provided by:
.
Stanford University
.
ACM Computing Surveys (CSUR), Volume 2, Issue 4 (December 1970)
hps://[Link]/10.1145/356580.356581
EISSN: 1557-7341
.
Von N e u m a n n ' s First C o m p u t e r 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 code for a stored program computer, with

numerical applications uppermost in his
A handwritten document now in the posses- mind; there was no question that his pro-
sion of Dr. Herman H. Goldstine contains posed device could do the requisite arith-
what is probably the earliest extant program metic operations. The key question was
for a stored program digital computer. Its whether or not the proposed instruction set
author, the remarkably talented mathema- provided a satisfactory means of logical
tician John von Neumann (1903-1957), was control for complex processes, and so he felt
in the process of refining the stored program that a sorting program would be a most
concept as he was writing this code; so his instructive test case. Furthermore, the
program represents a significant step in the existence of IBM's special purpose machines
evolution of computer organization as well for sorting gave him a standard against
as of programming techniques. In this paper which he could measure the proposed com-
we will therefore investigate the contents of puter's speed.
yon Neumann's manuscript in some detail, Before we start to study yon Neumann's
attempting to relate its ideas to other de- program, a few disclaimers are in order. In
velopments in the early history of high the first place, he probably never intended to
speed computing. have this program published and subjected
The program we will study is not what we to such scrutiny; although his manuscript
might expect an "ordinary" mathematician is carefully documented, he probably wanted
to have written; it does not solve a partial only to circulate it among a few interested
differential equation! Instead, it deals with colleagues. So when we find a few errors and
what was considered at that time to be the a few instances of clumsy coding, we should
principal example of a nonnumeric applica- realize that it was an early effort that was
tion for computers, namely, the problem of not supposed to represent a polished product.
sorting data into nondecreasing order. Second, we should realize that the histori-
Von Neumann chose this application for cal interest of this program is in great
good reason. He had sketched out an order measure due to its connection with the de-
* Computer Science Department velopment of instruction codes for stored

Computing Surveys, Vol. 2, No. 4, December 1970

 248 • D. E. Knuth

CONTENTS 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
Introduction 247-249 many important programming concepts;
The Early E D V A C 249-251 Eckert and Mauchly's first sample program
The Next EDVAC 252-253 for the ENIAC [4]; and a collection of
The Sorting Program 253-257
numerical programs, dating from 1944,
written by H. H. Aiken, G. M. Hopper,
Storage Allocation and Timing 257-258
R. V. D. Campbell, R. M. Bloch, B. J. Lock-
The Sequel 258-259
hart, and others, for the Harvard Mark I
References 259-260
[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-

Computing Surveys, Vol. 2, No. 4, December 1970

 Von Neumann's First Computer Program * 249

vantages which could be expected from an which successive digits of numbers were
electronic high speed computer such as he transmitted serially from a memory device
felt could reasonably be developed. He was to central electronic computing circuits and
familiar with previous American develop- back again. Early in 1944, Eckert and
ments in computing, and he was also aware Mauchly invented an acoustic delay-line
of the extensive calculations needed by the memory device which made it possible to
Ballistic Research Laboratory (BRL) in obtain a fairly large storage capacity with
connection with World War II; many of comparatively little hardware; so it became
these calculations were currently being done evident that great improvements over
on a Differential Analyzer at the Moore ENIAC could be made, at considerably less
School. It was by no means obvious that a cost. "Therefore, by July, 1944, it was
useful electronic computer could be built; agreed that when work on the ENIAC
but Mauchly and a young electrical engineer permitted, the development and construc-
named J. P. Eckert, Jr., drew up a tentative tion of such a machine should be undertaken.
technical outline of a suitable machine, and This machine has come to be known as the
Prof. J. G. Brainerd decided it was worth the EDVAC (Electronic Discrete VAriable
risk of committing the Moore School to a Computer)" [5].
major effort in this direction. A technical In the latter part of 1944, John yon Neu-
proposal was submitted to Col. Leslie E. mann (a consultant to BRL) became a
Simon, Col. Paul N. Gillon, and Lt. Herman consultant to the EDVAC project. He con-
H. Goldstine of the BRL in the spring of tributed to many discussions on logical
1943, and in a remarkably short time the US circuitry, and he designed the order code
government entered into a contract with the which was to be used. In the spring of 1945,
Moore School for research and development he wrote a preliminary report [17] which
of high speed electronic calculating devices, gives a detailed discussion of arithmetic
beginning July 1, 1943. The project, super- circuitry and the motivation for various
vised by Brainerd, had Eckert as chief design decisions which were made as EDVAC
engineer, Mauchly as principal consultant, evolved. This takes us to the beginning of
and Goldstine in charge of technical liaison our story.
with BRL. A first machine, the ENIAC
(Electronic Numerical Integrator And Com-
puter), was soon designed, and its design was THE EARLY EDVAC
frozen at an early stage so that future efforts
could be concentrated on its production and VOD Neumann's first draft report [17, 18] on
testing; it was dedicated on February 15, the EDVAC proposed building a serial
1946. (For further details about the develop- computer with three 32-bit registers and
ment of the ENIAC, see [6].) 8192 32-bit words of auxiliary memory. The
The ENIAC was a highly parallel com- three registers were called i and j (for inputs
puter; weighing over 30 tons, it involved to the arithmetic circuitry) and o (for out-
over 19,000 vacuum tubes, 1500 relays, etc. put) ; for convenience in what follows we will
Because of its electronic circuitry, it was denote these registers by the upper-case
considerably faster than any computing letters I, J, and A. The EDVAC memory
machine previously built. But it had only 20 was to be divided into 256 "tanks" of 32
words of internal memory, and it required words each, operating in a cyclic fashion.
complicated manual operations for setting Word 0 of each tank would pass a reading
up a program on plugboards. Long before station one bit at a time, then (32 bit-times
ENIAC was completed, it became clear to later) word 1 would be a v a i l a b l e , . . . , finally
the designers that they could utilize the word 31, then word 0 again, etc. Thus the
equipment more efficiently if they would accessing of information from tanks is essen-
adopt serial methods instead of so much tially the same as we now have from drums
parallelism; so in January 1944 they sketched or head-per-track disks. A bit-time was to be
out a "magnetic calculating machine" in 1 #sec, so the cycle time for each tank came

Computing Surveys, Vol 2, No. 4, December 1970

250 • D. E. Knuth

t o 32 × 32 = 1024 ~sec. T h e t a n k s were t o w h e r e a = aoala2a3a4 d e n o t e d a n o p e r a t i o n

be c o n s t r u c t e d f r o m E c k e r t a n d M a u c h l y ' s code, b = boblb2 d e n o t e d a v a r i a n t , y --
m e r c u r y d e l a y lines; t h i s c o n c e p t w a s l a t e r y0 + 2yl + 4 y 2 . + 8y3 Jr 16y4 d e n o t e d a
u s e d in t h e m e m o r y of t h e U N I V A C I word position within a tank, and x =
c o m p u t e r (1951). A l t h o u g h y o n N e u m a n n x0 + 2Xl -4- . ' . + 128x7 d e n o t e d a t a n k
r e a l i z e d t h a t f a s t e r o p e r a t i o n c o u l d be n u m b e r . T h e following a r i t h m e t i c o p e r a t i o n
achieved with a random-access memory, the c o d e s were p r o p o s e d , affecting t h e r e g i s t e r s
o n l y k n o w n w a y of b u i l d i n g such m e m o r i e s I, J, and A :
e c o n o m i c a l l y w a s t h e " i c o n o s c o p e " (like a
• AD (a = 00000). SetA (--IA-J.
T V t u b e , w i t h l i g h t or d a r k s p o t s c r e a t e d a n d • SB (a = 00001). SetA ~--I- J
s e n s e d b y a n e l e c t r o n b e a m ) , a n d he t e m - *ML (a = 00010). Set A (-- A -4- I X J
p o r a r i l y r e j e c t e d i t since its r e l i a b i l i t y w a s (rounded).
still u n p r o v e d . • DV (a = 00011). Set A ~-- I / J (rounded).
E a c h 3 2 - b i t w o r d w a s e i t h e r a n u m b e r or • SQ (a = 00100). Set A ~-- ~/I (rounded).
a n i n s t r u c t i o n c o d e ; t h e first b i t w a s 0 for • I I (a = 00101). SetA~--l.
n u m b e r s a n d 1 for i n s t r u c t i o n s . V o n N e u - • JJ (a = 00110). S e t A ~--J.
• SL (a = 00111). if A > 0, set A ~-- I; if
m a n n s u g g e s t e d w r i t i n g b i n a r y n u m b e r s in
A < 0, s e t A ~ - - J
r e v e r s e order, w i t h t h e l e a s t significant • DB (a = 01000). Set A ~-- binary equivalent
d i g i t s a t t h e left, since b i n a r y n o t a t i o n w a s of decimal number I.
u n f a m i l i a r a n y w a y a n d since t h e serial • BD (a = 01001) Set A ~- decimal equiva-
c i r c u i t r y f o u n d it m o s t c o n v e n i e n t to process lent of binary number I.
l e a s t significant d i g i t s first. T h e l a s t b i t of a
n u m b e r , following t h e m o s t significant bit, (As s t a t e d in t h e I n t r o d u c t i o n , we are
was its sign; n u m b e r s were r e p r e s e n t e d in changing von Neumann's notation; the
two's complement notation. Thus the word m n e m o n i c s y m b o l s for t h e s e codes a r e a d hoc
s y m b o l s c o n t r i v 0 d solely for t h e p u r p o s e s of
boblb2b3 . . . b3ob31 , bo = O, the present paper. Note that multiplication,
division, a n d s q u a r e r o o t were t o p r o d u c e
denoted the number r o u n d e d r e s u l t s . N o t all d e t a i l s of t h e s e
2-~°bl + 2-2962 -}- 2-2Sb3 +4- " ' ' o p e r a t i o n s were f u l l y specified b y y o n
Neumann; division and square root would
+ 2-1b30 -- b31, c h a n g e t h e c o n t e n t s of I , b u t it is n o t c l e a r
t h a t a v a l i d r e m a i n d e r w o u l d be l e f t t h e r e .
a n d 3 0 - b i t f r a c t i o n s in t h e r a n g e - - 1 _~
The decimal-to-binary and binary-to-deci-
x < 1 were r e p r e s e n t a b l e . F o r a d d i t i o n ,
m a l o p e r a t i o n s w e r e n o t w o r k e d out. A p -
subtraction, and conversion operations, the
p a r e n t l y overflow c o n d i t i o n s c a u s e d no
n u m b e r c o u l d also be r e g a r d e d as t h e i n t e g e r
special a c t i o n . )
bl + 2b2 + 4b3 + ... + 229b30 - 23°b31, E a c h of t h e a b o v e a r i t h m e t i c o p e r a t i o n s
w a s to be u s e d w i t h one of s e v e r a l v a r i a n t s
so t h a t i n t e g e r s in t h e r a n g e - 2 3 0 ~ x < 23°
specified b y b = boblb2 :
were r e p r e s e n t a b l e . B i n a r y c o d e d d e c i m a l
i n t e g e r s (abcdefg)lo were also allowed, in t h e • H (b = 111). Do the operation as described
form above, holding the result in A.
• A (b = 100) Do the operation as described
0 0 0 0 ala2a3a4blb2b3b4 • • • glgsgag4, above, then set J *-- I, I ~-- A, A <-- 0.
• S (b = 000). Do the operation as described
w h e r e ala2aaa4 w a s t h e code for d i g i t a, a n d above, then store the result A in memory location
blb2b3b4 w a s t h e code for d i g i t b, etc., in yx and set A ~-- 0.
r e v e r s e b i n a r y o r d e r . ( T h u s 0000 = 0, • F (b = 101). Do the operation as described
1000 = 1, 0 1 0 0 = 2,---, 0001 = 8, above, then store the result into the word immedi-
1001 = 9.) ately following this instruction, set A ~ 0, and
I n s t r u c t i o n w o r d s were to h a v e t h e f o r m perform the altered instruction.
• N (b = 110) Do the operation as described
I aoa~aaa3a4bob~b2OOOOOOOOOOyoyly2y,[Link]~xaxax, xtX6XT, above, then store the result into the word immedi-

Computing Surveys, Vol. 2, No. 4, December 1970

 Von Neumann's First Computer Program • 251

a t e l y following t h i s i n s t r u c t i o n , s e t A ~-- 0, a n d multiplication, division, and square root

skip t h e a l t e r e d i n s t r u c t i o n . extraction, there was a little more leeway,
Thus, for example, ADS yx would have the since those operations actually were com-
effect of setting location yx to I -{- J, and pleted in about 950 ~sec.)
clearing A to zero; JJA would interchange The reader will note that much of the
the contents of I and J, and clear A; SLH space in instruction words is wasted. Von
would set A to either I or J, according as the Neumann realized this, but did not think it
previous sign of A was 0 or 1. (The memory important at the time, since [17, p. 96] the
specification yx was ignored on all variants programming problems he had considered
except S.) required only a small fraction of the memory
Besides arithmetic operations, the ma- for instruction storage. But we will see that
chine could do the following: he changed his mind later.
• J M P (a --- "11000, b -- 000). T a k e the n e x t The machine we have considered here
i n s t r u c t i o n f r o m location yx ( t h e n 1 W yx, ete ). differs slightly from yon Neumann's de-
• L O D (a--- 10000, b = 000). S e t J ~ I , then scription iD [17], since the modifications
s e t I to t h e c o n t e n t s of m e m o r y l o c a t i o n yx. stated in his letter [18] have been included.
He wrote, from Los Alamos to Philadelphia,
Further codes a = 01010, 01011, 01100,
"The contents of this letter belong, of course,
01101, 01110, 01111 were reserved for input
and output operations (which were not yet into the manuscript [17], and I will continue
specified) and stopping the machine. the manuscript and incorporate these things
There was an important exception to the also, after I get it back from you--if possible
operations as we have described them: Only with c o m m e n t s . . , from you, Pres Eckert,
numbers (not instructions) ever appeared ill John Mauchly, and the others." But the
the registers I, J, and A. When the LOD manuscript was never completed, nor were
operations specified a memory address con- the modifications inserted when it was typed
taining an instruction, only the yx part of a month later, presumably because there
that instruction was to be loaded into I; were so many other things to be done. It is
the other bits were cleared. Conversely, when interesting to note that yon Neumann's
storing into memory by means of variants letter [18] also proposed the design of a
S, F, and N, only the least significant 13 special typewriter for preparing programs
bits of the number in A were to be stored from partially mnemonic input. Pushing a
in the yx part, if the memory location con- key marked -[- would cause the bits 100000
tained an instruction word. to be assembled (the first six bits of an addi-
Instructions were to be executed from tion instruction); then a key marked H
consecutive locations, unless the sequence of would insert the subsequent bits 111000...00,
control was modified by a JMP order. If forming a complete instruction word on a
the control sequence would come across a magnetic tape.
number (not an instruction word), the effect
The differences between [17] and the
would be as if an LOD instruction were per-
formed referring to this number. machine described here are chiefly concerned
with improvements in the logistics of instruc-
Most instructions would be performed in
tion modification. (a) There was no variant
one word-time, so that the machine could
N; instead, variant F would not treat the
keep up with the speed of the long tanks
where instructions were stored. But multi- altered word as an instruction if it turned
plication, division, square root, and radix out to be a number. (b) The convention on
conversion took 33 word-times (1056 ~sec). loading only 13 bits of instructions was not
References to memory, by means of LOD present (although the convention about
operations and the S variant, would require storing only 13 bits into instruction words
an additional 1024 ~sec unless the memory was). (c) Three other variants, like S, A, F
address was perfectly synchronized to match but not clearing register A, were originally
the following word of instructions. (For included.

Computing Surveys, Vol. 2, No. 4, December 1970

252 • D. E. Knuth

THE NEXT EDVAC number of registers, and the old I and J

disappeared. Block transfer operations be-
Von Neumann's letter says, " I have also tween the short and the long tanks made
worked on sorting questions . . . . I will many processes faster. The tentative plans
write you about the details very soon." He in [5] call for 32 short tanks, and 2048 addi-
said that he had written an internal sorting tional words in 64 long tanks. "Combining
program requiring about 130 words of in- this with the almost unlimited memory
structions; it could sort 500 p-word items capacity of the magnetic tape (even though
on a one-word key in about 1 + .425 (p -- 1) the numbers are not available here so
minutes. "I suspect that these arrangements, quickly) it seems that very few problems
which represent only a first attempt, could will exceed this capacity" [5, p. 81].
be improved . . . .
Here are the basic operations allowed by
" A t any rate the moral seems to be that the new EDVAC code, exclusive of multi-
the EDVAC, with the logical controls as plication and division [let C(s) denote the
planned for 'mathematical' problems, and contents of short tank number s]:
without any modifications for 'sorting'
problems, is definitely faster than the *PIK s,t,x Transfer s consecutive words,
[contemporary I B M sorters, about 400 s t a r t i n g at long tank location x, to s consecutive
cards/minute] . . . . Since the I B M ' s are s h o r t tanks, s t a r t i n g at s h o r t tank n u m b e r t. If x
is unspecified, the next s words following this
really very good in sorting, and since accord-
instruction are used, and the (s + 1)-th is the next
ing to the above, sorting can be meshed with instruction
the other operations of the EDVAC without *PUT s,t,x T r a n s f e r s consecutive words,
human intervention or need for additional s t a r t i n g at short tank n u m b e r t, to s consecutive
equipment, etc., the situation looks reason- long tank positions s t a r t i n g at location x. If x is
ably satisfactory to me . . . . It is legitimate unspecified, the next s words following this instruc o
to conclude already on the basis of the now tion are used, and the (s + 1)-th is the next in-
available evidence, that the EDVAC is struction.
very nearly an 'all-purpose' machine, and * A D D s,t. S e t A (--C(s) + C(t).
- S U B s,t. S e t A ~-C(s) - C(t).
that the present principles for the logical
* S E L s,/ I r A ~ O, s e t A ~ - - C ( s ) ; i f A ~ O,
controls are sound." set A ~-- C(t)
But von Neumann's code for this sorting • T R A x. Go to long tank location x (then x +
program does not seem to have survived; we 1. etc.) for subsequent instructions
can only say that his timing estimates look • J M P s. Go to s h o r t tank n u m b e r s (then
reasonable, since for large p they come to s + 1, etc ) for s u b s e q u e n t instructions.
slightly over 5 msec per pass per word • S T O s . Set C(s) ~--A.
transferred. The program which now is in • SET s,t SetC(s)(--C(t)
Dr. Goldstine's files is roughly 80 times As before, operations which did not refer to
faster, due to important improvements in long tank addresses took just one word-
machine organization which yon Neumann time (32 t~sec), with the exception of "long"
considered shortly afterward. This second arithmetic operations like multiplication and
EDVAC design was apparently never de- division. When a long tank location was
fined in as much detail as the previous one, specified, the machine waited until the
but a brief summary of its instruction codes desired word was accessible; at least two
appears in [5, p. 76] and we can deduce other word-times were needed for the instruction
properties by studying yon Neumann's T R A x , due to "long tank switching," if
program. Therefore we can reconstruct the the instruction was executed from a short
main features of the machine. tank.
The chief improvement incorporated into A distinction was made, as before, be-
this version of EDVAC was the introduction tween numbers and instruction words: When
of "short t a n k s " whose capacity was one STO or S E T attempted to store a new value
word each; this provided a small fast-access into an instruction word, only t h a t part of
memory which essentially increased the the instruction which specified a long tank

Computing Surveys, Vol. 2, No. 4, December 1970

 Von Neumann's First Computer Program • 253

location x was to be affected, and the value (a) n' < n, m' < m. There are two sub-
in A was regarded as an integer• cases:
Tentative plans for representing the (al) key(x,,) _< key(y~,). Let zz = xn,,
instructions in memory are discussed briefly and replace (l, n', m') by (l + 1, n' + 1, m').
in [5, pp. 83-86]. (a2) key(x,,) > key(y~,). Let zz = y~,,
and replace (/, n', m') by (l + 1, n', m' + 1).
(l~) n' < n, m' = m. Same action as
(al).
THE SORTING PROGRAM (~) n' = n, m' < m. Same action as
Now we are ready to discuss von Neumann's (a2).
program• His manuscript, written in ink, is (6) n' -- n, m' = m. The process has
23 pages long; the first page still shows been completed.
traces of the penciled phrase " T O P His program is divided up according to
S E C R E T , " which was subsequently erased• cases in this same way (sort of a "decision
(In 1945, work on computers was classified, table" arrangement). In order to make his
due to its connections with military prob- coding reasonably easy to follow, it is trans-
lems.) A facsimile of page 5, the first page of literated here into a symbolic assembly
the program itself, appears as Figure 1. language such as people might use with the
Von Neumann begins his memo by de- machine if it existed today. We use the
fining the idea of sorting records into order, pseudo-operation a R S T k (RST means
and of merging two strings of records that "reserve short t a n k " ) to mean that symbol
have been sorted separately into a single is to refer to the first of k consecutive short
sorted sequence. Then he states the purpose tank locations. The first R S T in a program
of the program: "We wish to formulate reserves short tank number 0, and short
code instructions for sorting and for mesh- tanks are reserved consecutively thereafter•
ing [i.e. merging], and to see how much The other notations of our assembly lan-
control-capacity they tie up and how much guage are more familiar: " E Q U " denotes
time they require." "equivalence", " C O N " denotes an integer
constant, an asterisk denotes the current
He never actually gets around to coding
location, and " * * " denotes an address
the entire sorting routine in this document;
which will be filled in dynamically as the
only the merging process is described. For
program runs.
the merging problem, we assume that n
records Xo, xx, • • • , x,_x are given, consist- Von Neumann's first step in coding the
ing of p words each; the first word of each program was to consider the four-way divi-
record is called its " k e y , " and we have sion into cases; see (A). (Note: All numbers
key(xo) _< key(x1) _< . - . < key(x,_l). An manipulated in the program are treated as
additional m p-word records y0, y l , " " , integers.) This code assumes t h a t the short
tank locations have been set up appropri-
ym-1 are also given, with key(y0) _< key(yl) g
ately; in particular, location S W I T C H
• .- < key(y~_l); the problem is to put the
contains a T R A instruction. The code in (A)
x's and y's together into the merged se-
(line 22) sets the address of that T R A to
quence go, zl, . . . , z,+,~-i, in such a way either ALPHA, B E T A , GAMMA, or
that key(zo) _< key(z1) g . . - < key(z,+~_l). DELTA.
He formulated the merging method as Next comes the code for routines (a), (f~),
follows (based on a procedure then used (~), and (6); see (B). Here we have a rather
with the I B M collator): Assume that we awkward piece of coding; von Neumann
have found the first l records Zo, . . . , thought of a tricky way to reduce cases (f~)
z~_l, where 0 _< l _< n + m; and assume and (~,) to case (a) by giving artificial
further t h a t these l records consist of Xo, values 0 and - 1 to key(y~,) - key(x,,).
• • , x,,_l and Yo, • • • , y~,,-1 in some order,
• But he didn't realize the far simpler approach
w h e r e 0 _ < n' _< n, 0 < m' < m, a n d n ' - l - of making (8) and (~) identical, respec-
m ~ = l. There are four cases: tively, to (al) and (a2). Thus, he could have

Computing Surveys, Vol. 2, No. 4, December 1970

254 • D.E. Knuth

X:,~5 ) ~ ~,, z, , ... :

¢) T Y, o) w ' . ~ ' - . ~ . , . ~
~,) ~ . , 7,, ,,'> , . : ,~ ,.,., -:/t.....,-
~,) a- -. 7i, ~2) / ¢ " / r .,o, "d,"," " , ' . ~ ",-

.- ~ . ) ... ~ "~
~,.~.

/o,) ~ - . ~" I

Ab/A~I~¢

7~,..,..,, . , ~ , , ~ .,.,.,.~.,,-f" ,'¢.~ ~ ~.,:, ~ a, /,,, /,, /,.,

c,~,) ~ co,,.v, --,',.~-~,/-,.~/',-- ~ "~,-~ "I" < ~ 2 .

FIG. 1. T h e original m a n u s c r i p t .

simply changed line 27 to "SEL BETA, the program. This would have saved four of
GAMMA", omitting lines 24, 25, 30, 31, 32, the precious short tank locations, and it
33, 34, 35 entirely, and then he could have would have made the calculation slightly
used BETA and GAMMA instead of faster. Similarly line 36 is unnecessary, since
ALPHA1 and ALPHA2 in the remainder of location E X I T could be stored in LDELTA.

Computing Surveys, Voi. 2, No. 4, December 19T0

 Von Neumann's First Computer Program • 255

(A)
Line no. Location Op Address(es) Remarks
I NPRIME RST 1 n'
2 MPRIME RST 1 m~
$ XKEY RST 1 key(x.,)
4 YKEY RST 1 key(y~,,)
5 N RST 1 n
6 M RST 1 m
7 LALPHA RST 1 Location ALPHA
8 LBETA RST 1 Location BETA
9 LGAMMA RST 1 Location GAMMA
10 LDELTA RST 1 Location DELTA
11 SWITCH RST 1 Instruction TRA **
12 TEMP1 RST 1 Temporary storage
IS TEMP2 RST 1 Temporary storage
14 COMPARE SUB NPRIME,N A , - - n ' - n.
15 SEL LGAMMA, LALPHA A ~- i f n' ~ n t h e n GAMMA e l s e ALPHA.
16 STO TEMP1 TEMP1 *-- A.
17 SUB NPRIME,N A ~-- n' - n.
18 SEL LDELTA, LBETA A ~-- i f n ~ ~ n t h e n DELTA e l s e BETA.
19 STO TEMP2 TEMP2 ~-- A.
20 SUB MPRIME,M A (-- m' -- m.
21 SEL TEMP2,TEMP1 A ~- i f m' ~ m then[TEMP2]eise[TEMP1].
22 STO SWITCH SWITCH ~-- TRA [A].
~S JMP SWITCH

(B)
Lint no. Locat*on Op Address(es) Rcmarhs
24 LALPHAI RST 1 Location ALPHA1
25 LALPHA2 RST 1 Location ALPHA2
$6 ALPHA SUB YKEY,XKEY A ~-- key(y~,) -- key(x~,).
27 SEL LALPHA1,LALPHA2 i r a _~ 0 t h e n ALPHA1 e l s e ALPHA2.
28 STO SWITCH
29 JMP SWITCH
20 ZERO RST 1 0
Sl MONE RST 1 --1
82 BETA SUB ZERO, ZERO A *- 0.
$8 TRA ALPHA+I Go to AI P H A + I .
$4 GAMMA SUB MONE,ZERO A ~-- - I .
S5 TRA ALPHA+I Go co A L P H A + I .
$6 DELTA TRA EXIT Merging is complete.

A p p a r e n t l y t h e i d e a of m a k i n g e q u i v a l e n t p e o p l e to s t u d y c a r e f u l l y ! O n t h e o t h e r h a n d ,
p r o g r a m s t a t e s i d e n t i c a l is n o t a n a t u r a l con- this particular manuscript was not merely a
c e p t , since e v e n y o n N e u m a n n m i s s e d i t r o u g h s k e t c h , it w a s e v i d e n t l y p u t t o g e t h e r
here. w i t h some care, so it s e e m s f a i r to l o o k closely
( I t is p e r h a p s in b a d t a s t e to m a k e such a t it in a n a t t e m p t to d i s c e r n w h i c h a s p e c t s
d e t a i l e d c r i t i c i s m of t h e p r o g r a m m i n g , since of p r o g r a m m i n g were m o s t difficult in t h e i r
yon Neumann was not intending to write c o n c e p t i o n . T h e i d e a is n o t t o c h o r t l e o v e r
a n o p t i m u m p r o g r a m for s o r t i n g ; he w a s the fact that yon Neumann's program isn't
merely experimenting with a tentative order perfect; i t is r a t h e r to realize t h a t t h e im-
code. E v e r y g r e a t m a t h e m a t i c i a n h a s a p e r f e c t i o n s give s o m e historical insights,
w a s t e b a s k e t full of t h i n g s he d o e s n ' t w a n t b e c a u s e of w h e n t h e p r o g r a m w a s w r i t t e n . )

Computing Surveys, Vol. 2, No. 4, December 1970

 256 • D. E. Knuth

(C)
Line no. Location Op Address(es) Remarks
$7 XPTR RST 1 Location of x,,
38 YPTR RST 1 Location of y~,
39 ZPTR RST 1 Location of z,,+m,
40 SIZE RST 1 P
41 MOVEIN RST 1 Instruction PIK p+I,BUFFER,**
112 MOVEOUT RST 1 Instruction PUT p,BUFFER,**
]v5 RETURN RST 1 Instruction TRA BACK1 or BACK2
44 ONE RST 1 1
]~ BUFFER RST p+l Place for record being transferred
$6 ALPHA1 SET MOVEIN, XPTR MOVEIN ~- PIK pT1,BUFFER,[XPTR]
47 SET MOVEOUT, ZPTR MOVEOUT *-- PUT p,BUFFER, [ZPTR].
68 PIK 1, RETURN RETURN *- TRA BACK1
$9 [ TRA BACK1 (This line "picked.")
5O JMP MOVEIN Execute three commands in short tank.
51 BACK1 ADD NPRIME, ONE A*---n'+l.
52 STO NPRIME n'*--A.
5S SET XKEY, BUFFER+p Update key(x.,).
54 ADD XPTR,SIZE A *- [XPTR]+p.
55 STO XPTR Update location of x~,.
56 ADD ZPTR, SIZE A ~-- [ZPTR]+p.
57 STO ZPTR Update location of z,,+m,.
58 TRA COMPARE Return to COMPARE.

The sorting program continues with the short tanks places limits on the record size p.
routine for case ( a l ) : I n (C) a block of (He says t h a t p _< 8 would be required if
p + 1 words (including the key for the next there were only 32 short tanks, while p < 40
record) is transferred into short tanks, and if there were 64; perhaps he was purposely
p words are m o v e d into the z area. This is a wasting short tanks, in order to convince
good way to avoid the latency problems of other people t h a t at least 64 short tanks are
delay-line memories, and it accounts for the desirable !)
considerable increase in speed in this pro- We need not discuss the code for (a2),
gram compared to what was possible with the since it is essentially the same as t h a t for
first E D V A C code. (al). All t h a t is left, therefore, is to write an
A slight i m p r o v e m e n t could be made here initialization routine t h a t gets everything
if Z P T R were omitted, letting M O V E O U T started properly. F o r this purpose, yon
keep track of tile current z location; a short N e u m a n n juggled the short t a n k locations so
t a n k would be saved, as well as the instruc- t h a t the six which are set up from outside
tion in line 47 (and a similar instruction for this routine (namely N, M, X P T R , Y P T R ,
case (,2)). H o w e v e r this trick would have Z P T R , S I Z E ) come first; t h e n come two
made the setup somewhat less symmetrical. which are somewhat special (namely X K E Y
Line 58 could have been omitted if the code and Y K E Y , which must contain key(x0)
for C O M P A R E were placed right after line and key(y0)); then come 14 which are to be
57. If line 51 were changed to " S U B set to certain constant values; and then
NPRIME,MONE", another short t a n k come the remaining " s c r a t c h " locations.
could h a v e been saved. Since yon N e u m a n n Figure 2 shows the resulting complete pro-
didn't mention these simplifications, while gram, including the initialization of the
his work on logic design strongly suggests short tanks. (At this point in his discussion,
t h a t he would h a v e t h o u g h t of them, it is yon N e u m a n n a p p a r e n t l y forgot about
plausible to say t h a t he w a s n ' t especially T E M P 1 and T E M P 2 ; Figure 2 assigns t h e m
concerned with saving space in short tanks, to the buffer area.)
although he does mention t h a t the scarcity of Like nearly all programs, this one has a

Computing Surveys, Vol. 2, No. 4, December 1970

 Von Neumann's First Computer Program • 257

N RST I PIK I,RETURN 6+49

M RST 1 [ TRA BACKI ¢+50
XPTR RST 1 JMP MOVEIN e-i-51
YPTR RST 1 BACKI ADD NPRIME,ONE e-t-56
ZPTR RST 1 STO NPRIME e+57
SIZE RST 1 SET XKEY,BUFFER+p e+58
XKEY RST 1 ADD XPTR,SIZE e-i-59
YKEY RST 1 STO XPTR a+60
NPRIME RST 1 ADD ZPTR,SIZE e+61
MPRIME RST 1 STO ZPTR ¢~+62
LALPHA RST 1 TRA COMPARE ~+63
LBETA RST 1 ALPIdLA2 SET MOVEIN,YPTR e+6t
LGAMMA RST 1 SET MOVEOUT,ZPTR e+65
LDELTA RST 1 PIK 1,RETURN ~+66
SWITCH RST 1 [T R A BACK2 e+67
LALPHA1 RST 1 JMP MOVEIN e-F68
LALPHA2 RST 1 BACK2 ADD MPRIME,ONE ¢+73
ZERO RST 1 STO MPRIME e+74
MONE RST 1 SET YKEY,BUFFER+p e-t-75
ONE RST 1 ADD YPTR,SIZE e+76
MOVEIN RST 1 STO YPTR e+77
MOVEOUT RST 1 ADD ZPTR,SIZE e+78
RETURN RST 1 STO ZPTR e+79
BUFFER RST p-}-I TRA COMPARE e+80
TEMPI EQU BUFFER+I BRING EQU NPRIME
TEMP2 EQU BUFFER+2 MERGE PIK 3,BRING e÷O
COMPARE SUB NPRIME,N e+27 PIK I,XKEY,** e-{-I
SEL
STO
SUB
SEL
LGAMMA,LALPHA
TEMPI
NPRIME,N
LDELTA,LBETA
e-F28
e-{-29
e+30
a+31
I PIK
TRA
SET
SET
I,YKEY,**
BACK3
BRING,XPTR
BRING+I,YPTR
e+2
~-F3
e+4
e+5
STO TEMP2 e+32 JMP BRING e+6
SUB MPRIME,M e+33 BACK3 PIK 14,NPRIME e+ll
SEL TEMP2,TEMP1 e-]-34 CON 0 e+12

I
STO SWITCH e+35 CON 0 e+13
JMP SWITCH e+36 CON ALPHA e+14
CON BETA e+15
ALPHA SUB YKEY,XKEY e+43
CON GAMMA e+16
SEL LALPHAI,LALPHA2 e+44
CON DELTA e-}-17
STO SWITCH e+45
TRA ** e+18
JMP SWITCH "e+46
CON ALPHA1 e+19
BETA SUB ZERO,ZERO e+39
CON ALPHA2 e+20
TRA ALPHA+I e+40 CON 0 e-}-21
GAMMA SUB MONE,ZERO e+41 CON --1 e+22
TRA ALPHA+I e+42 PIK p+I,BUFFER,** e+23
DELTA TRA EXIT e+81 PUT p,BUFFER,** c+24
ALPHA1 SET MOVEIN,XPTR e+47 _CON 1 e+25
SET MOVEOUT,ZPTR e+48 TRA COMPARE e+26

FIG. 2

bug: The second-last instruction " C O N 1" STORAGE ALLOCATION AND TIMING
actually belongs two lines earlier. If von
N e u m a n n had had an E D V A C on which to Although von N e u m a n n didn't use a sym-
run this program, he would have discovered bolic language to express his instructions, as
debugging i done here, his notation wasn't completely

Computing Surveys, Vol. 2, No 4, December 1970

258 • D. E. Knuth

numeric either. He used i l , 21, " " for short the other hand his allocation of ALPHA,
tanks NPRIME, MPRIME, etc. in the first BETA, and GAMMA vis-a-vis each other
piece of code, and later i s , ~2, "'" for the and the COMPARE routine was correctly
short tanks in the second, etc. Long tank handled; the instruction in SWITCH is not
locations were represented by unbarred a random memory reference, so his intuition
numbers with subscripts; for example, lines didn't mislead him here. (ALPHA1 and
32 and 33 in his notation were written as ALPHA2 .were placed badly; this was ap-
follows: parently an oversight.)
"18) ~ - ~ ~) ~ o Von Neumann discussed the relocatability
2~) 2~-+ ¢ of this routine by enumerating the nine
instructions which are variable (those whose
and from here on like (a) with 0,0 for codes depend on p, EXIT, or the relocation
xn0, y 0 .,, This was essentially a "regional" factor e). He didn't say exactly how these
addressing technique, which was used by instructions were to be changed after they
many programmers in the ensuing decade. have been read in from tape; he apparently
After having written the program, he did not yet realize that the limited EDVAC
assigned actual addresses to the subscripted code he had proposed (with no shift instruc-
ones. In order to make the code reloeatable, tions, for example) made it difficult to insert
for use as a general open subroutine, he p into the " P I K " and " P U T " instructions,
assigned the addresses relative to an un- since the machine could only store into the
specified starting location e. His address address field of instruction words.
assignments are shown in Figure 2 at the It is perhaps significant that he thought of
right of the instructions. this program as an open subroutine, not
He made an interesting and rather subtle closed, since he did not regard E X I T as a
error of judgment here, regarding latency parameter on a par with n, m, location(x0),
time. Since the instruction in location etc.
ALPHA1-}-4 (line 50 of the program in the He concludes his memorandum with an
preceding section) jumps into the short analysis of the running time, leading to a
tanks to execute three commands and total time of 2.60 + (n + m)(p/16 + 2.61)
transfer to BACK1, he didn't want BACK1 msec. (His actual figure was 1.61 instead of
to occupy location A L P H A I + 5 since the 2.61, due to a slip in arithmetic.) Some
long tank wouldn't be ready for that instruc- errors in the calculation of latency times,
tion until at least 33 word times after related to his misunderstanding cited above,
A L P H A I + 4 . So he intercalated 4 empty make this analysis slightly invalid; the
words between A L P H A I + 4 and BACK1, reader may verify that the actual running
"in order to avoid a delay of about one long time (averaged over all possible placements
tank." But since the instructions in of x0, y0, and z0 in the long tanks) is 3056 +
MOVEIN and MOVEOUT make essen- (n + m)(64p + 4016) ~sec. If we incorporate
tially random references to long tanks, an all of the improvements to the coding that
elementary argument can be given to prove have been mentioned above, the average
that the average computation time which time decreases to 2576 + (n + m)(64p +
elapses between the execution of instruction 2560) ~sec.
A L P H A I + 4 and the execution of instruc-
tion BACK1 is 2p + 49.5 word times, com-
pletely independent of the location of THE SEQUEL
BACKli Therefore BACK1 should really
have been placed so that its subsequent After World War II came to an end, the
instructions are optimally located, i.e. so original EDVAC group disbanded; Eckert
that the TRA COMPARE takes the least and Mauehly remained in Philadelphia, to
amount of time. Von Neumann inserted form their own company, while Goldstine
extra blank words into the initialization and yon Neumann went to the Institute for
routine for the same fallacious reason. On Advanced Study in Princeton. The veil of

Computing Surveys, Vol. 2, No. 4, December 1970

 Von Neumann's First Computer Program • 259

secrecy surrounding electronic computers every 48 ~sec, leaving four "blank" bits be-
was lifted when ENIAC was dedicated, and tween words. Further development work on
the great potential for high speed computing input/output devices was necessary before
was gradually realized by more and more EDVAC became operational late in 1951;
people. The principles of EDVAC's design then it continued steady and inexpensive
were very strong influences on all of the operation for many years, averaging, for
computers constructed during the next example, 145 hours of useful work per week
decade (see [14]). in 1961 [11]. It was finally retired from service
After yon Neumann's first two versions of in December 1962.
instruction codes had been digested by a For the story of yon Neumann's other
number of people, other variations began pioneering contributions to computing, see
to be proposed. In November 1945, Calvin Goldstine's recent account [6]. Goldstine and
N. Mooers devised a three-address code as yon Neumann published three important
an alternative to yon Neumann's idea; and supplements to [2] during the next years;
in August 1946, he lectured at the Moore these famous documents [7-9] formed the
School about a further development, the foundation for computer programming tech-
use of flagged data for terminating loops [13, niques, covering a wide range of topics from
Vol. 4, lect. 39]. Another interesting three- flowcharts to numerical analysis to reloeat-
address code, due to John Mauchly, was de- able loading routines. Reference [8, Sec. 11]
scribed by Eckert in the same series of lec- deals with sorting and merging in consider-
tures [13, Vol. 1, lect. 10]. Meanwhile yon able detail; von Neumann here put the fin-
Neumann had developed his ideas somewhat ishing touches onto the work he had sketched
further; he and Goldstine, in collaboration in 1945.
with Arthur W. Burks, prepared a mono-
graph which was to be the first widely cir- ACKNOWLEDGMENTS
culated document about high speed com-
puters, "Preliminary discussion of the logical I wish to thank Drs. Goldstine and Mauehly
design of an electronic computing instru- for considerable assistance in checking the
ment" [2]. By this time, their proposed ma- historical details presented in this paper,
chine had already changed somewhat dras- and for several delightfully informative dis-
tically: It was to have a random-access cussions.
(iconoscope) memory of 4096 40-bit words.
Instructions were 20 bits long, packed two
to a word. The operation codes had a differ- REFERENCES
ent flavor, too, resembling today's IBM
7094: "Clear and add x", etc. Left and right 1. AUGUSTA, ADA, COUNTESS OF LOVELACE.
Annotated transl, of Menabrea, L. F., Sketch
shift operations were included for the first of the Analytical Engine invented by Charles
time. Babbage. In Charles Babbage and h~s Cal(ulat-
~ng Engines (Phihp Morrison and Emily Mor-
The EDVAC project itself continued at rison, Eds.), Dover, New York, 1961, pp. 225-
the Moore School until August 1949, when 297; see also p. 68.
EDVAC was delivered to the BRL. In its 2. BURKS, ARTHURW., HERMAN H. GOLDSTINE,
ANn JOHN VON NEUMANN Preliminary discus-
final form, the EDVAC had a four-address sion of the logical design of an electronic com-
instruction code (the fourth address specify- puting instrument. Inst. for Advanced Study,
ing the location of the next instruction), de- Princeton, N. J., June 28, 1946; 2nd ed., Sept.
2, 1947 (42 pp). (Reprinted in yon Neumann's
vised by Samuel Lubkin. Its memory con- Collected Works, Vol. 5, A. H. Taub, Ed. (Per-
sisted of 128 long tanks, each containing gamon, London, 1963), pp 34-79.
eight 44-bit words, plus six one-word non- 3. DESMONDE,WILLIAMH., ANDKLAUSJ. BERKo
LING. The Zuse Z-3. Datamation 1~ (Sept.
addressable short tanks, and an auxiliary 1966), 30-31
drum. One of the only things that remained 4. ECKERT, J. PRESPER, JR., AND JOHN W.
unchanged throughout most of its design MAUCHLY. Application of analyzer to a set of
equations for external ballistics. In Proposal
was the basic clock rate of one ~sec per bit; for an electronic difference analyzer (J. G.
the completed machine processed one word Brainerd, Ed ), Moore School of Elec. Eng.,

ComputingSurveys,Vol.2, No. 4, December 1970

260 * D. E. K n u t h

U of Pennsylvania, Philadelphia, Pa., April 10. HARVARDUNIVERSITY, STAFF OF THE COMPU-

1943, App. C (4 pp). (Originally classified TATION [Link] of the Computa-
"Confidential.") tion Laboratory, Vol I, A Manual of Operation
5. ECKERT, J. PRESPER, JR., AND JOHN W for the Automatic Sequence-Controlled Calcu-
MAUCHLY. Automatic high-speed computing- lator (H Alken et al , Eds.), Harvard U. Press,
A progress report on the EDVAC. Moore Cambridge, Mass, 1946
School of Elec Eng., U. of Pennsylvania, 11 KEMPF, KARL. Electronic computers within
Philadelphia, Pa., Sept. 30, 1945 (111 pages) the Ordnance Corps Aberdeen Proving
(Originally classified "Confidential.") Ground, Aberdeen, Md., Nov. 1961 (140 pp.)
6. GOLDSTINE,HERMAN H. Chapter 3 in Com- 12 PANTAGES, ANGELINE Computing's early
puters and Their Role ~n the Physical Sciences years. Datamation 13 (Oct. 1967), 60-65.
(S Fernbach and A. H. Taub, Eds ), Gordon 13 PATTERSON, GEORGE W. (ED). Theory and
and Breach, New York, 1970. Techniques for the Design of Electronic Digital
7. GOLDSTINE, HERMAN H , AND JOHN YON Computers, Vol. ~ Moore School of Elec.
NEUMANN. Planmng and coding of problems Eng., U of Pennsylvania, Philadelphia, Pa.,
for an electronic computing instrument, Vol. 1946 (4 vols.)
1. Inst. for Advanced Study, Princeton, N. J , 14 ROSEN, SAUL. Electronic computers: A his-
Apml 1, 1947 (69 pp.). (Reprinted in von Neu- torical survey Comput Surveys 1, 1 (March
mann's Collected Works, Vol 5, A H Taub, 1969), 7-36
Ed., Pergamon, London, 1963, pp. 80-151.) 15. STIBITZ, GEORGE R., as told to Mrs Evelyn
8 GOLDSTINE,HERMAN H., AND JOHN YON NEU- Loveday The relay computers at Bell Labs.
MANN. Planning and coding of problems for Datamation 13 (April 1967), 35-44; 13 (May
an electromc computing instrument, Vol. 2 1967), 45-49.
Inst. for Advanced Study, Princeton, N. J ,
April 15, 1948 (68 pp.). (Reprinted m yon Neu- 16 TURING, A. M. On computable numbers,
mann's Collected Works, Vol. 5, A. H. Taub, with an application to the Entscheidungs-
Ed., Pergamon, London, 1963, pp 152-214 ) problem. Proc. London Math. Soc. {2} ~i2 (1936),
230-265; {2} 43 (1937), 544-546.
9. GOLDSTINE,HERMAN H., AND JOHN YON NEU-
MANN. Planning and coding of problems for 17. YONNEUMANN,JOHN First draft of a report
an electronic computing instrument, Vol. 3 on the EDVAC. Moore School of Elec E a g ,
Inst. for Advanced Study, Princeton, N J., U. of Pennsylvania, Philadelphia, P a , June 30,
Aug. 16, 1948 (23 pp.). (Reprinted in yon 1945 (101 p p ) . (This draft was written in
Neumann's Collected Works, Vol. 5, A H March-April 1945.)
Taub, Ed., Pergamon, London, 1963, pp 18. VON NEUMANN, JOHN. Letter to Herman H.
215-235 ) Goldstme dated May 8, 1945.

ComputingSurveys,Vol. 2, No. 4, December1970