Prime Number Sieves

[Deleted member 473]

In the late '80's (as opposed to the late '70's) I took to torturing an Amstrad 1640 with Mandelbrot Set images that required days to generate. Now they render in seconds to full iPad resolution.

Same here, with a BBC computer and then an Atari ST. Those were the days! Even my phone can do a better job now, at a higher resolution!

 

[Deleted member 473]

In the late '80's (as opposed to the late '70's) I took to torturing an Amstrad 1640 with Mandelbrot Set images that required days to generate. Now they render in seconds to full iPad resolution.

Black Hole, you may or may not have seen this implementation:

https://code.google.com/p/primesieve/


"primesieve generates the first 50,847,534 primes up to 10^9 in just 0.4 seconds on a single core of an Intel Core i7-920 2.66GHz, this is about 50 times faster than an ordinary C/C++ sieve of Eratosthenes implementation and about 10,000 times faster than trial-division."

 

[Black Hole]

Thanks, but optimisation is not really the point. The total processing time is not just the seconds, minutes, or hours that the processor runs, it is also the time spent coding in the first place. If one is only going to run a program and get the output once, there is no point spending many hours coding to shave off a few seconds of run time.

Also, the optimisations are not going to be much use if they rely on features that are not available in the target processor. These fast sieves do not run division tests - what they do is the same as we would have done at school: draw up a grid and cross off every second number, then every third, then every fifth... To implement my output using this method requires an array of (roughly) 30,000,000 elements, which might be tricky to implement on the Humax.

Besides, the point is to torture the processor - not make life easy for it!

 

[Deleted member 473]

Thanks, but optimisation is not really the point. The total processing time is not just the seconds, minutes, or hours that the processor runs, it is also the time spent coding in the first place. If one is only going to run a program and get the output once, there is no point spending many hours coding to shave off a few seconds of run time.

Also, the optimisations are not going to be much use if they rely on features that are not available in the target processor. These fast sieves do not run division tests - what they do is the same as we would have done at school: draw up a grid and cross off every second number, then every third, then every fifth... To implement my output using this method requires an array of (roughly) 30,000,000 elements, which might be tricky to implement on the Humax.

Besides, the point is to torture the processor - not make life easy for it!

I can't say I agree there. Mathematical optimization can transform an intractable calculation into one that is feasible in reasonable time. There is all the difference in the world between a $2^n$ run time and an $n log n$ run time. I know this optimization isn't so dramatic, but real advances have been made recently to allow real time rendering of 3D scenes, a calculation that was intractable without advanced theoretical advances.

Even in sorting algorithms, the difference between bubble sort and heap, merge and quick sort is dramatic and beautiful.

The algorithm quoted is a mathematical refinement of naive methods and I don't think it is any more expensive on storage than yours, is it? (I haven't examined it in detail. The algorithm claims $O(\sqrt n)$ storage, so unless you are after primes up to 900,000,000,000,000 you should be fine! It is not as you suggested, as far as I can see.) Also, the time spent on devising it is minimal compared with the time involved in computing a far smaller test case only a few decades ago. Security and encryption rely on finding large primes, and any one-time advance is probably worth the effort.

If you want to torture a processor, make it divide random numbers over and over!

This area of algorithms and computational and storage complexity is an area I used to work in, and I am quite fond of it.

 

[Black Hole]

You're welcome to see if you can get it to run on the Humax, and if you can beat my 14 minutes to generate the first 3,713,160 primes, bearing in mind I only spent about an hour on it.

Finding large primes for encryption purposes requires primes that are intractable by sieve methods. For this, a candidate number is tested by a process in number theory which fails if the number is definitely not a prime, but cannot say that the number definitely is prime. A number of such tests are applied, and if they all pass it is taken as a high probablility that the candidate is indeed prime (and the tests are such that if they pass, the candidate is good enough for the purpose).

I used to work in secure military communications, and public key elliptic curve encryption algorithms is a particular interest.