mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Conjectures 'R Us

Reply
 
Thread Tools
Old 2008-06-21, 12:20   #1
Siemelink
 
Siemelink's Avatar
 
Jan 2006
Hungary

22·67 Posts
Default Discussion about CPU time needed and k's remaining

Quote:
Originally Posted by KEP View Post
Have also begun sieving the remaining 6 k's total for Riesel Base 22 and 23 plus Sierpinski Base 23. So is also taking these. They will all be taken to 1 million n or primed.
Nice ambitions! How many cores are you planning to use for this? You must have more than my 10...

Willem.
Siemelink is offline   Reply With Quote
Old 2008-06-21, 15:19   #2
KEP
Quasi Admin Thing
 
KEP's Avatar
 
May 2005

11110100002 Posts
Default

Quote:
Originally Posted by Siemelink View Post
Nice ambitions! How many cores are you planning to use for this? You must have more than my 10...

Willem.
First I'm planning to use my 4 cores on my Quad, and once (if not primed before) I complete the Base 19 sierpinski run on my Dual Core, I'll extend this to 6 cores. Actually I've fast RAMs on the Quad, so it will actually make an even more extensive sieving possible. At the moment, I'm sieving with ~4-6e6 p/sec. And also at the moment 1 k is removed every 1-2 seconds. Out of ~7 million k candidates only ~175,000 is remaining after 3 hours of sieving.

Does anyone know, is it possible to use sr2sieve to sieve different bases? and is it possible to use sr2sieve to sieve both Riesels and Sierpinskis?

If it is, I really think that even better sieving could be carried out
KEP is offline   Reply With Quote
Old 2008-06-24, 07:18   #3
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

2×41×131 Posts
Default

Quote:
Originally Posted by KEP View Post
I'm reserving all 4 k's for Sierpinski base 22, untill 1 million or primed.

KEP!
Quote:
Originally Posted by KEP View Post
Have also begun sieving the remaining 6 k's total for Riesel Base 22 and 23 plus Sierpinski Base 23. So is also taking these. They will all be taken to 1 million n or primed.
Can you do me a favor KEP? Please LLR a candidate that you have remaining around n=1 million and let me know how much time it takes? I suspect it may take 24 hours or more. (Actually, just getting a time per iteration and then multiplying it times the # of iterations to see how long it should take should be sufficient.) Then let me know if you still really intend to take them to n=1M?

This is likely to be 25-50 CPU years (or more) of work and you'd probably want to have 10-20 total quads dedicated to prime searching in order to complete it in a semi-reasonable timeframe...half of them or more to work on this and the other half for other efforts to keep things interesting.

Remember that these are bases 22 and 23 not base 3. Base 3 is a very prime base and the tests are much smaller for the same n-value. I could perhaps see attacking 10 k's on base 3 to n=1M on a single quad (or 6 cores) but that would also likely be several CPU years of work and could still take up to a year on a single quad, depending on how lucky you were to find primes early on.

It's OK if you want to sieve n=100K-1M. That's a very good idea and it helps the project greatly. I just want you to be aware of the boredom factor when LLRing (or PFGWing or Phroting or whatever software you use), which will set in very quickly on these bases especially as you push past n=200K-250K on all k-values remaining.


Thanks,
Gary
gd_barnes is online now   Reply With Quote
Old 2008-06-27, 05:46   #4
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

2·41·131 Posts
Default

Quote:
Originally Posted by KEP View Post
First I'm planning to use my 4 cores on my Quad, and once (if not primed before) I complete the Base 19 sierpinski run on my Dual Core, I'll extend this to 6 cores. Actually I've fast RAMs on the Quad, so it will actually make an even more extensive sieving possible. At the moment, I'm sieving with ~4-6e6 p/sec. And also at the moment 1 k is removed every 1-2 seconds. Out of ~7 million k candidates only ~175,000 is remaining after 3 hours of sieving.

Does anyone know, is it possible to use sr2sieve to sieve different bases? and is it possible to use sr2sieve to sieve both Riesels and Sierpinskis?

If it is, I really think that even better sieving could be carried out

Completing the Sierp base 19 run on just 2 cores to n=100K will likely take 6 months to a year or more with 1539 k's remaining at n=11.12K. Can you give an update on that effort before getting too much into the base 22 and 23 effort?


Thanks,
Gary

Last fiddled with by gd_barnes on 2008-06-27 at 05:50
gd_barnes is online now   Reply With Quote
Old 2008-06-28, 05:37   #5
KEP
Quasi Admin Thing
 
KEP's Avatar
 
May 2005

24·61 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
Completing the Sierp base 19 run on just 2 cores to n=100K will likely take 6 months to a year or more with 1539 k's remaining at n=11.12K. Can you give an update on that effort before getting too much into the base 22 and 23 effort?


Thanks,
Gary
Well sieving is well under way for Base 19. As soon as I complete the k<=250M range for Base 3, I will hand over the remaining candidates and the prooven k's (might be 2-3 weeks more of work). After that I will launch the assault on these remaining k's on both my cores, by splitting the k's remaining in 2 seperate and equaly sized files.

Regarding base 22 and 23, sieving is also really greatly progressing. At the moment you can decide what kind of reservation you would make for me. At least for the next 4 weeks or so, sieving will be the only work done at these Bases. This is the sieve status on the bases:

Riesel Base 22: Sieved to 2645779448941 and less than 34527 k's remain
Riesel Base 23: Sieved to 2841008935111 and less than 29079 k's remain
Sierpinski Base 22: Sieved to 1721884962157 and less than 59047 k's remain
Sierpinski Base 23: Sieved to 2944135041649 and less than 26058 k's remain

Iteration timing: Must wait... but will come

So let me know, what kind of reservation you would like for me to do, sieve/LLR vice? It's fine with me to do just sieving, though it actually makes this kind of prime searching more boring if one only gets to look for factors and never gets the chance to look for primes

KEP!
KEP is offline   Reply With Quote
Old 2008-06-28, 06:54   #6
KEP
Quasi Admin Thing
 
KEP's Avatar
 
May 2005

17208 Posts
Default

@ Gary:

I've given my reservations some thoughts, and here is what I've decided:

I'll sieve for 1 week more on all my Base 22 and Base 23 reservations. Maybe 2 weeks if I have to work in the next weekend. After that I will see if I can complete the verification process of the k<250M for Base 3. The sieve files will be 4, and maybe somone can merge them among different bases and/or Riesel and Sierpinski combined, so it actually works

If I'm going home for the next weekend (living 2 places, thats what actually makes it difficult to give feedback), then I will put all 4 cores from the quad working on the base 19. Hopefully this will bring it much faster down and closer to 0 k's.

Now let me hear what you say Gary... maybe a sieve drive before LLRnet should be considered, especially since I may consider to do some more work on these bases once I wrap the base 19, but that holds for the future to see

Take care everyone.

KEP

Ps. Sieve speed for the Riesel Bases is ~5,000,000 p/sec. For sierpinski base 22 sieve speed is ~3,000,000 p/sec and for Sierpinski base 23 sieve speed is ~5,200,000 p/sec.

Last fiddled with by KEP on 2008-06-28 at 06:56 Reason: Just added some sievespeed measurements
KEP is offline   Reply With Quote
Old 2008-06-28, 09:28   #7
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

2·41·131 Posts
Default

KEP,

Thanks for the response. I had noted in your last status for Riesel base 3 that you were taking it to k=500M. I'll change in now to k=250M.

No, I'm not encouraging you to only sieve. Few people would find only sieving interesting.

I currently have you reserved for the following:

Riesel base 3 to k=250M and n=25K. (A big amount of work)

Sierp base 19 to n=100K for all 1500+ k-values remaining. (A huge amount of work)

Riesel and Sierp bases 22 and 23 to n=1M for all 10 k's remaining. (An astromically enormous amount of work)

I can't dictate what people reserve. I can only attempt to keep efforts moving if possible. I can ask that they continue working on things that they reserve or unreserve part of their reservation if they determine that they reserved too much or if they are no longer interested in them, which you have done. I can also remind them of the amount of work that they are reserving. That's what I'm reminding you about here.

If I were to make a recommendation for these 6 bases for 6 high-speed cores and you would like to do plenty of sieving AND primality testing, I would suggest this:

Keep your Riesel base 3 reservation as is and put 2 cores on it non-stop if possible. This will likely take 4-8 weeks.

Reduce your reservation on Sierp base 19 to n=30K or 35K. I know this seems small but I promise you it will be much more work than you may realize for 1500+ k's for a base that isn't very prime. Initially put 2 cores on it and sieve and LLR as you go as needed. When Riesel base 3 is complete, put its 2 cores on this to get it completed quickly. This would take perhaps 2-3 months by adding the extra 2 cores after 4-8 weeks.

Reduce your reservation on Riesel and Sierp bases 22 and 23 to n=250K. Initially have 2 cores on it for sieving and then LLRing as needed. When Sierp base 19 is complete, move all 4 cores over to it for a total of 6. This will still be a very large amount of work. I have no idea how long this will take. I will speculate 4-8 months by adding the extra 4 cores after 2-3 months. It all depends on how quickly the 10 k's drop but I will guess that they will be very slow to drop.

Reference bases 22 and 23, on my reservation for Sierp base 12 using your sieved file, it has taken me 10 days to process n=129K-160K on one high-speed core but it is slowing greatly. My estimated time to n=250K (the limit of your sieved file) on one core is ~3 months. Tests at n=160K are coming in at 2200 secs. or about 37 mins.! Extrapolating without an actual test, I can say that it will take 9000-10000 secs. or 2.5-3 hours per test at n=250K!! And that's only base 12!

In suggesting this, I'm not saying that you should reduce the range of what you are sieving. Many people, Jean Penne is our main one, sieve much larger ranges then they intend to test to help out the effort. When complete with Sierp base 19, leave your n=30K or 35K to 100K file for the team and when complete with Riesel and Sierp bases 22 and 23, leave your n=250K-1M file for the team. Even when you complete the above, I'm sure a large portion if not all of them will still be available and besides, you may find a more interesting effort at that point.


Gary

Last fiddled with by gd_barnes on 2008-06-28 at 09:34
gd_barnes is online now   Reply With Quote
Old 2008-06-28, 09:55   #8
KEP
Quasi Admin Thing
 
KEP's Avatar
 
May 2005

24·61 Posts
Default

@Gary:

First a timing for k=68 n=999991 for sierpinski base 23: ~44 ms or 199,035.232 seconds per test. So at now a maximum completion time of: 31,447,566,656 seconds. However sieving is moving 9 k's an hour per core still, so huge amount of work is still saved by doing sieving.

However here is some comments to your plan (which I really liked and may stick to):

1. Keep my reserved range for Riesel Base 3 for k<=500M, since it has been PRP tested to n<=500 and verification of the PRPs will start monday on both the 250M k ranges and sieving of the Base 19 will be haulted for now.

2. Next friday I will bring all my 4 cores on the quad working on each ~385 k's. This will mean that by next friday I'll stop sieving on the bases 22 and 23. With the current speed more than a thousand candidates should be factored.

3. In 4-6 weeks at least the Base 19 should be completed to n<=100K and hopefully the Base 3 Riesel will have been completed to n<=25K, so at this time I should be able to put six cores working on these 4 bases. When that happens I plan to sieve a great deal further (hopefully to 25T) which is about 10 weeks of sieving time. After that I intend to split the sieved files up in pieces which can keep my 6 cores run individually for 6 weeks without running dry.

The above plan I hope to see greatly progressed around christmas, and if any of the base 22 and base 23 k's should remain, I figure that about that time the k/n pairs has gotten so high that further sieving might be nescessary for the remaining k's before a public release...

Anyway hope this is not to long an outcast, and looks forward to be able to send you a lot of primes every week untill the Base 19 is completed. Also I hope that it is OK with you if I keep my reservations for now. Maybe later on if the task of running the bases 22 and 23 gets to scary or turns out to be to hard to complete, of course we can then discuss a public release.

Also sorry if I sounded agrevated, but I really believed that I could get somewhere and I also thinks if I put 4-6 cores on sieving the high bases, no problems with getting somewhere will in fact be seen

Take care my friend!

Kenneth!
KEP is offline   Reply With Quote
Old 2008-06-28, 15:30   #9
michaf
 
michaf's Avatar
 
Jan 2005

47910 Posts
Default

As for an idea how long it all takes:

Riesel base 31, there are 9 k's left.
On 1 core, it took 2 months (minus 2 days) to go from n=68133 to 78661!

I haven't checked whether I'll be hitting another FFT-switchover, but if so, timings will be much worse after that happens. If nothing interesting happens (primes :)) I'll have about 5 months of work only for 9 k's to only 100k!

and... 31,447,566,656 seconds is about 1000 CPU-years...!!
(ok... that is the MAX time :) )

anyways, I hope you can turn up your muscles and get it done with :)
(Finding primes early on will most certainly help a lot!)

Last fiddled with by michaf on 2008-06-28 at 15:31
michaf is offline   Reply With Quote
Old 2008-06-28, 16:12   #10
KEP
Quasi Admin Thing
 
KEP's Avatar
 
May 2005

11110100002 Posts
Default

Quote:
Originally Posted by michaf View Post
As for an idea how long it all takes:

Riesel base 31, there are 9 k's left.
On 1 core, it took 2 months (minus 2 days) to go from n=68133 to 78661!

I haven't checked whether I'll be hitting another FFT-switchover, but if so, timings will be much worse after that happens. If nothing interesting happens (primes :)) I'll have about 5 months of work only for 9 k's to only 100k!

and... 31,447,566,656 seconds is about 1000 CPU-years...!!
(ok... that is the MAX time :) )

anyways, I hope you can turn up your muscles and get it done with :)
(Finding primes early on will most certainly help a lot!)
Thanks. But a great way to really get somewhere is to keep sieving untill at least 25 T and maybe to 100 T, that should reduce the ~148,000 candidates remaining to ~100,000 candidates. But still it will be 4-6 weeks before I get to some serious work again on these bases, according to my previously plan, so maybe as we get closer we can discuss again how to get even further in even faster time. I expect to be around 5-6T p for Riesel bases and sierpinski base 23 and maybe around 3-4T p for Sierpinski base 22, on the coming friday, when in fact I'm going to pause these bases and launch the assault on the base 19 which is now taken to n<=11209 and 1 prime is waiting to be reported

Thank you!

KEP
KEP is offline   Reply With Quote
Old 2008-06-28, 20:57   #11
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

2·41·131 Posts
Default

Quote:
Originally Posted by KEP View Post
@Gary:

First a timing for k=68 n=999991 for sierpinski base 23: ~44 ms or 199,035.232 seconds per test. So at now a maximum completion time of: 31,447,566,656 seconds. However sieving is moving 9 k's an hour per core still, so huge amount of work is still saved by doing sieving.

However here is some comments to your plan (which I really liked and may stick to):

1. Keep my reserved range for Riesel Base 3 for k<=500M, since it has been PRP tested to n<=500 and verification of the PRPs will start monday on both the 250M k ranges and sieving of the Base 19 will be haulted for now.

2. Next friday I will bring all my 4 cores on the quad working on each ~385 k's. This will mean that by next friday I'll stop sieving on the bases 22 and 23. With the current speed more than a thousand candidates should be factored.

3. In 4-6 weeks at least the Base 19 should be completed to n<=100K and hopefully the Base 3 Riesel will have been completed to n<=25K, so at this time I should be able to put six cores working on these 4 bases. When that happens I plan to sieve a great deal further (hopefully to 25T) which is about 10 weeks of sieving time. After that I intend to split the sieved files up in pieces which can keep my 6 cores run individually for 6 weeks without running dry.

The above plan I hope to see greatly progressed around christmas, and if any of the base 22 and base 23 k's should remain, I figure that about that time the k/n pairs has gotten so high that further sieving might be nescessary for the remaining k's before a public release...

Anyway hope this is not to long an outcast, and looks forward to be able to send you a lot of primes every week untill the Base 19 is completed. Also I hope that it is OK with you if I keep my reservations for now. Maybe later on if the task of running the bases 22 and 23 gets to scary or turns out to be to hard to complete, of course we can then discuss a public release.

Also sorry if I sounded agrevated, but I really believed that I could get somewhere and I also thinks if I put 4-6 cores on sieving the high bases, no problems with getting somewhere will in fact be seen

Take care my friend!

Kenneth!
I'm still not sure you're getting what I'm stating here on Sierp base 19 anyway. How many cores will you have on that base in order to complete it to n=100K in 4-6 weeks? I'm talking both sieving and primality testing. To finish this in 4-6 weeks will likely take several quads. Let me put it this way, if I put my 6 quads full time non-stop on Sierp base 19, I MIGHT be able to finish it to n=100K in 4-6 weeks, perhaps a little less but not much less. If you have one full quad on it, that's likely 4-5 months of work. If only 2 cores, then double that. Sure many k's will be eliminated as you go but a good majority of them will still remain and testing near n=100K on Sierp base 19 will take a long time for each candidate.

On sieving, you're mistaking the elimination of candidates as substantially reducing the overall testing time of the entire n-range. It does not if you're sieving optimally because when estimating, you have to account for sieving and LLRing time. It only saves time at the n-ranges in which LLRing takes longer than the removal rate of your sieving. If you're sieving optimally, the sieving removal rate SHOULD be slower than the lower n-range testing level and faster than the higher n-range testing level. That is for n=100K, your testing time might be 1800 secs. but your optimal removal rate might be 3500 secs. for the range of n=100K-200K because you need to sieve until the removal rate is the same of an LLR-test at 70% of the n-range that you are breaking off for primality testing (would be n=170K for n=100K-200K).

I may have stated this before but the optimal thing to do in sieving is to sieve until the removal rate is about the same as the primality testing time at 70% of the n-range but break off sieving pieces in powers of 2 n-ranges for primality testing. So for n=100K-1M, you'll LLR a candidate at n=170K to get a testing time, break off n=100K-200K from sieving for primality testing when the sieve rate is about the testing time, then LLR a candidate at n=340K to get a testing time, break off n=200K-400K when the sieve rate is about that testing time, LLR a candidate at n=680K, break off n=400K-800K when the sieve rate is about that testing time, LLR a candidate at n=940K, and finally sieve n=800K-1M until the sieve rate is about that testing time. In other words, you don't continue to sieve the entire n-range the whole time.

Technically, the more pieces you break off, the more efficient it is CPU-wise. It's just a matter of how much you want to mess with it. But the efficiency begins to drops greatly if you don't break it off at least in powers of 2 n-ranges. By powers of 2, I mean your lower candidate (100K in this case) times 2^q.

It sounds like you'll be reducing your reservation at some point on the bases 22 and 23 and providing a sieved file for the team for the n-ranges above that which you test. Great! At n=~1M on base 23, that's over 2 days to test! One more thing that I'll add on that: I would be surprised if we found primes for more than 6 out of the 10 k's remaining on those bases to n=1M! It might only be 3-5 of them. These high bases and n-ranges on bases that are not very prime are TOUGH to find primes for! Many of these conjectures I do not expect to be proven in our lifetimes! (believe it!) :-)

I have a suggestion for you to get a better rough estimate of the time it will take to LLR Sierp base 19. Find a candidate that is at about 60% of your n-range. So for n=10K-100K, that would be n=64K. Then LLR that candidate. Now multiple that time by the total number of candidates you have remaining in your sieved file. THAT should be close to the total time it will take you to LLR the entire n-range. Of course we can probably reduce that by 10-20% because k-values can be removed as primes are found. Also, of course further sieving reduces that LLRing time but you're taking time to sieve also. If you sieve in the optimal manner above, you should get close to the most efficient combination of sieving and LLRing.

If you want to LLR an n=64K candidate and provide me with the time it takes and also let me know the number of candidates remaining in your n=10K-100K (or n=11.2K-100K or whatever) sieved file, then perhaps I can give you a better idea of how to estimate the level of resources needed or how long it will take with your current allocated resources to complete Sierp base 19 to n=100K. At that point, we might be able to get a good idea of how high you'd like to take bases 19, 22, and 23.


Gary

Last fiddled with by gd_barnes on 2008-06-28 at 21:06
gd_barnes is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Conjectures with one k remaining rogue Conjectures 'R Us 109 2017-04-29 01:28
Estimating time needed for GNFS CRGreathouse Factoring 16 2014-03-10 03:40
Estimating time needed for GNFS CRGreathouse Factoring 0 2014-03-02 04:18
Predicting the needed time for high n-values? Rincewind Sierpinski/Riesel Base 5 4 2009-06-11 12:24
Time needed to factor a 150 digit number ladderbook Factoring 14 2008-11-27 13:02

All times are UTC. The time now is 08:25.


Sat May 28 08:25:59 UTC 2022 up 44 days, 6:27, 0 users, load averages: 1.32, 1.49, 1.54

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.

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