mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > ONeil

Reply
 
Thread Tools
Old 2018-05-16, 18:51   #1
ONeil
 
Dec 2017

24×3×5 Posts
Minus "Genius" needed to speed up this not-even-a-sieve in Python but he did not succeed

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.

Quote:
2
3
5
7
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
4253
4423
9689
9941
11213
Code:
    
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 is offline   Reply With Quote
Old 2018-05-17, 21:19   #2
ONeil
 
Dec 2017

24×3×5 Posts
Default

you can see it in action here:


Hit run once its done loading.

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

Last fiddled with by Uncwilly on 2018-05-17 at 22:10 Reason: Made link unclickable.
ONeil is offline   Reply With Quote
Old 2018-05-17, 22:11   #3
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

22·3·17·47 Posts
Default

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.
Uncwilly is online now   Reply With Quote
Old 2018-05-17, 23:33   #4
ONeil
 
Dec 2017

24·3·5 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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
ONeil is offline   Reply With Quote
Old 2018-05-18, 02:02   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

225648 Posts
Default

Quote:
Originally Posted by ONeil View Post
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.
Uncwilly is online now   Reply With Quote
Old 2018-05-18, 19:26   #6
nordi
 
Dec 2016

23·32 Posts
Default

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.
nordi is offline   Reply With Quote
Old 2018-05-18, 19:28   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·7·11·41 Posts
Default

I suggest that you learn a language like C if you want speed.
rogue is online now   Reply With Quote
Old 2018-05-19, 05:48   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24EC16 Posts
Default

@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.

Last fiddled with by LaurV on 2018-05-19 at 05:50
LaurV is offline   Reply With Quote
Old 2018-05-19, 08:36   #9
ONeil
 
Dec 2017

24·3·5 Posts
Default

Quote:
Originally Posted by LaurV View Post
@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.
ONeil is offline   Reply With Quote
Old 2018-05-19, 09:28   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,143 Posts
Default

Quote:
Originally Posted by ONeil View Post
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.
retina is offline   Reply With Quote
Old 2018-05-19, 11:46   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by ONeil View Post
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
any suitable sieve written in C or Python? Shen Information & Answers 4 2017-01-05 04:49
Sieve needed for a^(2^b)+(a+1)^(2^b) robert44444uk Software 55 2009-08-12 06:39
Sieve needed for k*b1^m*b2^n+1 beyastard Software 55 2009-07-29 12:51
Volunteer needed for sieve merging MooooMoo Twin Prime Search 9 2007-01-01 21:13
Pentium4 2.8Ghz speed help needed Clyde83 Hardware 26 2006-08-21 10:33

All times are UTC. The time now is 00:23.

Wed May 19 00:23:27 UTC 2021 up 40 days, 19:04, 0 users, load averages: 2.31, 2.26, 1.97

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.