Lehmer sieve
Computing device
From Wikipedia, the free encyclopedia
Lehmer sieves are electromechanical or simple electronic devices that implement sieves in number theory. Lehmer sieves are named for Derrick Norman Lehmer and his son Derrick Henry Lehmer. The father was a professor of mathematics at the University of California, Berkeley at the time, and his son followed in his footsteps as a number theorist and professor at Berkeley.[1]
.jpg)
A sieve in general is intended to find the numbers which are remainders when a set of numbers are divided by a second set. Generally, they are used in finding solutions of Diophantine equations or to factor numbers. A Lehmer sieve will signal that such solutions are found in a variety of ways depending on the particular construction.[2]
Construction
The first Lehmer sieve in 1926 was made using bicycle chains of varying length, with rods at appropriate points in the chains. As the chains turned, the rods would close electrical switches, and when all the switches were closed simultaneously, creating a complete electrical circuit, a solution had been found. Lehmer sieves were very fast, in one particular case factoring in 3 seconds.[3] The original is lost, but an early-1980s reconstruction is at the Computer History Museum in Mountain View, California.[4]
.jpg)
Built in 1932, a device using gears was shown at the Century of Progress exposition in Chicago. These had gears representing numbers, just as the chains had before, with holes. Holes left open were the remainders sought. When the holes lined up, a light at one end of the device shone on a photocell at the other, which could stop the machine. The machine could then be wound backwards to find the point at which the light had shone, allowing the observation of a solution. This incarnation allowed checking of five thousand combinations a second.[5]
In 1936, a version was built using 16 mm film instead of chains, with holes in the film instead of rods. Brushes against the rollers would make electrical contact when the hole reached the top. Again, a full sequence of holes created a complete circuit, indicating a solution.[6]
Several Lehmer sieves[5][6][7] (and the Bicycle Sieve replica[4]) are on display at the Computer History Museum. Since then, the same basic idea has been used to design sieves in integrated circuits or software.[citation needed]
Early work independent of Lehmer
In 1896 F. W. Lawrence published the paper "Factorisation of numbers".[8] In its final section it outlines a design for an automated, electromechanical digital computing device which could apply the sieving method described in the paper. In 1910 a French translation was published by André Gérardin in his journal Sphinx-Oedipe:[9] this sparked a number of efforts to build devices on the lines of Lawrence's description.[10]: 512
In February 1912 Gérardin reported in Sphinx-Oedipe that Maurice Kraitchik had built a mechanical prime sieve. According to Hugh C. Williams and Jeffrey Shallit its design is "rather similar to that of Lawrence" (Kraitchik already knew about Lawrence's paper when his machine was announced, though he did not acknowledge a connection.)[10]: 512 According to Shallit, Williams and François Morain, while Kraitchik's machine "might have worked reasonably well at low speeds, it would very likely have been useless at higher speeds". In March Gérardin also announced the existence of two other machines, one designed by Pierre Carrisan[11] and the other by himself. But according to Shallit, Williams and Morain "[a]ll three of these early attempts to construct a sieve suffered from the same inadequacies: they existed only as roughly constructed prototypes, were rather inefficient, required the human eye to scan for solutions, and produced no significant results—apparently none whatsoever."[12]
However during 1913-14 Eugène-Olivier Carissan, who had previously built the machine of his brother Pierre's design, designed and built a new prototype. Its performance was encouraging and so a precision version was ordered from the Paris horologists Chateau Frères et Cie. World War I delayed production and so the final machine à congruences ("congruence machine") was only completed in 1919. This machine was electro-mechanical but hand-cranked. It was able to prove 1,321,442,641 prime in 15 minutes of operation and prove 18,405,321,661 prime in 1 hour of operation.[13] According to Williams and Shallit "[t]his seems to have been the first automatic sieve mechanism to have ever been successfully constructed."[10]: 512 Shallit, Williams and Morain judged the 1926 Lehmer sieve to be "in many ways much less sophisticated" (though in fact it is somewhat faster). Since 1994 the 1919 Carissan machine has been in the collection of the Musée des Arts et Métiers.[14][12][15][a]
It was displayed at the Société d'encouragement pour l'industrie nationale's large Paris exhibition of calculating machinery in June 1920.[16] Eugène-Olivier had plans for improvements including motor-driven operation, but it seems these were not carried out: both Carissan brothers died by 1925 and the machine fell into obscurity over time.[12] D. H. Lehmer did not hear of the Carissans until 1989. He was aware of Lawrence and Kraitchik by at least 1934, when he described their designs for machines as "impractical ... [though] theoretically interesting"[17] even though, according to Williams and Shallit, Lehmer's 1932 gears sieve "represents in many ways the fruition of their ideas".[10]: 513 Similarly Gérardin was, according to Richard F. Lukes, "apparently totally unaware of Lehmer's previous work" when he constructed a new number sieve in 1937. This was reported to be an electrically-powered, automatic device incorporating a printer. Based on a photograph[18] Lukes speculated that it was based on an adding machine.[19][20]
Electronic sieves
In 1945 and 1946 D. H. and Emma Lehmer gained early experience with the vacuum-tube digital computer ENIAC at the University of Pennsylvania.[21] In the next two decades D. H. Lehmer and others would devote significant attention to writing software sieves for general-purpose computers. However, on his return home to Berkeley Lehmer also decided to seek to build a fast special-purpose hardware sieve using vacuum tube logic. In an unpublished 1946 document he proposed a design for such a sieve, naming it the "Electronic Sieve": it would have been able to be reconfigured by plugging and unplugging logic modules. The proposal also lays out his idea for an "Acoustic Sieve" in which, in Lukes' words, "the periodic element would be a tube of ethylene glycol with a piezo-electric crystal at each end".[19]: 16–7 [22] Lehmer and Berkeley engineering professor Paul Morton did, at some point between 1946 and 1964, design and build all or part of a sieve using counters.[b] After about two years' work they gave up this effort and instead turned their attention to working with delay line memory.[c][23]: 451
In 1962 D. G. Cantor, G. Estrin, A. S. Fraenkel and R. Turn proposed another electronic sieve: this one would have used shift registers and been capable of being connected to a general-purpose computer, but was never built.[19]: 18–9 [24]
The Delay Line Sieve
Lehmer and Morton's DLS-127, the initial form of the Delay Line Sieve, began operations in 1965[25] or 1966.[26] The DLS-127 was built as an unsponsored educational project of Berkeley's Departments of Mathematics and Electrical Engineering at a cost of about US$2000 ($20,433 in 2025), including a total of about $150 ($1,532 in 2025) for its navy-surplus wire delay lines. The machine used the innate delay of delay-line memory to advantage, running a number of delay lines of different lengths in parallel and noting a solution when they all returned input data simultaneously. It also had vacuum-tube components.[27] Input was by means of a paper tape which was prepared by software on an IBM 7094}[28]: 53 [19]: 17 or a CDC 6400.[29][d] In the early 1970s the machine was upgraded with an additional six moduli and renamed the DLS-157: these new delays were implemented using shift registers rather than delay lines. The Delay Line Sieve ceased operations in 1975;[28][e] it is now in the collection of the Computer History Museum.[7]
See also
Notes
- Lehmer's 1976 account seems to suggest that shortly after he returned to Berkeley (which would have been in 1946) he began work with Morton on a single effort to build a valve-based sieve; that this resulted in a valve-based sieve built around two short counters; and that they abandoned this then immediately began a single effort to work with delay lines which produced the DLS-127 (apparently working by 1965, at the earliest). But the timing seems to make this unlikely, especially if Stephens and Williams are correct that the work on the counter sieve was "two years of effort". Relatedly, it's not clear (at least without seeing the document) if the "Electronic Sieve" concept in the 1946 proposal document had input from Morton or had much connection to the counter sieve which Lehmer ended up working on with Morton.
- According to the paper of Lehmer's 1976 presentation to the International Research Conference on the History of Computing, he and Morton gave up on the counter-based sieve because "[t]he whole thing was a little too short on reliability" while in his in-person presentation he said that "we could get reliable results, fairly reliable, but the whole thing turned out to be a little bit too expensive to set up".
- Lukes and Stephens and Williams both say that an IBM 7094 was used to prepare the paper tapes, but in his 1982 Computer Museum talk Lehmer instead says that a CDC 6400 was used.
- However Lehmer does not clearly confirm this in his 1976 talk.