Slashdot Mirror
Researcher Modifies Sieve of Eratosthenes To Work With Less Physical Memory Space (scientificamerican.com)
grcumb writes: Peruvian mathematician Harald Helfgott made his mark on the history of mathematics by solving Goldbach's weak conjecture, which states that every odd number greater than 7 can be expressed as the sum of three prime numbers. Now, according to Scientific American, he's found a better solution to the sieve of Eratosthenes: "In order to determine with this sieve all primes between 1 and 100, for example, one has to write down the list of numbers in numerical order and start crossing them out in a certain order: first, the multiples of 2 (except the 2); then, the multiples of 3, except the 3; and so on, starting by the next number that had not been crossed out. The numbers that survive this procedure will be the primes. The method can be formulated as an algorithm." But now, Helfgott has found a method to drastically reduce the amount of RAM required to run the algorithm: "Now, inspired by combined approaches to the analytical 100-year-old technique called the circle method, Helfgott was able to modify the sieve of Eratosthenes to work with less physical memory space. In mathematical terms: instead of needing a space N, now it is enough to have the cube root of N." So what will be the impact of this? Will we see cheaper, lower-power encryption devices? Or maybe quicker cracking times in brute force attacks? Mathematician Jean Carlos Cortissoz Iriarte of Cornell University and Los Andes University offers an analogy: "Let's pretend that you are a computer and that to store data in your memory you use sheets of paper. If to calculate the primes between 1 and 1,000,000, you need 200 reams of paper (10,000 sheets), and with the algorithm proposed by Helfgott you will only need one fifth of a ream (about 100 sheets)," he says.
*sigh*
Getting tired of "news" posting _zero_ details.
Does anyone have details on the actual algorithm? Reference Implementation?
Seriously. I got a scholarship using a TRS80 and the Sieve of Eratosthenes.
Worse than that, they should have used the Libraries of Congress unit for storage capacity, not the ream.
Nullius in verba
If I 3D-print a Sieve of Eratosthenes, can I use it to drain cooked pasta?
You are welcome on my lawn.
Getting tired of "news" posting _zero_ details.
I'd be happier if the meagre details they do post were at least correct. If one fifth of a ream is 100 sheets then 200 reams is 100,000 sheets not 10,000 as the summary states.
The news is about a cube root, not a square root.
While you are right that the cube root is interesting, the Sieve of Eratosthenes is a different algorithm. Historically, you need an array of bits, with each bit set if it is the second bit after 2, the third bit after 3, the 5th bit after 5, etc. It is WAY faster than testing each number with the factors from 2 to the square root of the number.
As I understood it, rather than needing 1000 bits for the first 1000 numbers, you need cuberoot(1000) bits or 10 bits. They also say 1/5 the bits - so maybe someone can clarify that or post a better link.
(yeah, you can optimize a bit by ignoring the even numbers and so on but its still doesn't get you close to the cube root of memory).
Yeah 2 seconds after I posted my second message I found myself wishing for an edit feature...
This is slashdot, we don't go for all those commie-pinko futuristic hand-holding features from the 1990's.
I mean, if we let people edit their posts (even just during a 1-minute grace period), ohmygod where will it end??
Just cruising through this digital world at 33 1/3 rpm...
Adding 3 odd numbers gets you an odd number has never really astonished me.
Sure, but now we know that 206702934571364971352346820353 is guaranteed to have three prime addends.
And that ain't hay.
As part of a programming assignment I wrote two programs for finding primes.
The first one using a moving window technique. Lets say my window size is 100, so I fill in the numbers 1 to 100 into the window, do my sieve job on this, get the primes I got so far and put them in a list, and fill the window with the numbers 101 to 200, run them through the primes I got and then through whatever remains, extract the primes and add them to the list, etc...
The second was an instant filter system, i.e. I've got a list of tuples, each list element has a prime and a multiple of it, and my sieve table size is one, i.e. a counter. Lets say my list is A=(2,2) and B=(3,3), my counter is 4. While A2 is less than counter do A2 =A2+A1. A2 is now equal to A2, so counter is not prime. Next counter is 5, While A2 is smaller than counter do A2 = A2+A1, A2 is now bigger than counter, so it passes test A, while B2 is smaller than counter do B2=B2+B1, B2 is now bigger than counter, so it passes test B. End of prime list reached, so counter is prime. Create new tuple C(5,5) and add it to the list. Big advantage: No multiplications involved, the process of doing the while loop can be improved by using bit-shifted versions of the prime, so I only have additions, comparisons and bit shifts to deal with, which is easy and fast to implement with long integer implementations. And I need only to store the primes it found and their multiples, and the memory usage is very local and cache friendly.
Just out of curiosity I'd like to see their algorithm. Because some algorithms from math/CS look good on paper and are proven to run comparatively fast on a ideal Turing machine, but produce laughable results in real-life tests...
"So what will be the impact of this? Will we see cheaper, lower-power encryption devices? Or maybe quicker cracking times in brute force attacks?"
Neither.
It's a method to discover primes using elimination of non-primes up to the square root of the number you're after.
If you can get that far, you can get to the prime itself quite easily. It's not going to help discover new large primes without eliminating BILLIONS of numbers in between.
And from there it has nothing to do with cracking encryption whatsoever.
The impact of this is that a child's method of eliminating factorisable numbers slowly takes up slightly less storage space (i.e. slightly less variables held in RAM) than before. It's not a breakthrough in maths, but a slight efficiency saving in the computer science to perform the algorithm in practical terms.
From an optimal information-theory viewpoint:
1000 bits, 168 of which are true (the 168 primes below 1000) and 832 are false.
Given this model of the data, the optimal encoding of the 1's should use 2.573 bits each, while the optimal encoding of the 0's should use 0.265 bits each.:
ln(1000/168) / ln(2) = 2.573... bits
ln(1000/832) / ln(2) = 0.265... bits
The space required for the entire sequence:
(168 * ln(1000/168) + 832 * ln(1000/832)) / ln(2) = 653.109... bits
The model would have to be significantly better than this. Improvements to the model must produce a better probability estimate than the raw statistics. The most obvious single improvement to the model is to treat the even numbers as special, where a simple rule can give you 100% model accuracy and thus use 0 bits to encode all the even positions.
To get the entire sequence down to only 10 bits implies a very large computational overhead, because even with the prime probability all the way down to 1/1000 the list would still be:
(1 * ln(1000/1) + 999 * ln(1000/999)) / ln(2) = 11.407... bits.
So i'm thinking the O(N^1/3) doesnt apply to small values of n, but instead only to enormous values of n.
"His name was James Damore."
I was about to post something longer, but my computer deleted it at just the right moment. Summary: (a) The origin of this article was an interview given at an algebra colloquium in Buenos Aires a few weeks ago. Its appearance in Scientific American was a little unexpected (to me). I should be able to post a preprint soon. (b) In my colloquium talk, I made sure to mention that I had just come across a precedent in the literature: W. F. Galway, Dissecting a sieve to cut its need for space. In Algorithmic number theory (Leiden, 2000), vol 1838 of Lecture Notes in Comput. Sci., pages 297-312. Springer, Berlin, 2000. In both cases, we are talking about space essentially O(N^(1/3)) and time essentially O(N). Galway improves on the Atkin-Bernstein sieve, which is specifically about producing lists of primes. The sieve of Eratosthenes can be used for more general purposes, e.g., producing lists of factorizations or computing tables of values of arithmetic functions that depend on factorization. I actually got interested in the problem while using a sieve to produce successive values of mu(n), where mu is the Moebius function. As far as I can tell, there's a basic underlying idea being used in both cases, viz. Diophantine approximation. In brief, if you are finding primes (or what have you) in an interval [N,N+N^(1/3)], you do not have to sieve by every m=sqrt(N); you can tell in advance which integers m will have no multiples in that interval. This is all more or less orthogonal to [http://sweet.ua.pt/tos/software/prime_sieve.html]. Indeed what I do and what Oliveira e Silva does can very likely be combined. Best Harald Helfgott