"Genius" needed to speed up this not-even-a-sieve in Python but he did not succeed

[ONeil]

I need help regarding a Mersenne Prime Sieve which I edited to perform this task; this code is from a perfect number generator. The problem is the program slows down at 11213 in python. Can anyone offer some speed enhancements for this sieve in Python? The output starts out like this.

2
3
5
7
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
4253
4423
9689
9941
11213

    
from itertools import count
 
def postponed_sieve():                   # postponed sieve, by Will Ness      
    yield 2; yield 3; yield 5; yield 7;  # original code David Eppstein, 
    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
 
def prime_sieve():                   # postponed sieve, by Will Ness      
    yield 2; yield 3; yield 5; yield 7;  # original code David Eppstein, 
    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
 
def mod_mersenne(n, prime, mersenne_prime):
    while n > mersenne_prime:
        n = (n & mersenne_prime) + (n >> prime)
    if n == mersenne_prime:
        return 0
    return n
 
def is_mersenne_prime(prime, mersenne_prime):
    s = 4
    for i in range(prime - 2):
        s = mod_mersenne((s*s - 2), prime, mersenne_prime)
    return s == 0
 
def calculate_perfects():
    yield(2)
    primes = prime_sieve()
    next(primes)                     #2 is barely even a prime
    for prime in primes:
        if is_mersenne_prime(prime, 2**prime-1):
            yield(prime)
                  
if __name__ == '__main__':
    for perfect in calculate_perfects():
        print(perfect)
#edited by Tom E.O'Neil to find Mprimes

[ONeil]

you can see it in action here:


Hit run once its done loading.

https://repl.it/@TommyONeil/HumongousRubberyElements

[Uncwilly]

I have again made a link of your's, not a hyperlink. The user needs to be more involved before you your code on their machine.

[ONeil]

Originally Posted by Uncwilly

I have again made a link of your's, not a hyperlink. The user needs to be more involved before you your code on their machine.

Hi Uncwilly this is not referenced from my site. It resides at repl.it. Is there anyway you could relink? Thanks

[Uncwilly]

Originally Posted by ONeil

Hi Uncwilly this is not referenced from my site. It resides at repl.it. Is there anyway you could relink? Thanks

Nope. I don't care where you placed the code. It is code that you wrote. You want to have users run it from their machine. There needs to be more user interaction before the code runs. Links to zip's or to pages that have a link to the files are ok.

Linking directly to an exe or to page that runs code is not ok. When I previously told you about this you failed to understand where problems could pop up.

[nordi]

The first step would be to know which part of your code needs to be optimized. Use Python's profiler to figure out where your code spends most of its time, then focus on that code.

[rogue]

I suggest that you learn a language like C if you want speed.

[LaurV]

@op: additional of what other people told you in the past about demonstrating your knowledge (or... ignorance) not only about math but also about programming, here you also proved that you don't know what a "sieve" is. This is not a sieve, it is an (extremely slow) program that finds mersenne primes. You use some wheel to find primes, then do LL test for each prime to see if the corespondent mersenne is itself prime. But you can not use the information to "sieve" anything with it. It should be nice if you could "sieve" the prime exponents in such a way to avoid doing at least few percents of the LL tests, even one percent of them, then THAT should have been A RESULT. Please note the uppercase letters. This what you show is crap.

[ONeil]

Originally Posted by LaurV

@op: additional of what other people told you in the past about demonstrating your knowledge (or... ignorance) not only about math but also about programming, here you also proved that you don't know what a "sieve" is. This is not a sieve, it is an (extremely slow) program that finds mersenne primes. You use some wheel to find primes, then do LL test for each prime to see if the corespondent mersenne is itself prime. But you can not use the information to "sieve" anything with it. It should be nice if you could "sieve" the prime exponents in such a way to avoid doing at least few percents of the LL tests, even one percent of them, then THAT should have been A RESULT. Please note the uppercase letters. This what you show is crap.

I maybe ignorant, but at least I'm trying to find Mersenne Primes.

[retina]

Originally Posted by ONeil

I maybe ignorant, but at least I'm trying to find Mersenne Primes.

You are trying to reinvent the wheel. There is nothing wrong with reinventing the wheel, but first you have to determine what is wrong with the current wheel, and then improve on that. So far all you have done is make the same wheel in a less efficient manner. You have not put in any new concepts or designs, yet.

You have implemented the well known LL test in a scripting language. We have all done that at some point just to get a feel for how things work. But it is not something important enough to post to a public board and expect everyone else to "improve" it for you. If you are really serious about it, learn about FFT and/or NTT (or preferably invent a new faster method) and implement the test in optimised assembly on your favourite high-performance CPU. THEN you will get some attention for doing something important.

[science_man_88]

Originally Posted by ONeil

I maybe ignorant, but at least I'm trying to find Mersenne Primes.

y/k+(y-1)/(2kp)=1 iff 2p+1 divides 2kp+1 true or false.