Mathematician optimized Eratosthenes sieve to search for prime numbers with less memory consumption.

The 38-year-old Peruvian mathematician Harald Helfgott proved the ternary Goldbach hypothesis three years ago, and now he was able to optimize a computer algorithm for calculating the Eratosthenes sieve. Photo: Matías Loewy



In the III. BC ancient Greek mathematician, astronomer, geographer, philologist and poet Eratosthenes Kirensky invented a brilliant way to search for primes. A very effective and fast method that is still used today is called the sieve of Eratosthenes .



The essence is clear from the title. The sieve of Eratosthenes means searching for primes by the method of elimination. We take a list of numbers, exclude from it all composite numbers - and we get a list of prime numbers, as if sifting the list through a sieve.



In the form of the algorithm, the sieve of Eratosthenes is formalized as follows:

')

1. Write out all integers from two to n (2, 3, 4, ..., n) in a row.
2. Let the variable p be initially equal to two - the first prime number.
3. Cross out in the list the numbers from 2p to n, counting steps in p (these will be multiples of p: 2p, 3p, 4p, ...).
4. Find the first non-crossed number in the list greater than p, and assign the value of the variable p to this number.
5. Repeat steps 3 and 4 as long as possible.

After performing this operation, only primes remain uncrossed in the list.



Obviously, the computer implementation of the sieve of Eratosthenes requires a large amount of memory. So it was, until the 38-year-old Peruvian mathematician Harald Helfgott offered his solution to the problem.

Harald Helfgott

Harald Helfgott attracted widespread attention in 2013, when he managed to solve the Goldbach ternary problem . Goldbach's ternary problem is a weaker assertion of Goldbach's main binary problem , one of the most well-known open mathematical problems, which is still unsolved. This is a statement that any even number, starting with 4, can be represented as a sum of two prime numbers.



Goldbach's ternary hypothesis follows directly from the binary hypothesis. The ternary hypothesis states that any odd number, starting with 7, can be represented as a sum of three prime numbers. This hypothesis was proved for numbers from N to infinity by Ivan Vinogradov in 1937, for which he received the Stalin Prize and the title of Hero of Socialist Labor. Soviet mathematicians thought that Vinogradov proved the hypothesis for all numbers, but in fact later it turned out that the lower bound N in Vinogradov’s work is 10 ^{6 846 168} .



Peruvian mathematician Harald Helfgott was able to finally prove this hypothesis, reducing the N limit to an acceptable number of 10 ²⁹ , and all the other numbers were checked on a supercomputer. His evidence was published in the journal Science on May 24, 2013 (doi: 10.1126 / science.340.6135.913). It is confirmed by other qualified mathematicians who are able to understand the evidence, for example, by Terence Tao .



Now the talented mathematician Harald Helfgott, whose ancestors come from the Chernivtsi region, has directed his efforts to another important task of modern science - the optimization of the search for prime numbers. He was able to propose an improved version of the Eratosthene lattice - a method of searching for prime numbers, formulated in about 240 BC. The new version in the computer implementation requires less RAM, which means less paging from virtual memory - therefore, the process is significantly accelerated.



“Like many other 10-year-olds, I studied the Eratosthenes sieve in elementary school,” says Harald Helfgott, who now works at the National Center for Scientific Research in France and the University of Gottingen.



Harald admitted that he began to think “even too much” about the Eratosthenes lattice while working on the ternary Goldbach problem. In particular, the amount of data in memory. He understood that it is the limited amount of memory that is the bottleneck, which reduces the maximum possible calculation speed in this case.



Experts say that the efficiency of the algorithm is determined by two factors:

1. The number of operations per bit of input data.
2. The number of bits in memory during the execution of instructions.

By the number of operations per bit, the Eratosthene lattice is relatively effective. It grows in proportion to the size of the interval from 1 to N. But if you look at what needs to be stored in memory for each step of the algorithm at large intervals, then there is no question of any efficiency.

Sieve Optimization of Eratosthenes

To optimize the computer algorithm for the sieve of Eratosthenes, the mathematician used a variant of the same method that he used when working on the Goldbach ternary problem. This is a circular method of Hardy-Littlewood . The method itself, which at the beginning of the last century was wonderfully perfected by mathematician Ivan Vinogradov, as a result of which he was almost able to prove Goldbach's hypothesis.



According to the Hardy-Littlewood method, the solution of the problem is given by an integral over the unit circle of some series. This integral is divided into two, one of which is estimated, and about the other, its relative smallness is proved. The components of the first sum are called large arcs, and the second one - small.



The mathematician himself explains the method as follows:

“The analysis of the number of decisions is made, in fact, by means of the Fourier transform . Imagine that prime numbers are sounds on some record, say, at times 2, 3, 5, 7, 11, and so on, in microseconds. After the transformation, you get a kind of noise in which you try to hear some notes. Among them there are those that are heard quite well - this is the big arc. And there are frequencies that are simply noise fragments — these are small arcs. The whole method is divided into two parts - the selection of notes and proof that the rest is actually noise. Estimates for large arcs are responsible for the first part of the method, and small ones for the second.

Based on the Hardy-Littlewood method, the scientist developed an approach that allows you to use the memory size N (cube root of N) instead of the amount of RAM N.



Figuratively speaking, instead of 1 gigabyte of memory, i.e. 10 ⁹ bytes (not to be confused with gibbyte 2 ³⁰ ) only 1 kilobyte is needed (∛10 ⁹ = 10 ³ bytes).



Gigabyte and kilobyte - a big difference, you see.



In a sense, such optimization was a side effect of solving the Goldbach problem.



Harald Helfgott presented theses of his work at the 21st Latin American Colloquium on Algebra in Buenos Aires from July 25-29, 2016, and also at the Sinapsis 2016 event in Paris - an informal meeting of Peruvian scientists living in Europe.



There are different algorithms for finding prime numbers, but Helfgott notes that the Eratosthenes sieve has an important quality - it is compatible with other mathematical operations, such as factorization, and in fact, factorization (expansion of large numbers into prime factors) is based on cryptography. “Factoring has become a key element of modern civilization,” Helfgott states.