mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Sierpinski Project

Reply
 
Thread Tools
Old 2005-07-07, 01:28   #1
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

33F16 Posts
Thumbs up Combine sieving with SoB?

Hi there!

Currently, over at SoB, there is a big effort on the way to sieve all candidates with n < 50M (instead of n < 20M), as this is supposed to be the optimal sieving range.

They will soon reach 100T with a recheck (991 < n < 50M) and it could be possible to combine PSP and SoB searches afterwards, doing both to 50M.

The corresponding thread:
http://www.free-dc.org/forum/showthr...&threadid=9663
Mystwalker is offline   Reply With Quote
Old 2005-07-07, 04:31   #2
Citrix
 
Citrix's Avatar
 
Jun 2003

22·397 Posts
Default

Give me a day to do some calculations and Riselsieve can also be included in the sieve the program will work as if all of RS's k's were +1.



Citrix
Citrix is offline   Reply With Quote
Old 2005-07-07, 04:34   #3
hhh
 
hhh's Avatar
 
Jun 2005

373 Posts
Default

For everybody who is to lazy to read all the thread, in a few words the facts.

SoB has pushed first pass sieve near to 2^50, which is expected to be reached next spring. That's why SoB started a resieving effort with a larger dat, for 991<n<50M.(instead of 20M). This one will soon reach 100T. After reaching 100T, SoB will continue on firstpass sieving and continue secondpass when 2^50 is reached.
In order to use at its best the benefits of large scale, I brought up the idea to merge the sieve dat's of SoB and PSP. The sieve speed would go down, but of course there would be an overall benefit.
Now, it's not enough to put the two dat's together, they should have the same same limit of n, too. So, if PSP would like to do such a merger, the PSP-50M-dat would have to be sieved until a reasonable bound in order to reduce it's size. Perhaps until 40T. For this, there is 9 months of time, until SoB retakes secondpass sieving. Then, we could take over together.

Of course, even though theoretically it's a good idea, there are arguments not to do it. For example, it is not obvious that PSP wants already to sieve so far (50M), given the fact that the PRP-testing is only at 2M.

But somehow, it's a now or never situation, because there will not be another occasion like this (resieve, limit of proth, coincidence of current work levels) so soon.
Looking forward to read your opinions, Yours H.
hhh is offline   Reply With Quote
Old 2005-07-07, 15:22   #4
VJS
 
VJS's Avatar
 
Dec 2004

13×23 Posts
Default

I would also like to point out that with the current implementation of proth. A dat size of 53M is the most efficient with respect to time vs work done.

53M is optimal but an odd size number. There is a flat spot in the optimal dat size curve between about 45-55M, any higher than 55M the efficiency drops dramatically. Anything smaller than 45M your out of the optimal size.

What this means in a nutshell...

Differences between 20M (your dat and SoB's older dat) vs a dat size of 50M. Well 50M dat is 2.5x larger sure... Takes about 50% more memory once you reduce the size (40T). However it is only between 10-20% slower than the 20M dat.

So theortically 250% x 85% = ~212% more work done per unit time.

Second adding k's isn't that bad on the sieve speed. Doubling the number of k's doesn't half the sieve speed. There is also the issue that by combining k's more mod's will be shared etc...

The major problem is that you would have to sieve everything from 20M<n<50M upto at least 18T (2^44). But 40T would be great. You could skip 40T to 100T with the 20M<n<50M dat people would probably do it later.

_________________________

Not sure how you guys feel about it since your <2M on first pass.
VJS is offline   Reply With Quote
Old 2005-07-07, 18:42   #5
ltd
 
ltd's Avatar
 
Apr 2003

77210 Posts
Default

I would like to see the merge of ranges if possible.
To be honest it would help PSP much more then it would help SOB due to the
fact that you have a lot of siever over there compared to our sieve effort at the moment. If you give me time till end of next week i can create a sieve file
1006 to 50Mil.

I would push the PSP sieving of the low ranges with all the power i have to have removed as many factors as possible if we decide to merge.

Edit:

I hope that i can hold the schedule for creating the file. That depends alot on
the installation i have to do at a customer site this weekend (friday to monday :( ). If i have to stay there longer then monday evening i think it will take longer as there is lots of work on my desk.

Lars

Last fiddled with by ltd on 2005-07-07 at 19:08
ltd is offline   Reply With Quote
Old 2005-07-07, 19:41   #6
VJS
 
VJS's Avatar
 
Dec 2004

12B16 Posts
Default

You have alot of time to do so, it's more of a think project currently. It will take SoB at least another 6 months if not more to finish secondpass to 100T and first pass to the limit of proth.

The major point is getting the dat done, and the first... 3T is a killer ...

With a 20M<n<50M it might not be too bad.

Second I don't mean to be a spoil sport or anything, but alot of people are jumping on the prime bandwagons lately. Different bases, k's, +/1, twins etc... it seems like its easy to do alot of prp testing find primes upto n=100K etc and stop, expecting others to continue. I site a projects lack of sieving for other peoples prp testing as evidence... not that any one project is better than another. But sieving to 50M is a comitment to a project, that's all I wanted to point out. PSP has been doing a good job of sieving thus far and p=100T for n<2M is not bad at all.

Will it happen, I don't know. But who is to say what will happen when SoB reaches the limit of proth. If there is any sieve project which should be combined with the SoB sieve project it should be PSP, IMHO.
VJS is offline   Reply With Quote
Old 2005-07-07, 19:59   #7
VJS
 
VJS's Avatar
 
Dec 2004

4538 Posts
Default

Alot one more thing...

http://www.free-dc.org/forum/showthr...&threadid=8014

This thread is the development of the 991-50M sieve effort, worth a read IMHO since I was one of the people who started it.

Some of the earlier post were just plain wrong but I didn't have the data. The graphs will be roughly the same. There is good graph on the second page showing factor density drop off. Around 18T as I had stated earlier.

I'd also like to add simply creating the dat and sieving out the first T is a start. Also don't forget to use newpgen or some other program for the first ?? 1G ??? or 64K ??? can't remember. Proth has a minimum value to which it will sieve, 1G though the interface I think 64K if you fudge a pmin= manually. Alot of factors exist below the 1G of course.

If you need some advice don't hesitate to ask here, I can tell you only what I know from experience using the client.

Last fiddled with by VJS on 2005-07-07 at 20:00
VJS is offline   Reply With Quote
Old 2005-07-08, 03:03   #8
hhh
 
hhh's Avatar
 
Jun 2005

373 Posts
Default

As soon as you are ready, PM me and I will give you and email adress that can take the dat or so; I would be pleased to take a chunk.
H.
hhh is offline   Reply With Quote
Old 2005-07-08, 06:24   #9
Citrix
 
Citrix's Avatar
 
Jun 2003

22·397 Posts
Default

Well here is the mathematical calcualtions I did

Running time of prothsieve= *****

(sqrt(sum of weight of all k's) + #of k's )* constant * sqrt(range (max-min))

Using this formula the time it would take SOB alone and PSP alone will be 2.4X compared to 1.7 X if PSP and SOB merged.

Clearly, it would be better if the 2 project's sieving efforts merged. But if you consider having PSP find all the primes upto 10 million and then sieve upto 50 million the time would be 2.0 X. So it makes sense logically to merge the project's sieving efforts.

At the same time it makes alot of sense to merge the rieselsieve and PSP's sieiving effort upto 20M.


But the question arises that does PSP want to go to 50M? The answer to this is yes, but with the current computing power it seems almost a fantasy for PSP to reach 50 M in the near future. So, unless more people contribute to the PRP section it will be a waste of computing time for the helpful SOB sievers, Since PSP might never use those sieve ranges (20M to 50M)



**** irrespective of whether k's are +1 or -1
constant depends on your machine


Hopefully, the above makes sense!
Citrix

Last fiddled with by Citrix on 2005-07-08 at 06:30
Citrix is offline   Reply With Quote
Old 2005-07-08, 09:32   #10
hhh
 
hhh's Avatar
 
Jun 2005

373 Posts
Default

Citrix, the above makes sense, I think, but what is your point?, do you want it or not?
IMHO, it is true that SoB is behind in sieving, but this is no reason not to help PSP. One project is behind, the other one ahead, no big deal. Anyway, if one day one project is finished, people will probably not retire, but head over for an other.

As for rieselsieve, when you look at the discussion on the SoB-site, there seem to be - at least - obstacles. I'm not in the maths, and I have even no idea how the siever works in detail, but these obstacles seem to me (from the discussion), not trivial. If you can solve them, and write a siever that can take rieselsieve into account, I would even opt for taking rieselsieve, too. PSP, SoB, and Riesel would of course be even more efficient.
That's BTW why I think we should sit back, think over all these things very well, and then make them good, and once and for all.

H.
hhh is offline   Reply With Quote
Old 2005-07-08, 10:30   #11
thommy
 

354810 Posts
Default

OK, here is a negative thought.
PSP is more or less just a fun project. What is so special about a prime sierpinski? Even if it is the lowest. Thats like who was the first afro american on the moon. Its just not important, and most people do not care.
SoB seems more worthy for me.

What is when the comes a new project testing all k's that are multiples of 15 and 8 mod 25 or whatever just some new k values for form k*2^n+1. Would you like combining that one too in your sieving effort?

But i dont sieve anyway, so thats just my opinion.
  Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
64-bit sieving paleseptember Five or Bust - The Dual Sierpinski Problem 16 2009-01-25 20:26
Should a diskless node run it's own ecm program or should I combine them somehow? jasong GMP-ECM 1 2006-02-24 08:34
Sieving ValerieVonck Math 9 2005-08-05 22:31
Sieving OmbooHankvald Prime Sierpinski Project 4 2005-06-30 07:51

All times are UTC. The time now is 06:37.


Tue Jul 5 06:37:46 UTC 2022 up 82 days, 4:39, 0 users, load averages: 1.69, 1.54, 1.43

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔