An Infinite Prime Number Generator

Primes, divisors, arithmetic, number properties, ...
Post Reply
MuthuVeerappanR
Posts: 538
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

An Infinite Prime Number Generator

Post by MuthuVeerappanR »

Hi all, I recently saw a post on an Infinite Prime Number Generator on Stack Exchange given below.

Code: Select all

from itertools import count
from timeit import default_timer

start = default_timer()
                                         # ideone.com/aVndFM
def postponed_sieve():                   # postponed sieve, by Will Ness      
    for c in (2, 3, 5, 7):  # original code David Eppstein,
      yield c
    sieve = {}                           # Alex Martelli, ActiveState Recipe 2002
    ps = postponed_sieve()               # a separate base Primes Supply:
    p = next(ps) and next(ps)            # (3) a Prime to add to dict
    q = p*p                              # (9) its sQuare 
    for c in count(9, 2):                 # the Candidate
        if c in sieve:               # c's a multiple of some base prime
            s = sieve.pop(c)         #     i.e. a composite ; or
        elif c < q:  
             yield c                 # a prime
             continue              
        else:   # (c==q):            # or the next base prime's square:
            s=count(q+2*p,2*p)       #    (9+6, by 6 : 15,21,27,33,...)
            p=next(ps)               #    (5)
            q=p*p                    #    (25)
        for m in s:                  # the next multiple 
            if m not in sieve:       # no duplicates
                break
        sieve[m] = s                 # original test entry: ideone.com/WFv4f

res = 0
for k in postponed_sieve():
  if k > 10000000:
    break
  res += 1
  #print(k)

print(res)
print(default_timer() - start)
The code runs through all odd numbers and does 'something' to filter out the primes. I thought if I can only check numbers 1 and 5 mod 6, I can achieve a better run time. But to my surprise, there are no marked difference in timings. Even more surprisingly, I changed the code to check appropriate numbers mod 30, and even then I can see no difference in timings.

So my question is WHY? Can anyone point out the reason for this? Especially with the 'mod 30' version, we are checking only 8 out of every 30 numbers, rather than 15 out of every 30 numbers in the 'mod 2' version. Even discounting for certain computing aspects, I expect atleast 25% reduction in time. But no good came out of the modification. I can't understand why.

Mod 6 version

Code: Select all

from itertools import count
from timeit import default_timer

start = default_timer()

def psieve():
  for k in (5, 7, 11):
        yield k
  D = {}
  ps = psieve()
  p = next(ps)
  q = p * p
  for temp in count(12, 6):
    for j in (1, 5):
      k = temp + j
      if k in D:
        step = D.pop(k)
      elif k < q:
        yield k
        continue
      else:
        step = 2 * p
        p = next(ps)
        q = p * p
      res = k + step
      while res in D or res % 6 not in (1, 5):
        res += step
      D[res] = step

res = 0
for k in psieve():
  if k > 10000000:
    break
  res += 1
  #print(k)

print(res + 2)
print(default_timer() - start)
Mod 30 version

Code: Select all

from itertools import count
from timeit import default_timer

start = default_timer()

def psieve():
  for k in (7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47):
    yield k
  D = {}
  ps = psieve()
  p = next(ps)
  q = p * p
  for temp in count(49, 30):
    for j in (0, 4, 10, 12, 18, 22, 24, 28):
      k = temp + j
      if k in D:
        step = D.pop(k)
      elif k < q:
        yield k
        continue
      else:
        step = 2 * p
        p = next(ps)
        q = p * p
      res = k + step
      while res in D or res % 30 not in (1, 7, 11, 13, 17, 19, 23, 29):
        res += step
      D[res] = step

res = 0
for k in psieve():
  if k > 10000000:
    break
  res += 1
  #print(k)

print(res + 3)
print(default_timer() - start)
Last edited by MuthuVeerappanR on Tue Nov 13, 2018 10:50 am, edited 1 time in total.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
v6ph1
Posts: 134
Joined: Mon Aug 25, 2014 7:14 pm

Re: An Infinite Prime Number Generator

Post by v6ph1 »

I don't know how the checks will be compiled, but I think, there is a hidden complexity in the loop checking:
e.g.
res = k + step
while res in D or res % 30 not in (1, 7, 11, 13, 17, 19, 23, 29):

You iterate through all (uneven) multiples - even if you don't store them, but in the case mod 6, you only need to calc the multiples, which are equal to 1 or 5 mod 6:
So if p % 6 = 1, you need to set step alternating to 4*p and 2*p.
If p % 6 = 5: 2*p and 4*p (in this order)

For mod 30, you can calculate the 8 arrays by your self.
Image
MuthuVeerappanR
Posts: 538
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: An Infinite Prime Number Generator

Post by MuthuVeerappanR »

Thanks v6ph1. I too arrived at the same loop for making the program slow. But I think it may be slightly different.

Rather than the loop checking, I think the runs more often as the chance of hitting the numbers with mod in the given set becomes low. That I think is the trade-off in the higher mod versions.

With some experimentation, I think the mod-6 version is marginally better than the original whereas higher mod-version don't do any good.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
v6ph1
Posts: 134
Joined: Mon Aug 25, 2014 7:14 pm

Re: An Infinite Prime Number Generator

Post by v6ph1 »

For sure, mod 6 will have a better performance than mod 2 -> the speedup is around 1.4 ... 1.5
and for mod 30, we will have a speedup of 1.8 in comparison to mod 2.

It is possible to optimize the performance of the higher versions as mod 6.
But the max performance (n/2)/EulerPhi(n), which is only high for numbers n a lot of prime factors.
2->1 (2.0), 6->2(3.0), 30->8 (3.75), 210->48 (4.375)
And the memory consumption is higher.
So the optimum can be found between 210 (2*3*5*7) and 2310 (2*3*5*7*11)
Easy to implement is mod 30, as the array index can be reduced by a logical operation without mod.
Image
MuthuVeerappanR
Posts: 538
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: An Infinite Prime Number Generator

Post by MuthuVeerappanR »

I changed the code to remove the loop-checking and use modified-step values but still no improvements in timing.

For example, the mod-2 version takes ~ 75 secs to list all primes upto 10^8, the mod-6 version takes ~ 85 secs whereas the step-adjusted-mod-6 version takes ~ 95 secs.

step-adjusted-mod-6 vesion

Code: Select all

from itertools import count
from timeit import default_timer

start = default_timer()

def psieve():
  for k in (5, 7, 11):
        yield k
  D = {}
  ps = psieve()
  p = next(ps)
  q = p * p
  mul = {(1, 4): 1, (5, 4): 2, (1, 2): 2, (5, 2): 1}
  for temp in count(12, 6):
    for j in (1, 5):
      k = temp + j
      if k in D:
        step = D.pop(k)
      elif k < q:
        yield k
        continue
      else:
        step = 2 * p
        p = next(ps)
        q = p * p
      res = k + step * mul[(k % 6, step % 6)]
      while res in D:
        res += step * mul[(res % 6, step % 6)]
      D[res] = step

res = 0
for k in psieve():
  if k > 10 ** 8:
    break
  res += 1
  #print(k)

print(res + 2)
print(default_timer() - start)
I think this is the reason I don't like CS. Seems everything's right and we expect a reduction in runtime but on the contrary, it actually increases.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
User avatar
yourmaths
Posts: 34
Joined: Mon Aug 25, 2014 11:00 am

Re: An Infinite Prime Number Generator

Post by yourmaths »

I did something similar to this when I was learning about the many applications of sieving. At the time I could fit a sieve of size around 10^8 in memory, so sieving just odd numbers gives a quick algo for primes up to 2x10^8. Running two sieves, residue 1 and 5 mod 6 boosts performance by a factor of 3, so I went ahead and coded a parallel sieve mod 2310. I saved the primes (actually the difference between successive primes to save disk space) for each residue class in a separate file, with the intention of being able to open each file at the same time and to use python generators to return the next prime in sequence.

The only problem was that I found out that there is apparently a (machine rather than software) limit to the number of files you can have open at the same time (on the order of about 100) so that approach didn't work. I still have the 5-6 GB of primes up to 2x10^11 saved on a portable hard drive somewhere...
level = lambda number_solved: number_solved // 25
Image
Post Reply