1

I am a bit struggling with further optimizing my prime calculating function.

So far I ended up with the sieve of Eratosthenes.

I found on https://primesieve.org/ a hint to further optimize this with the implementation of wheels and a link to this article: ftp://ftp.cs.wisc.edu/pub/techreports/1991/TR1028.pdf

I tried to translate this pseudocode into python, but it's not properly working. I have the feeling that the iterations in step B are not correct. When calculating prime_sieve_fast(100, 3), 91 is not removed. This is logical since the running variables never reach 7*13 or 13*7. What did I get wrong?

def prime_sieve(n):
    prime_list=[0,0]
    for i in range(2,n+1):
        prime_list.append(1)
    for p in range(2,int(n**(1/2))+1):
        for j in range(p**2,n+1,p):
            prime_list[j]=0
    primenumbers=[]
    for i in range(n):
        if prime_list[i+1]==1:
            primenumbers.append(i+1)
    return prime_list,primenumbers    

def prime_sieve_faster(n,n_wheel):
    primes=prime_sieve(100)[1][:n_wheel+1]
    w=wheel(n_wheel,primes[:-1])
    M=len(w)
    prime_list=[1]*(n+1)
    for r in range(M):
        if w[r%M]==0:
            b=0
        else:
            b=1
        for i in range(r,n+1,M):
            prime_list[i]=b
    for i in range(n_wheel):
        prime_list[primes[i]]=1
    prime_list[1]=0
    for p in range(primes[n_wheel],int(n**(1/2))+1):
        print(p)
        step=w[p%M]
        if step==0:
            prime_list[p]=0
        else:
            for f in range(p,p+M+1,step):
                for x in range(p*f,n+1,M*p):
                    prime_list[x]=0
                    print(p,f,x,M*p)
    primenumbers=[]
    for i in range(n):
        if prime_list[i+1]==1:
            primenumbers.append(i+1)
    return prime_list,primenumbers


def wheel(k,primes):
    M=1
    for prime in primes:
        M*=prime
    W=[1]*M
    for prime in primes:
        for x in range(0,M,prime):
            W[x]=0
    W[M-1]=2
    prev=M-1
    for x in range (M-2,0,-1):
        if W[x]!=0:
            W[x]=prev-x
            prev=x
    return W
Will Ness
  • 70,110
  • 9
  • 98
  • 181
FordPrefect
  • 320
  • 2
  • 11
  • 2
    Please check your indentations in the post and fix as needed, this is difficult to read and wouldn't run as-is – G. Anderson Oct 29 '18 at 17:55
  • Sry, I corrected it. It was my first post here and the code blocks are not really copy and paste friendly as I had to figure out. Edit: Apparently there are also some unnecessary print() in the code which I put there for analyzing. If the numbers get big one should comment them. – FordPrefect Oct 29 '18 at 18:26
  • The function normal_sieve in [this code](https://github.com/user-name-is-taken/new_prime_sieve/blob/master/best_sieve) was the best sieve I could come up with. It doesn't use wheels, but you might want to take a look. – mikeLundquist Oct 29 '18 at 19:10
  • I will have a look at it. However, I really want to understand why my implementation of the code in this paper isn't working. I stumbled over this stuff, while struggling with project euler Problem 501, I already figured out that I have to find a good implementation of pi(x) rather then counting up lots of primes by finding them. But since I spent so much time on understanding different prime sieves and on their implementation I really want to know whats wrong here. The wheel works proper. Also the first half of prime_sieve_fast is working properly. – FordPrefect Oct 29 '18 at 19:25
  • The list with only ones for the spokes ist set correctly only the sieving afterwards is not running as it should because of a false implementation of the boundaries or because I oversea some unmentioned limitation in the paper. – FordPrefect Oct 29 '18 at 19:31
  • I use wheels [here](https://stackoverflow.com/a/30563958/849891) but it's in an indefinite sieve. see if it helps in any way.... – Will Ness Oct 29 '18 at 20:29
  • Thanks for the link. But I think you are using a quite different attempt than in the paper. So the matter ist not so much to get a algorythm for the fastest prime generator in python. It ist more that I want to understand where I didn't get the instructions from that paper right. It really bothers me. BTW: @user4757074 for curiosity I tried out your code. But the first function does not work because the index in the inner core becomes bigger than the length of the array. From the second one I tried out the idea of using a bitarray, but it takes two times longer than mine, actually. – FordPrefect Oct 29 '18 at 20:41
  • What I'm saying is you should start with simplifying your code. For example, doing `for i in range(2,n+1):prime_list.append(1)` accomplishes the same thing as `prime_list += range(2,n+1)`. You could use a PEP8 linter to do a lot of this for you. normal_sieve was the simplest and fastest sieve I could find. In real C code, you'll be using a bit array. But again, the bit array isn't the point. The point is SIMPLIFY. And yeah, don't look at sieve in that code, just normal_sieve. – mikeLundquist Oct 29 '18 at 21:27
  • i guess you mean prime_list=[0,0]+[1]*(n-1). What you wrote isn't identical. In fact that is some small percentage faster. But I guess the improvements of the correct integration of the wheel are orders of magnitude faster. – FordPrefect Oct 29 '18 at 22:38
  • the wheel's [speedup](https://codereview.stackexchange.com/q/92365/9064) is `PROD( p/(p-1) )` over all `p`s in `wheel`. taking `wheel = {3,5,7,11}` it's *2.4x*, and with `13` it's *2.6x*. So, *not* even one order of magnitude. The prime `2` gives *2x* the speedup by itself, so technically it's ~ *5x* speedup overall, but it is so easy to skip over evens that I'd say it doesn't count. And those speedups *are* theoretical -- the space use rises so much that dealing with the wheel mechanics quickly overcomes the expected benefits. I got my *2.2x* speedup with `3,5,7` and I was happy with it. :) – Will Ness Oct 30 '18 at 07:01

0 Answers0