Fermat’s Library | Von Neumann’s First Laptop Program annotated/defined model.
Von Neumann’s First Laptop Program • 253
location x was to be affected, and the worth
in A was regarded as an integer•
Tentative plans for representing the
directions in reminiscence are mentioned briefly
in [5, pp. 83-86].
THE SORTING PROGRAM
Now we are prepared to focus on von Neumann’s
program• His manuscript, written in ink, is
23 pages lengthy; the first web page nonetheless exhibits
traces of the penciled phrase “TOP
SECRET,” which was subsequently erased•
(In 1945, work on computer systems was categorized,
due to its connections with navy prob-
lems.) A facsimile of web page 5, the first web page of
the program itself, seems as Determine 1.
Von Neumann begins his memo by de-
fining the thought of sorting data into order,
and of merging two strings of data that
have been sorted individually into a single
sorted sequence. Then he states the objective
of the program: “We want to formulate
code directions for sorting and for mesh-
ing [i.e. merging], and to see how a lot
control-capacity they tie up and how a lot
time they require.”
He by no means really will get round to coding
the complete sorting routine in this doc;
solely the merging course of is described. For
the merging downside, we assume that n
data Xo, xx, • • •, x,_x are given, consist-
ing of p phrases every; the first phrase of every
document is known as its “key,” and we have
key(xo) _< key(x1) _< .-. < key(x,_l). An
extra m p-word data y0, yl, “”,
ym-1 are additionally given, with key(y0) _< key(yl) g
• .- < key(y~_l); the downside is to put the
x’s and y’s collectively into the merged se-
quence go, zl, … , z,+,~-i, in such a means
that key(zo) _< key(z1) g ..- < key(z,+~_l).
He formulated the merging technique as
follows (primarily based on a process then used
with the IBM collator): Assume that we
have discovered the first l data Zo, …,
z~_l, the place 0 _< l _< n + m; and assume
additional that these l data consist of Xo,
• • •
, x,,_l and Yo, • • • , y~,,-1 in some order,
where0_< n’ _< n, 0 < m’ < m, andn’-l-
m ~ = l. There are 4 circumstances:
(a) n’ < n, m’ < m. There are two sub-
circumstances:
(al) key(x,,) _< key(y~,). Let zz = xn,,
and substitute (l, n’, m’) by (l + 1, n’ + 1, m’).
(a2) key(x,,) > key(y~,). Let zz = y~,,
and substitute (/, n’, m’) by (l + 1, n’, m’ + 1).
(l~) n’ < n, m’ = m. Identical motion as
(al).
(~) n’ = n, m’ < m. Identical motion as
(a2).
(6) n’ — n, m’ = m. The course of has
been accomplished.
His program is divided up in accordance to
circumstances in this similar means (kind of a “resolution
desk” association). In order to make his
coding fairly simple to observe, it is trans-
literated right here into a symbolic meeting
language such as individuals may use with the
machine if it existed immediately. We use the
pseudo-operation a RST okay (RST means
“reserve quick tank”) to imply that image
is to refer to the first of okay consecutive quick
tank places. The first RST in a program
reserves quick tank quantity 0, and quick
tanks are reserved consecutively thereafter•
The different notations of our meeting lan-
guage are extra acquainted: “EQU” denotes
“equivalence”, “CON” denotes an integer
fixed, an asterisk denotes the present
location, and “**” denotes an handle
which will be crammed in dynamically as the
program runs.
Von Neumann’s first step in coding the
program was to think about the four-way divi-
sion into circumstances; see (A). (Be aware: All numbers
manipulated in the program are handled as
integers.) This code assumes that the quick
tank places have been set up appropri-
ately; in explicit, location SWITCH
incorporates a TRA instruction. The code in (A)
(line 22) units the handle of that TRA to
both ALPHA, BETA, GAMMA, or
DELTA.
Subsequent comes the code for routines (a), (f~),
(~), and (6); see (B). Right here we have a reasonably
awkward piece of coding; von Neumann
thought of a difficult means to scale back circumstances (f~)
and (~,) to case (a) by giving synthetic
values 0 and -1 to key(y~,) – key(x,,).
However he did not notice the far easier strategy
of making (8) and (~) equivalent, respec-
tively, to (al) and (a2). Thus, he may have
Computing
Surveys, Vol. 2, No.
4,
December 1970