“Lehmer sieve”的意思、由来-开放百科全书

词条

Lehmer sieve

释义

Construction
See also
References
Further reading
External links

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.

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.

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.^[1]

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 for the observation of a solution. This incarnation allowed checking of five thousand combinations a second.

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.

Several Lehmer sieves 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. {{CN|date=April 2015}}

References

1. ^W. W. Rouse Ball (1960) Lehmer's Machine, in Mathematical Recreations and Essays, Macmillan, New York, pp 61-62.

External links

Lehmer sieves, by Dr. Michael R. Williams, Head Curator of The Computer History Museum
Lehmer sieves at Computer History Museum (at the bottom of the page)

2 : History of computing hardware|One-of-a-kind computers

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Construction

See also

References

Further reading

External links