Primes [was Re: find all multiplicands and multipliers for a number]

[Steven D'Aprano]

On Sun, 12 Apr 2015 05:17 pm, Marko Rauhamaa wrote:

> The range(2, n) version is 3 times slower than the candidates() version.
> 
> And in fact, the sqrt optimization now makes the original version 20%
> faster:


MY pyprimes module includes a series of progressively better (or, in the
opposite direction, progressively worse) prime number generators. The doc
string for the pyprimes.awful module says:

"""
This is a collection of awful and naive prime-related functions, supplied
for educational purposes, as toys, curios, or as terrible warnings on
what **not** to do.

None of these methods have acceptable performance in practice; they are
barely tolerable even for the first 100 primes.
"""

It starts off with an adaptation of the very first prime generator I ever
wrote, in RPL on a HP calculator oh so many years ago. It was more or less
a naive implementation of the mathematical definition: for each candidate
prime n, I test it against *every* potential divisor starting with 2 and
ending with n-1. Yes, I actually did write that for real.

Not surprisingly, it starts off horribly slow, and gets ever slower as the
primes get further apart. Over the first 1000 primes, it is five times
slower than the second worst performer, and about 1430 times slower than
the best performer.

Starting with that as the base:

- stopping once you hit a factor gives you a factor of 5 speed up;
- skipping even numbers (apart from 2) gives you an additional 
  factor of 2 speed up;
- stopping at the square root of n instead of going all the way to 
  n-1 gives you an additional speed up of 16 times;

- dividing only by primes rather than all odd numbers *slows* the
  function down by about 5%, at least for generating the first 
  1000 primes.

Dividing only by primes doesn't pay off until you get to about fifty
thousand primes or so.

So that's a good example of how some optimizations don't pay off until you
get to sufficiently large inputs. Even so, none of those four "awful" trial
division generators perform well enough to use in production. For that, you
have to start using a sieve algorithm.



On my computer, I get these results for generating the first 1000 primes:


[steve at ando src]$ python2.7 pyprimes/speed.py
Calculating speeds for first 1000 primes...
Done!
Total elapsed time: 5.6 seconds

Generator                             Elapsed    Speed
                                      (sec)      (primes/sec)
==============================================================
pyprimes.awful.primes0                4.14         241.8
pyprimes.awful.primes1                0.79        1271.8
pyprimes.awful.primes2                0.41        2445.5
pyprimes.awful.turner                 0.18        5495.9
pyprimes.probabilistic.primes         0.03       30840.5
pyprimes.awful.primes4                0.03       38853.1
pyprimes.awful.primes3                0.02       40940.0
pyprimes.sieves.sieve                 0.01      133742.7
pyprimes.sieves.cookbook              0.01      194028.0
pyprimes.sieves.wheel                 0.00      206483.7
pyprimes.sieves.croft                 0.00      344359.9
==============================================================




Here are the results for the four sieves, taken over the first million
primes.



Calculating speeds for first 1000000 primes...
Done!
Total elapsed time: 167.2 seconds

Generator                             Elapsed    Speed
                                      (sec)      (primes/sec)
==============================================================
pyprimes.sieves.wheel                 122.50        8163.4
pyprimes.sieves.sieve                 17.09       58509.9
pyprimes.sieves.cookbook              16.52       60520.6
pyprimes.sieves.croft                 10.48       95445.0
==============================================================


The Croft Spiral algorithm averages 95 thousand primes per second over the
first million primes, significantly better than the next best algorithm.
I'm not sure why the wheel algorithm starts off so promising and then falls
so badly behind the other three.


http://code.google.com/p/pyprimes/source/browse/



-- 
Steven