mersenneforum.org "Genius" needed to speed up this not-even-a-sieve in Python but he did not succeed
 Register FAQ Search Today's Posts Mark Forums Read

2018-05-16, 18:51   #1
ONeil

Dec 2017

3608 Posts
"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

 2018-05-17, 21:19 #2 ONeil   Dec 2017 24×3×5 Posts 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.
 2018-05-17, 22:11 #3 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 3×3,163 Posts 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.
2018-05-17, 23:33   #4
ONeil

Dec 2017

24·3·5 Posts

Quote:
 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

2018-05-18, 02:02   #5
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

100101000100012 Posts

Quote:
 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.

 2018-05-18, 19:26 #6 nordi   Dec 2016 2×29 Posts 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.
 2018-05-18, 19:28 #7 rogue     "Mark" Apr 2003 Between here and the 628510 Posts I suggest that you learn a language like C if you want speed.
 2018-05-19, 05:48 #8 LaurV Romulan Interpreter     Jun 2011 Thailand 249F16 Posts @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
2018-05-19, 08:36   #9
ONeil

Dec 2017

24×3×5 Posts

Quote:
 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.

2018-05-19, 09:28   #10
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

10111111010002 Posts

Quote:
 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.

2018-05-19, 11:46   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Shen Information & Answers 4 2017-01-05 04:49 robert44444uk Software 55 2009-08-12 06:39 beyastard Software 55 2009-07-29 12:51 MooooMoo Twin Prime Search 9 2007-01-01 21:13 Clyde83 Hardware 26 2006-08-21 10:33

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

Sat Apr 17 23:27:08 UTC 2021 up 9 days, 18:08, 0 users, load averages: 1.43, 1.58, 1.71