Lehmer sieve

Last updated
A Lehmer sieve - a primitive digital computer once used for finding primes and solving simple Diophantine equations. Computer History Museum (4145886786).jpg
A Lehmer sieve - 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.

Contents

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. [ citation needed ]

See also

Related Research Articles

<span class="mw-page-title-main">Algorithm</span> Sequence of operations for a task

In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes and deduce valid inferences, achieving automation eventually. Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus".

<span class="mw-page-title-main">Analog computer</span> Computer that uses continuously variable technology

An analog computer or analogue computer is a type of computer that uses the continuous variation aspect of physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved. In contrast, digital computers represent varying quantities symbolically and by discrete values of both time and amplitude.

The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented as either "1" or "0", but other representations such as true/false, yes/no, on/off, or +/ are also widely used.

<span class="mw-page-title-main">Claude Shannon</span> American mathematician and information theorist (1916–2001)

Claude Elwood Shannon was an American mathematician, electrical engineer, computer scientist and cryptographer known as the "father of information theory".

<span class="mw-page-title-main">History of computing hardware</span> From early calculation aids to modern day computers

The history of computing hardware covers the developments from early simple devices to aid calculation to modern day computers.

<span class="mw-page-title-main">Logic gate</span> Device performing a Boolean function

A logic gate is an idealized or physical device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output.

In electrical engineering, a switch is an electrical component that can disconnect or connect the conducting path in an electrical circuit, interrupting the electric current or diverting it from one conductor to another. The most common type of switch is an electromechanical device consisting of one or more sets of movable electrical contacts connected to external circuits. When a pair of contacts is touching current can pass between them, while when the contacts are separated no current can flow.

SPICE is a general-purpose, open-source analog electronic circuit simulator. It is a program used in integrated circuit and board-level design to check the integrity of circuit designs and to predict circuit behavior.

<span class="mw-page-title-main">Theoretical computer science</span> Subfield of computer science and mathematics

Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.

<span class="mw-page-title-main">D. H. Lehmer</span> American mathematician

Derrick Henry "Dick" Lehmer, almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s and devised the Lucas–Lehmer test for Mersenne primes. His peripatetic career as a number theorist, with him and his wife taking numerous types of work in the United States and abroad to support themselves during the Great Depression, fortuitously brought him into the center of research into early electronic computing.

<span class="mw-page-title-main">History of computing</span> Aspect of history

The history of computing is longer than the history of computing hardware and modern computing technology and includes the history of methods intended for pen and paper or for chalk and slate, with or without the aid of tables.

<span class="mw-page-title-main">History of computer science</span> Aspect of history

The history of computer science began long before the modern discipline of computer science, usually appearing in forms like mathematics or physics. Developments in previous centuries alluded to the discipline that we now know as computer science. This progression, from mechanical inventions and mathematical theories towards modern computer concepts and machines, led to the development of a major academic field, massive technological advancement across the Western world, and the basis of a massive worldwide trade and culture.

CALDIC was an electronic digital computer built with the assistance of the Office of Naval Research at the University of California, Berkeley between 1951 and 1955 to assist and enhance research being conducted at the university with a platform for high-speed computing.

<span class="mw-page-title-main">Computer</span> Automatic general-purpose device for performing arithmetic or logical operations

A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These programs enable computers to perform a wide range of tasks. A computer system is a nominally complete computer that includes the hardware, operating system, and peripheral equipment needed and used for full operation. This term may also refer to a group of computers that are linked and function together, such as a computer network or computer cluster.

<span class="mw-page-title-main">Derrick Norman Lehmer</span> American mathematician (1867–1938)

Derrick Norman Lehmer was an American mathematician and number theorist.

Lehmer is a surname. Notable people with the surname include:

<span class="mw-page-title-main">Electronic engineering</span> Electronic engineering involved in the design of electronic circuits, devices, and their systems

Electronic(s) engineering is a sub-discipline of electrical engineering which emerged in the early 20th century and is distinguished by the additional use of active components such as semiconductor devices to amplify and control electric current flow. Previously electrical engineering only used passive devices such as mechanical switches, resistors, inductors, and capacitors.

Most of the terms listed in Wikipedia glossaries are already defined and explained within Wikipedia itself. However, glossaries like this one are useful for looking up, comparing and reviewing large numbers of terms together. You can help enhance this page by adding new terms or writing definitions for existing ones.

This glossary of electrical and electronics engineering is a list of definitions of terms and concepts related specifically to electrical engineering and electronics engineering. For terms related to engineering in general, see Glossary of engineering.

<span class="mw-page-title-main">Hugh C. Williams</span> Canadian mathematician (born 1943)

Hugh Cowie Williams is a Canadian mathematician. He deals with number theory and cryptography.

References

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

Further reading