Reference / Paper · 2010
The complete reconstruction of D. H. Lehmer's 1946 ENIAC set-up for computing the exponent of 2 modulo primes — the longer companion to "A Week-End Off".
Setting-up early computer programs: D. H. Lehmer’s ENIAC computation Maarten Bullynck, Liesbeth de Mol To cite this version: Maarten Bullynck, Liesbeth de Mol. Setting-up early computer programs: D. H. Lehmer’s ENIAC computation. Archive for Mathematical Logic, 2010, 49, pp.123-146. ⟨hal-01396497⟩ HAL Id: hal-01396497 https://lilloa.hal.science/hal-01396497v1 Submitted on 14 Nov 2016 HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. HAL Authorization Setting-up early computer programs. D.H. Lehmer’s ENIAC computation.∗ Maarten Bullynck† Liesbeth De Mol‡ April 21, 2010 Abstract A complete reconstruction of D.H. Lehmer’s ENIAC set-up for computing the exponents of p modulo 2 is given. This program served as an early test program for the ENIAC (1946). The reconstruction illustrates the difficulties of early programmers to find a way between a man operated and a machine operated computation. These difficulties concern both the content level (the algorithm) and the formal level (the logic of sequencing operations). Keywords:ENIAC History of Computer Programs Number Theory Derrick H. Lehmer MSC(2000):11-04 11N36 11A07 01A60 11Y16 1 Introduction In 1943 the Army’s Ordnance Proving Ground at Aberdeen Maryland contracted John W. Mauchly and Prespert J. Eckert to build the ENIAC, the first U.S. electronic digital and (basically) general-purpose computer. Its original purpose was the computation of ballistic trajectories. However, due to its architecture, it could be used to solve many more problems. Already in 1945 the Ordnance also assembled a “Computations Committee” that had to prepare for utilizing the machine after its completion. The Committee consisted of the number theorist D.H. Lehmer, the logician H.B. Curry, the astronomer L.B. Cunningham and the statistician F.L. Alt [1]. Each developed their own test program to be run on the ENIAC after it was first presented to the public at Penn University February 15, 1946. Soon afterwards, through John von Neumann, the Atomic Energy Commission got interested in using the ENIAC for computations connected to the development of the H-bomb. ∗ This research was supported by the Flemish Fund for Scientific Research (FWO- Flan- ders) and the Humboldt Foundation. A version of this paper has been published in Archive for Mathematical Logic, vol. 49, nr. 2, 123-146. The original publication is available at www.springerlink.com † [email protected], Université Paris 8, Vincennes à Saint-Denis, France ‡ [email protected], CLPS, Universiteit Gent, Blandijnberg 2, 9000 Gent, Belgium 1 These test programs, the ballistic trajectory computations and especially the problems that the Atomic Energy Commission wanted to put on ENIAC soon made clear the difficulties and limitations of “programming” the ENIAC in its original hardware configuration [2, 3]. For each new problem, the ENIAC had to be programmed directly and locally, setting the switches on each individual unit, laying the cables to interconnect these units and control the timing and sequencing of the units’ operations. The units, 30 in number, operated in parallel, which made the timing and sequencing a tricky job. Moreover, the amount of dynamic (“RAM”) and static (“ROM”) memory was limited. The memory problem could, however, be circumvented by using punch cards to store (intermediate) results and inputting them into the computation at a given point. Again, the synchronization of this was a difficult task. Programming the ENIAC in its original configuration thus came down to “the design and development of a special-purpose computer out of ENIAC component parts” [2, p. 32]. Or as Jean Bartik, one of the ENIAC’s female programmers, put it, the ENIAC “was a son-of-a-bitch to program” [4, p. 94]. As a consequence, ways of simplifying the ENIAC’s set-up were contemplated. Initially, often recurring instructions were codified as two-digit numbers that could be looked up in the function table unit that in its turn triggered the right program pulses [5, sec. 7.4]. A logical coding system consisting of a 60word vocabulary of orders was put on the ENIAC in the latter half of 1947. Mid 1948 a 100-word converter code was developed and installed on the ENIAC (i.e., the ENIAC was rewired, switches set semi-permanently) [6, 7]. This code was often expanded and revised during the following years and turned the ENIAC into a “more effective serial stored-program computer” [2, p. 32–33].1 The setup of a new problem on ENIAC was thus considerably simplified, though at a cost. The running time increased with a factor of six on the average. The early (declassified) test programs are unique instances of “programming” a machine that had not the kind of logical design we know nowadays as the von Neumann architecture. Furthermore any kind of programming language was totally absent. These programs demonstrate the difficulties of adapting computations made to human measure to a machine. Also various solutions towards logically organizing the processes within that computation had to be invented. The current reconstruction of D.H. Lehmer’s ENIAC program extends and completes the partial reconstruction presented in [9] and discusses in detail Lehmer’s early attempt at “programming”. Furthermore, the reconstruction of the sieve is now improved by removing certain redundancies. 1 There is much controversy regarding the invention of the stored-program computer. We will not enter into this discussion but refer to the lucid discussion in [8]. 2 2 ENIAC: Architecture and Program Planning 2.1 Overview of ENIAC The Electrical Numerical Integrator And Computer (ENIAC) was first described in a proposal John Mauchly submitted to Penn University, and was ultimately built with U.S. Army money by a team of engineers under the direction of Presper Eckert Jr. It used about 18,000 vacuum tubes and 1,500 relays. From 1945 to 1947 this was a highly parallel computer, though its parallelism was hardly ever used [10, p. 376]. Lehmer’s program was one of the notable exceptions. The ENIAC had a modular architecture. It comprised 20 accumulators, a multiplier, a divider and square rooter, a constant transmitter, 3 function tables, a master programmer, a cycling unit, an initiating unit and also a card reader and a printer. The constant transmitter and the function tables were the ENIAC’s main (static) memory storage units (“ROM”). The accumulators were the main (dynamic) memory storage units that could be changed during a computation (“RAM”), each storing a signed 10-digit number. However, each accumulator had 12 program controls which “gives us 240 components we can use in the computational dataflow.” [11, p. 20]. Furthermore each accumulator could be used to store more than one number. E.g. it could be used to process two 5-digit numbers with the same sign. These could be processed separately by using special shifter and deleter adaptors (See Sec. 3.3.4).2 Another way to extend the ENIAC’s small amount of both memory types is the following. The constant transmitter (CT) consisted of two panels: (CT2) where numbers could be stored by manually setting the switches before computation, and (CT1) where the counters were set automatically according to the input that was read on a punched card fed into the card reader. This could be done during a computation, though that required some ingenuity to synchronize the (slow) reading of the punched card with the steps in the computation. Therefore, the designers of the ENIAC added an interlock to this unit, to simplify exactly this kind of synchronization [5, sec. 8.2.4].3 With the card reader and the (CT1) unit new numbers could be brought into the computation during runtime. Of crucial importance in the ENIAC was the central programming pulse (CPP), emitted by the cycling unit once every 1/5000th of a second, marking the beginning and end of a computation cycle. These pulses synchronized the operations of the units. When a unit completed an operation it emitted one of these as a program output pulse, stimulating the next operation. All the units required an integral number of cycles. E.g. an accumulator required 1/5000th of a second for an addition, therefore we speak also of an addition time instead of a cycle. The ENIAC had two kinds of electronic circuits: the numerical circuits for storing and processing electric signals representing numbers and programming 2 The possibility of splitting one number into two smaller numbers is also possible in the function tables and the constant transmitter. 3 For similar reasons, also the printer unit and the division units had such an interlock. 3 circuits for controlling the communication between the different parts of the machine. Most of the units had both kind of circuits, except for the master programmer and the initiating unit which consisted only of programming circuits. Numerical pulses have a range of 0P to 9P (a 10P also exists) with 1P being the unit voltage. Program pulses always have a voltage of one CPP (=1’P). Numerical and programming pulses are strictly separated. There was however a technique to convert a digit pulse into a program pulse through the use of a special digit-to-program pulse adaptor and one or two dummy programs (See Sec. 2.4.1, 2.4.2). Our further discussion of the ENIAC will focus on the salient “programming” facilities, that is, mainly the accumulator and the master programmer. In this discussion we have made use of various references. The most detailed technical description of the ENIAC is [5], less detailed but instructive and rather readable accounts are [10, 12, 13]. We would also like to refer to recent research on the ENIAC: [14] analyzed the ENIAC’s architecture and used VLSI to put ENIAC on a chip; [15, 11] present (incomplete) Java simulations of ENIAC.4 2.2 Accumulators The accumulators were the main arithmetic units of the ENIAC and could be used to add or subtract a number. Fig. 1 gives a graphical representation of an accumulator. Each accumulator held a 10 place decimal number and a sign (P for plus and M for minus), stored in ten decade ring counters and a PM counter. It had 5 input channels (α to ǫ) to receive a number. It had two output channels (A and S) to transmit a number n (through A) or its complement 1010 − n (through S). In one addition time, the accumulator could either receive a number n, adding (if n ≥ 0) or subtracting (if n < 0) it to/from its content, or transmit the number it stored through one or both of its output channels. The program part of the accumulator consisted of 12 program controls: 4 receivers and 8 transceivers. A transceiver had a program pulse input and output terminal, a clear-correct switch (to clear or not clear its content after a cycle; it could also be used to round off numerical results), an operation switch (to be set to α-ǫ, A, S, AS or 0, determining whether the accumulator should receive or transmit a number, or do nothing) a repeat switch (with which it could either receive or transmit up to 9 times). When a transceiver received a program pulse through a program cable at addition time r, the operations set on the program switch associated with that transceiver were executed. When these had been finished after n (1 ≤ n ≤ 9) addition times, a program pulse was transmitted through the output of the transceiver at addition time r + n. A receiver differs from a transceiver in that it has no output terminal and no repeater switch. An accumulator furthermore contains a significant figures switch. This is used to round off numerical results. If the significant figures switch is set to a number 4 More particularly, the master programmer, the function tables, the card reader, the printer and the special multiplication and division combinations of accumulators are missing in the Java simulations. The source code of Hansen’s Java simulation can be found at: http://home.arcor.de/-ph/eniac/download.html. 4 s, then, when clearing takes place using the clear-correct switch, decade 10 − s clears to 5 and all other decades to 0. α β γ ǫ δ A Input Channels S Output Channels Receivers o/c o/c o/c o/c In In In In SF Transceivers Transceivers o/c o/c o/c o/c o/c o/c o/c o/c In Out In Out In Out In Out In Out In Out In Out In Out r r r r r r r r Figure 1: A Schematic Representation of an Accumulator. Here, “SF” is the significant figures switch, “In” rsp. “In/Out” the operation switches of the 4 receivers rsp. the 8 transceivers, “r” the repeater switch and “o/c” the clearcorrect switch for the 12 program controls. On the bottom, an incoming arrow indicates that a program pulse can be received, an outgoing arrow that a program pulse can be sent. At the top, α to ǫ are the 5 input terminals and A and S the two output terminals. 2.3 Master Programmer: Loops and Sequencing The master programmer provided a certain amount of centralized programming memory. It consisted of 10 independently functioning units, each having a 6stage counter (called the stepper, see Fig. 2), 3 input terminals (the stepper input, direct input and clear input), and 6 output terminals for each stage of the stepper. Each such stage s was associated with a fixed number ds by 5 manually setting decade switches, and with 1 to 5 decade counters. If a pulse arrived at the stepper input (SI) of a stepper, one was added to the counter of stage s. If this number equaled the preset number ds ,it cleared the counter of stage s and cycled to the next stage s + 1. In both cases, a program pulse was emitted through the output terminal of stage s. A pulse at the direct input (DI) immediately cycles the stepper to the next stage and a pulse at the clear input (CI) resets the stepper to its initial configuration. In neither case a program pulse was emitted. In this way the master programmer could be used, among other things, to sequence operations and to iterate a given subroutine. S6 S5 S4 S3 S2 S1 DISICI Figure 2: A Schematic (Reduced) Representation of a stepper counter of the Master Programmer. S1 to S6 represent the 6 stages of the stepper, DI is the direct input, SI the stepper input and CI the clear input. Note that there are 3 input terminals for CI and DI and only 2 for SI. 2.4 Conditional Branching The ENIAC was capable of discriminating between program sequences by examining the magnitude of some numerical result. This was done by using the technique of converting digit pulses into program pulses, through special adaptors and dummy controls. “Magnitude discrimination” or “branching” could be done by exploiting the fact that 9 digit pulses were transmitted for sign indication M and none for sign indication P . The fact that digit pulses were 6 transmitted for every digit except for 0 could be exploited in a similar manner. The digit pulse corresponding to the sign (or a digit) was converted into a program pulse by connecting the P M lead (or another digit lead) of the A and/or S output terminal of an accumulator to a program cable. A special adaptor which was placed on this lead took care of the conversion. The program cable was then connected with the program pulse input terminal of (an) otherwise unused “dummy (program) control(s)” (d.p.c.) [5, Sec. 4.5].5 There were two main branching methods: the first is explained in detail by Adèle Goldstine [5], the second one is only referred to without further explanation. In what follows we will reconstruct both methods. 2.4.1 First Branching Method A S (i) (ii)(iii) o AS 1 o o 0 0 1 1 P0 P1 P2 P3 P4 s. a. s. a. a b Figure 3: First Mode of Branching on the ENIAC Fig. 3 illustrates the wiring of a branching method that uses both output terminals. Assume that the discrimination is of the following nature: if a given number n becomes smaller than some other number m, then program a should be executed, else program b should be executed. If the accumulator is activated to execute this kind of “magnitude discrimination” at time r, it should store n − m (or m − n) at time r. For this method a first transceiver (i) should be set such that the accumulator will send its content once through both its A and S output channels, when (i) is stimulated by a program pulse. Now, in Fig. 3, when the discrimination program is activated at time r through program cable P0, n − m is sent through the A and S output channels. If n < m, a negative number is transmitted, nine pulses are transmitted through the PM lead of the A output terminal and no pulse is transmitted at the PM lead of 5 A dummy control had the following main functions [5, Sec. 4.5]: “The dummy program has at least 3 important functions: (1) conversion of digit pulses into program pulses, (2) delay of a program pulse, and (3) isolation of programs from one another.” 7 the S output terminal. The nine pulses transmitted through the PM lead of the A output terminal are converted into a program pulse using a special adaptor (indicated as “s.a.” in Fig. 3), thus stimulating program cable P1 which in its turn activates the first dummy control (transceiver (ii)) at time r + 1. At time r + 2 a program pulse is transmitted from (ii) leading to the execution of some program a. Similarly, program b will be activated when n ≥ m.6 2.4.2 Second Branching Method Fig. 4 shows a branching method that uses only one output terminal, together with the master programmer. This method is preferred if one needs to be economical with the accumulators, avoiding to use a complete accumulator only for the execution of branching. One stepper si of the master programmer is used: both the first and second stage of this stepper should be set to cycle to the next stage when they reach some value v.7 As is the case for the first method, if one wants to discriminate between two programs depending on whether a number n becomes smaller than a certain value m, the accumulator doing the discrimination should store n − m at the time of the discrimination. Assume that the discrimination program is activated at time r through program cable P0 in Fig. 4. This activates the transmission of n − m through the A output terminal. Now let n ≥ m. Then, at time r + 1 the dummy control (transceiver (ii)) will not be activated and transceiver (i) will send a program pulse to cable P 1 activating another transceiver (iii) of the accumulator. This transceiver is set to do nothing except for sending a program pulse when it is “done” at time r + 2 to cable P4. This cable is connected to the stepper input of stepper si of the master programmer. The program pulse arriving at the stepper input will lead to the addition of 1 to the counter of stage 1. At time r + 3 a program pulse is then sent from stage 1 of stepper si to program cable P5, activating program a and also resetting the stepper. If, on the other hand, n < m, then, at time r+1 a dummy control (transceiver (ii)) and transceiver (iii) are activated, both set-up to do nothing except transmitting a program pulse at time r + 2 to program cable P3 rsp. P4. P3 is connected to the direct input of stepper si , P4, as we already know, to the stepper input of stepper si . This means that both the direct input as well as the stepper input are stimulated simultaneously. This is unproblematic because the result of a program pulse at the direct input is that the stepper immediately cycles to the next stage of the stepper [5, Sec. 10.5]. The program pulse at the stepper input then results in the addition of 1 to the counter of stage 2. At time r + 3 a program pulse is sent from stage 2 of stepper si to program cable P6, resulting in the activation of program b as well as the resetting of stepper si . It should be pointed out that in the reconstruction of Sec. 3.3 we will only use the second branching method. There we will use the simplified and reduced 6 Note that the case n = m is processed in the same way as n > m. 7 If the stages of stepper s are used only for branching, the value of v is irrelevant so v may i be set to 1. However, it may be useful to re-use these stages of the stepper at some earlier or later stage of a given program in which specific values v need to be set. 8 PM A S s. a. (i) (ii) (iii) o A 1 o o 0 0 1 1 v v P0 P1 P2 P3 P4 P5 P6 a b Figure 4: Second Mode of Branching on the ENIAC PM scheme of Fig. 5 to keep the structure of the wiring schemes transparent. A S s. a. (i) (ii)(iii) o A 1 o o 0 0 1 1 P0 P1 P2 P3 a b Figure 5: Simplified Representation of the Second Mode of Branching on the ENIAC 2.5 Programming ‘primitives’ As has been acknowledged by Prespert J. Eckert, the head engineer of the ENIAC, the main inspiration for the ENIAC was the idea of “linked adding machines” [16, p. 22]. This origin is still visible in the architecture of the ENIAC, especially in the crucial role of the accumulators. However, the designers added a powerful set of “programming” machinery, like conditional branching and the master programmer. Patching together a sequence of different processes into 9 one program that could be run without interruption was thus possible (within the limits of the hardware), though all but a straightforward task. As a consequence, it need not wonder that among the first users of the ENIAC, many conceived aids and simplifications to program the machine. Since looping and sequencing could be controlled by the master programmer, a scheme of the wiring on the master programmer was used to represent the sequencing of and interconnections between the main steps of the computation. This kind of “reduced” wiring scheme was used by D.R. Hartree in an article that described his ENIAC computation [17].8 H.H. Goldstine and J. von Neumann developed a further abstraction from such a scheme and from the actual hardware in the context of the EDVAC project [18]. Their flow diagrams were used “to plan first the course of the process and the relationship of its successive stages to their changing codes, and to extract from this the original coded sequence as a secondary operation.” [18, p. 4]. Flow diagrams are flexible tools that have remained in use until today. Finally, the logician H.B. Curry developed an abstract calculus of program composition using his theory of combinators in the process of studying how to put an inverse interpolation problem on the ENIAC [19]. Curry’s work will, however, be the topic of another paper, in the meantime we refer to Knuth and Pardo’s lapidary discussion [20, pp. 434–435]. The most difficult kind of program on the ENIAC, even with the tools Goldstine, von Neumann and Curry had devised, remained the programming of a complex parallel computation. In 1996, the historians Marcus and Akera proposed a modus procedendi for synchronizing such a parallel computation. For the synchronization of two branches, they proposed to program the master programmer as follows [16, p. 23]: 1) Set the first stage of a stepper on 11. 2) Route a program pulse into the stepper, and let the stage of the stepper provide a program pulse each addition time. 3) Route the program output pulse of the first branch into the direct input of the 1st decade of the first stage, so that the counter goes from 0 to 1 or from 10 to 11. Route the program output pulse of the second branch into the direct input of the 2nd decade so that the counter goes from 0 to 10 or from 10 to 11. 4) Connect the output of the second stage to whatever happens after both parallel paths have terminated. Since a stepper stage can be associated with maximally 5 decades, this procedure would allow for a maximum of 5 parallel branches to be synchronized, i.e., each branch contributing a “1” to a decade and the next step in the program only beginning when the stage content has reached “11111”. According to Marcus and Akera, this set-up was never used. 8 We will make use of this representation for Lehmer’s program below (See Fig. 7). Incidentally, Hartree thanks K. McNulty (one of the all-female team of ENIAC programmers) and D.H. Lehmer for helping him set up and program the ENIAC. 10 There are, however, other ways of synchronizing parallel branches that have been wired on the ENIAC. The second branching method (2.4.2) is actually an example of synchronizing two branches. Moreover, Mauchly and Lehmer synchronized a 14-branch parallel computation within Lehmer’s calculation of exponents of 2 modulo p (the sieve). 3 Lehmer’s Program In 1946 the number-theorist Derrick H. Lehmer and his wife Emma spent a Fourth-of-July weekend testing the ENIAC. The Lehmer family – Derrick, his wife Emma and two teenage kids – arrived at the Moore school on Friday 5 p.m. where they met John Mauchly. Mauchly helped them set up the ENIAC for the implementation of Lehmer’s program and stayed on as an operator through the week-end [21, p. 451]. According to Akera [22, p. 40] [Lehmer’s program] was a difficult enough problem that it attracted the attention of some mathematicians who could say, yes, an electronic computer could actually do an interesting problem in number theory – something as sophisticated in number theory – and produce useful results. There were many people who speculated about this – von Neumann among them – but to actually do it, to demonstrate it, was, I think, important to the post-war reputation of electronic computers among mathematicians. The objective of Lehmer’s program was to compute a list of exponents e of 2 mod p, p prime.9 3.1 Description of the Problem It was first noted by J.H. Lambert in 1770 that Fermat’s little theorem (ap−1 ≡ 1 mod p) could be used as a primality test. If for a given number b, 2b ≡ 2 mod b than b is with high probability a prime number. Unfortunately, an infinite set of exceptions to this primality test exists. Early on in his career, D.H. Lehmer had written on the converse of Fermat’s theorem [23], and often returned to the topic. In 1936 Lehmer established the general form of exceptions to the converse [24]. He proved that if for a composite number n = pq (p and q prime), 2pq − 2 is divisible by pq, this can only occur if and only if p − 1 is divisible by the exponent of 2 modulo q and q − 1 is divisible by the exponent of 2 modulo p [24, p. 353]. Similar theorems can be proven for composites b of the forms pqr, pqrs etc. that satisfy 2b ≡ 2 mod b. It is thus clear that a list of exponents of 2 mod p (p prime) is useful for the construction of prime tables. Lehmer had been using Kraı̂tchik’s tables for finding exponents of 2. These tables, however, only extended to 300 000, and contained rather a lot of errors. 9 The exponent e of 2 modulo a prime p is defined as follows: the smallest number e such that 2e ≡ 1 mod p. 11 As a result of his ENIAC computation Lehmer published a list of errors to Kraı̂tchik’s tables [25] and a list of factors of 2n ± 1 [26], both in 1947. More details on his actual computation were only published two years later in [27] due to the “classified” label attached to many things involving the ENIAC. In the following two sections, we will provide the details of the set-up of Lehmer’s program on the ENIAC. The flow diagram and the algorithms as presented in Sec. 3.2 follow the discussion by Lehmer himself [27]. The actual reconstruction of Sec. 3.3 of the set-up is ours. 3.2 The Problem from the Machine’s Eye View Translating a problem from man’s view to a machine was not obvious when the first electronic computers emerged. Originally, this translation involved two main steps: programming and coding. According to Hartree [28, pp. 111–112]: “Programming” is the process of drawing up the schedule of the sequence of individual operations required to carry out the calculation, and “coding” is the process of translating these operations into instructions in the particular form in which they are read by the machine. Coding was clearly the more difficult part, especially for a machine such as the original ENIAC where coding equalled wiring the machine. This was exactly the reason for rewiring the ENIAC (Sec. 1, p. 2) and developing so-called “storedprogram logical machines”, i.e., the von Neumann architecture. The difficulties of coding as well as the immense speed-up of electronic computing had an impact on the more ‘high-level’ programming part. The approaches and algorithms that had been in use for human computors and for desk calculators had to be rethought in function of the restrictions that coding the machine imposed and of the exponential speed-up of the ENIAC.10 In [27] Lehmer explicitly addressed this translation problem in the discussion that accompanied the flow chart for the ENIAC’s computation of the exponents e of 2 modulo p (See Fig. 6). A human computer would calculate the exponents e more or less in the following way. First, he would take a list of primes and select the next p. Then he would, using the many abbreviations possible in modular arithmetic, calculate powers of 2 and reduce them modulo p, though not all powers, but only those that are divisors of p − 1. This is because a number-theorist knows that if there is an exponent e (< p − 1) of 2 so that 2e ≡ 1 mod p (p prime), than e is either a divisor of or equal to p − 1. He might also make use of already existing tables of exponents. As Lehmer later described it, “[i]n contrast, the ENIAC was instructed to take an “idiot” approach” [30, p. 4]. A first problem is to let the machine recognize the “next prime”: 10 In a test computation [29] the ENIAC computed a trajectory in 15 minutes, the second best machine, Bell’s relay calculators, needed 70 hours! 12 The “next value of p” [i.e. the next prime] presents an interesting problem to the ENIAC. [Circumstances] prevented the introduction [of] punched cards. [...] This means that the ENIAC should somehow compute its own values of p. To this effect a “sieve” was set up which screened out all numbers having a prime factor ≤ 47. [27, p. 302] A more sophisticated method would have required “much outside information [introduced] via punched cards [...] to be prepared by hand in advance” [27, p. 302]. Not only would this have taken quite some time, but it would have been mandatory to synchronize the card reader with the rest of the computation using the interlock, making the set-up considerably more difficult. Therefore, Lehmer entered a sieve into the program to select the next p (box (III) in the flow chart, Fig. 6). This sieve is a rather straightforward implementation of Eratosthenes’s sieve, where multiples of already known primes p1 , p2 , ..., pn are calculated and then rejected, leaving only those integers relatively prime to p1 , p2 , ..., pn . In the ENIAC computation, only odd numbers were tested so 2 had not to be included as a test prime in the sieve. The ENIAC checked in parallel whether a next number p (in a progression of numbers to be checked p = 2i + 1) is a multiple of one or more of the first 14 odd prime numbers (3 to 47) or not. About 86 % of the composite integers were thus eliminated. To reduce the number of “fake” primes remaining, Lehmer added an extra test later on in the program (box (V) in the flow chart, Fig. 6). Next, the powers of 2 were calculated and reduced modulo p (p being a sieved number) to compute the exponents e in the following way [30, pp. 4–5] (box (IV) in the flow chart, Fig. 6): In contrast, the ENIAC was instructed to take an “idiot” approach, based directly on the definition of e, namely, to compute 2n ≡ Γn (modp), n = 1, 2, .... until the value 1 appears or until n = 2001, whichever happens first. Of course, the procedure was done recursively by the algorithm: Γn + Γn if Γn + Γn < p Γ1 = 2, Γn+1 = Γn + Γn − p otherwise Only in the second case can Γn+1 be equal to 1. Hence this delicate exponential question in finding e(p) can be handled with only one addition, subtraction, and discrimination at a time cost, practically independent of p, of about 2 seconds per prime. This is less time than it takes to copy down the value of p and in those days this was sensational. The limit value for e was changed two times during Lehmer’s three-day computation. For the first 300.000 integers e was ≤ 2000, for 300000 < p < 1000000 this limit was reduced to 1000 and for 106 < p < 4.5 · 106 it was set at 300 [27, p. 302]. 13 I. Initiation and Preliminary setup II. Increase p by 2 III. Sieve Is p divisible by a prime ≤ 47? Yes No IV. Exponent Routine Is e > 2000 ? Yes No V. Does e divide p-1 ? No VI. Erase exponent Calculation Yes VII. PRINT p, e and f Figure 6: Lehmer’s flow chart for the ENIAC computation 14 Finally, having obtained the exponent e of 2 modulo p, an extra primality test on p was introduced (box (V) in the flow chart, Fig. 6). As known, p−1 must be divisible by e if p is prime. A division by repeated subtraction checked whether p − 1 was divisible by e, if so, the quotient f was stored (and later punched), if not, the value p was rejected. After this final elimination of composite p’s, only 25 composite numbers remained in the range 1000000 < p < 3000000. Emma Lehmer finally eliminated these few remaining composites manually “by comparison with [a] list of primes” [27, p. 302]. 3.3 Reconstruction of the Program In Fig. 7 Lehmer’s flow diagram is translated in a wiring scheme of the master programmer, following Hartree’s representation of ENIAC programs (See Sec. 2.5). In what follows we will first give a brief informal account of the three main steps of the program and then provide the details of the reconstruction. The following conventions will be used in the reconstruction. First, it is assumed that for every accumulator the transceivers are numbered as t1 , t2 , ..., t8 from left to right. Secondly, even though we will make frequent use of the constant transmitter, it will not be included in the schemes because it would take up too much space and is the less important part of the wirings. Instead, we will indicate the number transmitted by the constant transmitter directly on the relevant numerical cable. Furthermore, if the operation switch, the repeater switch and the clear-correct switch of a given transceiver of an accumulator are marked with “X”, this means that the transceiver has already been used in some other part of the program. 3.3.1 Informal account of the three main steps The three most important and interesting steps of the computation are the sieve (III), the exponent routine (IV) and the division routine (IV). The sieve is used to determine whether or not a given number p = 2i + 1 is prime relative to the first 14 odd prime numbers. Lehmer used a sieve instead of a look-up table because this was the more efficient method (see Sec. 3.2, p. 12). Now, the sieve uses hardware parallelism: in our reconstruction, 14 out of the 20 accumulators (Ap1 , ..., Ap14 ) are used to check in parallel whether or not the number p being processed is divisible by one of the 14 prime numbers. The main idea behind the sieve reconstruction can best be explained as follows. Remember that the sieve method is used here to search for numbers that are not divisible by a given set of prime numbers pi , in this case, the first 14 odd primes. The sieve can be represented by a matrix of k rows and infinitely many columns. The infinite rows are periodic, the i-th row having a period of pi . The value in the r-th column and the i-th row equals r modulo pi . The problem is then to find those columns that contain no 0s. For instance, suppose we have a sieve which selects numbers that are not divisible by 2, 3 and 5. Then we would get the following sieve matrix: 15 n= 105 − 1 (II) n= 1 (VI) n= 2000 (IV) (V) (VII) Init (III) Figure 7: The set-up of the Master Programmer for Lehmer’s ENIAC computation 16 1 0 1 2 1 2 1 0 0 1 3 4 1 0 2 0 0 1 1 1 2 0 1 2 0 3 4 0 1 1 2 0 1 0 1 0 1 2 3 ... ... ... In this example, the first number (except for 1) not divisible by 2, 3 and 5 is 7, since the 7th column is the first one that contains no 0s. Basically, what is done in the ENIAC sieve is that each of the 14 Apj corresponds to a row j of the sieve. At the start-up each accumulator stores the complement of pj − 1.11 Now, since only odd numbers p are sieved, with every loop of the sieve program each of the accumulators Apj is increased with 2 in parallel. Thus, the first number p being checked is 3. Clearly, if any of the numbers stored in one of the accumulators becomes 0 and thus positive, a divisor is detected (there is at least one 0 in the p-th column), if not, p is a prime relative to each of the 14 primes. Dummy controls assure that, whatever the case, the correct subroutine is followed. Of course, if an accumulator becomes 0, its content should be reset. I.e., the complement of 2pj should be loaded into that accumulator. This is done by making use of the function tables and special adaptors. Note that the mathematics of the sieve (addition and detection happen independently in each of the accumulators) guarantees that the 14 branches are synchronous. The program for the exponent routine was already described in detail in Sec. 3.2. It produces powers of 2 modulo the p found by the sieve. Besides the fact that Lehmer chose for the “idiot” approach, he also had to economize on the number of accumulators. For example, the doubling procedure uses only two accumulators instead of the multiplier unit (that takes up four accumulators). Also for the division routine, economization on ENIAC’s accumulators was necessary. Thus, Lehmer did not use the divider unit but wired his own division procedure, basically an implementation of Euclid’s algorithm for integers. It uses only 3 accumulators, of which two are also used in other subroutines. The exponent e found is successively subtracted from the prime number p − 1 until either p = 0 or p < 0. Note that in this reconstruction full use is made of nearly all of ENIAC’s different components and salient features, including some of its special adaptors and all of the accumulators. In this sense, the reconstructions highlight some of ENIAC’s typical properties, possibilities and problems. 3.3.2 I. Initiation and preliminary set-up. As will become clear throughout the remainder of this reconstruction, certain components have to be set in advance. The 0th value (f (0)) of each of the function tables has to be set to a specific value. Also each of the 14 accumulators Apj used in the sieve need to be set to the complement of pj −1 (See Sec. 3.3.4). The numbers + 2, -2 and -1 are set manually on the constant transmitter (CT). An accumulator AP used to store the number P = 2r + 1 being processed, should be set to store the number 1. The computation is started by an initiating pulse 11 The reason for this is that the first p checked is equal to 3. 17 sent to the 14 accumulators and the CT. 3.3.3 II. Increase p by 2 In this subroutine the 14 Apj ’s (See Sec. 3.3.4), AP (storing the prime number p being processed), as well as a transceiver Ae1 used in subroutine IV should be set to receive once through one of their input channels. The constant transmitter is set to send the value + 2 once. This leads to the desired increase of 2 in the several components affected by this increase. Note that after the first execution of II (the addition of 2), P = 3. 3.3.4 III Sieve In our reconstruction of the prime sieve, we have used 14 accumulators Apj for each prime pj ≤ 47, (1 ≤ j ≤ 14 ) except for 2.12 Upon initializa