Lehmer sieve

From testwiki
Jump to navigation Jump to search
A Lehmer sieveTemplate:Snd a primitive digital computer once used for finding primes and solving simple Diophantine equations.

Lehmer sieves are mechanical 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]

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 293+1=3×3×529510939×715827883×2903110321 in 3 seconds.[3] The original is lost, but an early-1980s reconstruction is at the Computer History Museum.[4]

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, 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.Template:CN

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]Template:Rp

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]Template:Rp 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]Template:Rp 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]Template:Efn

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]Template:Rp 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]Template:Rp[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.Template:Efn After about two years' work they gave up this effort and instead turned their attention to working with delay line memory.Template:Efn[23]Template:Rp

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]Template:Rp [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 Template:USDCY, including a total of about $150 Template:USDCY 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]Template:Rp[19]Template:Rp or a CDC 6400[29].Template:Efn 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]Template:Efn it is now in the collection of the Computer History Museum.[7]

See also

Notes

Template:Notelist

References

  1. ↑ Template:Cite magazine
  2. ↑ Template:Cite magazine. Untitled, uncredited preamble to the "D.H. Lehmer's Number Sieves" article, on the preceding page
  3. ↑ W. W. Rouse Ball (1960) Lehmer's Machine, in Mathematical Recreations and Essays, Macmillan, New York, pp. 61–62.
  4. ↑ 4.0 4.1 Template:Cite object Note that this is an early-1980s reconstruction by others (mainly Roberto Canepa) of the Lehmer "bicycle chain sieve", by then already lost
  5. ↑ 5.0 5.1 Template:Cite object
  6. ↑ 6.0 6.1 Template:Cite object
  7. ↑ 7.0 7.1 Template:Cite object
  8. ↑ Template:Cite journal
  9. ↑ Template:Cite journal French translation of Template:Cite journal
  10. ↑ 10.0 10.1 10.2 10.3 Template:Cite conference
  11. ↑ A photograph of Pierre Carissan's machine appears at Template:Cite conference
  12. ↑ 12.0 12.1 12.2 Template:Cite journal
  13. ↑ Template:Cite journal
  14. ↑ Template:Cite object
  15. ↑ Template:Cite conference
  16. ↑ Template:Cite journal
  17. ↑ Template:Cite journal
  18. ↑ The photo seems to be the same one reproduced at Template:Cite magazine
  19. ↑ 19.0 19.1 19.2 19.3 Template:Cite thesis (Thesis supervised by Hugh C. Williams.)
  20. ↑ A. Gérardin. Machine à congruences (modèle 1937). In 70e Congrès des Sociétés Savantes de Paris et des Départements, Section des Sciences, pages 14,II, p.37. Gauthier-Villars, Paris, 1937
  21. ↑ Template:Cite web
  22. ↑ Template:Citation. Unpublished manuscript
  23. ↑ Template:Cite book
  24. ↑ Template:Cite journal
  25. ↑ Template:Cite AV media. Video of Template:Cite speech Computer History Museum catalogue no.102651670 (copies in different video formats are listed under different catalogue numbers)
  26. ↑ Template:Cite journal
  27. ↑ Template:Cite magazine
  28. ↑ 28.0 28.1 Template:Cite book
  29. ↑ Template:Cite AV media. Video of Template:Cite speech Computer History Museum catalogue no.102651670 (copies in different video formats are listed under different catalogue numbers)

Further reading

Retrieved from "https://en.wiki.beta.math.wmflabs.org/w/index.php?title=Lehmer_sieve&oldid=21754"