Fermat’s Library | Von Neumann’s First Laptop Program annotated/defined model.

2023-01-09 13:19:45

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

See Also

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

Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top