Results 1 to 36 of 36

Thread: how long untill was pass seive client limit?

  1. #1

    how long until we pass the seive client limit?

    its now 1-july-2005

    i guesstimated we are increasing the sieve range by 30T / month

    which puts us over 850T come october and into 1000T+ by december.

    nope wait.. missed the 900T-994T range.. so say 1000T by april 2006


    well that destroys my argument.. i was going to say well be past the limit of 2^50 in 12 months. but unless someone can refine my figures its more like 30 months


    as an aside.. i would be interested to hear if anyone had some substatiated figures about sieveing speed. maybe a graph of the current seive point from Mike's page http://www.aooq73.dsl.pipex.com/scores_p.htm
    Last edited by vjs; 07-01-2005 at 06:04 PM.

  2. #2
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    Date Gaps size Daily Ch.
    Mon 23-Feb-2004 09:09 788947.35G n.m.
    Mon 23-Feb-2004 15:10 786509.06G 9726.1 G
    Tue 24-Feb-2004 09:10 785937.58G 762 G
    Wed 25-Feb-2004 09:08 785156.69G 782 G
    Thu 26-Feb-2004 09:08 784693.75G 462.9 G
    Fri 27-Feb-2004 09:08 783922.15G 771.6 G
    Mon 01-Mar-2004 15:10 780271.45G 1122.8 G
    Tue 02-Mar-2004 09:08 779423.51G 1132.7 G
    Wed 03-Mar-2004 09:08 778763.82G 659.7 G
    Thu 04-Mar-2004 09:07 778333.33G 430.8 G
    Fri 05-Mar-2004 15:08 776337.70G 1595.6 G
    Mon 08-Mar-2004 09:08 774069.63G 824.8 G
    Tue 09-Mar-2004 09:08 773321.55G 748.1 G
    Wed 10-Mar-2004 09:09 772679.94G 641.2 G
    Thu 11-Mar-2004 09:10 771885.72G 793.7 G
    Fri 12-Mar-2004 09:08 771455.37G 430.9 G
    Mon 15-Mar-2004 09:14 769242.42G 736.6 G
    Tue 16-Mar-2004 09:09 767243.89G 2005.5 G
    Wed 17-Mar-2004 09:08 766501.69G 742.7 G
    Thu 18-Mar-2004 09:09 765418.62G 1082.3 G
    Fri 19-Mar-2004 09:08 764713.12G 706 G
    Mon 22-Mar-2004 09:08 763785.43G 309.2 G
    Tue 23-Mar-2004 09:10 763246.51G 538.2 G
    Thu 25-Mar-2004 09:07 761989.14G 629.3 G
    Fri 26-Mar-2004 09:11 761488.63G 499.1 G
    Mon 29-Mar-2004 15:14 759103.44G 733.4 G
    Wed 31-Mar-2004 09:08 757852.13G 716.7 G
    Thu 01-Apr-2004 09:09 756291.02G 1560 G
    Fri 02-Apr-2004 09:08 754761.51G 1530.6 G
    Mon 05-Apr-2004 09:36 753431.46G 440.5 G
    Tue 06-Apr-2004 09:08 752756.68G 688.2 G
    Thu 08-Apr-2004 09:13 749991.93G 1380 G
    Tue 13-Apr-2004 09:08 747738.00G 451.1 G
    Wed 14-Apr-2004 09:07 746958.10G 780.4 G
    Fri 16-Apr-2004 09:23 746482.54G 236.5 G
    Mon 19-Apr-2004 09:09 745085.33G 467.3 G
    Wed 21-Apr-2004 09:09 744249.83G 417.8 G
    Mon 26-Apr-2004 09:08 738558.10G 1138.5 G
    Tue 27-Apr-2004 09:08 736866.55G 1691.5 G
    Fri 30-Apr-2004 09:08 735069.67G 599 G
    Tue 04-May-2004 09:08 731752.57G 829.3 G
    Wed 05-May-2004 09:08 729978.36G 1774.2 G
    Mon 10-May-2004 15:08 726263.58G 707.6 G
    Fri 14-May-2004 03:09 722679.92G 1023.7 G
    Mon 17-May-2004 09:08 720128.59G 785.2 G
    Thu 20-May-2004 09:08 718696.38G 477.4 G
    Tue 25-May-2004 09:08 714982.66G 742.7 G
    Thu 27-May-2004 09:08 713285.51G 848.6 G
    Wed 02-Jun-2004 09:08 710088.77G 532.8 G
    Fri 04-Jun-2004 09:08 709381.35G 353.7 G
    Wed 11-Aug-2004 09:26 631038.29G 1151.9 G
    Wed 15-Sep-2004 09:09 590425.70G 1160.8 G
    Tue 21-Sep-2004 15:09 580606.80G 1571 G
    Wed 29-Sep-2004 03:10 568653.19G 1593.7 G
    Wed 06-Oct-2004 09:09 558185.93G 1443.9 G
    Wed 03-Nov-2004 09:10 524936.09G 1187.5 G
    Tue 09-Nov-2004 03:13 520958.57G 691.5 G
    Mon 22-Nov-2004 09:10 498766.02G 1675.2 G
    Mon 29-Nov-2004 21:23 487705.63G 1472.9 G
    Tue 04-Jan-2005 09:38 437550.74G 1412.4 G
    Mon 10-Jan-2005 03:14 428081.56G 1651.6 G
    Mon 17-Jan-2005 09:11 414273.96G 1905 G
    Mon 24-Jan-2005 09:11 401024.46G 1892.8 G
    Tue 22-Mar-2005 09:13 292128.53G 1910.4 G
    Mon 28-Mar-2005 03:14 281373.62G 1870.2 G
    Wed 06-Apr-2005 15:13 265635.87G 1656.7 G
    Wed 13-Apr-2005 03:13 254784.45G 1669.4 G
    Mon 18-Apr-2005 09:13 247279.85G 1429.4 G
    Wed 04-May-2005 09:13 228616.29G 1166.5 G
    Tue 10-May-2005 09:13 221015.76G 1266.8 G
    Mon 23-May-2005 09:14 209273.04G 903.2 G
    Fri 03-Jun-2005 09:15 201763.03G 682.7 G
    Wed 29-Jun-2005 15:14 176950.92G 945.2 G

  3. #3
    Some calculations of the interiour of the envelope style: I counted 20 people sieving from time to time or all the time. If they have in average one machine with 300kp/s 24H online per day, every single one can finish a 1000G range in a month, so we have perhaps 1000G per Day, well that's what Nuri said.
    But than I don't agree anymore. I counted 270000 G of unreserved stuff until 2^50. That means we will have reservations for all that in one year. I did not check my lookup, correct me if I'm wrong.
    This is without considering that we are restarting over with the large dat which takes power, too.
    But, in one year, firstpass will only be at 10.5M meaning that this is not yet so far; we have a lot of time to catch up the first pass sieving. This is convincing me to continue there, first, as only this is saving work right now. (This is until I change my mind, because I want to see a lot of factors or so).

    I don't know if it is true, but one of the problems of the project could become frustration. In this sense, Sieving is good, especially with the large dat file, because you are again finding something every few days.
    oops sorry no negative influence... did I say anything?

  4. #4
    Thanks for the data Nuri.

    it support the 1000T /day estimate.

    if hhh is correct with the 270000G count then thats 270 days or 9 months

    i guess you can then allow for redo the first 750T with the large n .dat (which i know is underway) which gives another 600 days.

    so i think to sum up.. we dont need to worry about any of this until next year at least (2006).

    at least i dont fell im . i can sit back and

  5. #5
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    I don't see anything negative here???

    It's sort of funny that you guys are talking about that. Everytime I reserve a range I keep wondering what's the best approach. Either to continue with low p or finish the high p first.

    Every range done with the 991-50M is a range that doesn't have to be redone.

    In either respect using the 991-50M dat is really the only option in my opinion, setting range aside.

  6. #6
    In the resieve attempt, there are accepted only ranges of 1000 G, in order to keep things simple, right? So, one argument for the choice is if you have enough power to finish a range. People with less power should do first pass sieving.
    But: the day will come when 2^50 is reached. What will these people do then? No problem, one reserves a 'confusion'range where smaller chunks are accepted as well.
    Well, in fact, me too I think that the discussion turn around nothing in fact. Let's sieve and see what happens.

    Shoelace, my apologies to have quoted you as Nuri. I thought he had started the thread.

  7. #7
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    I personally am planning to continue with regular sieve ranges (with 991-50m dat) until 2^50, and start resieve ranges with 991-50m dat thereafter.

  8. #8
    Same here. Once I get back, I'm going to do the 50m sieving on first pass.

  9. #9
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    HHH,

    Part of the reason why we are sieving in 1T chuncks is as you had stated is to make record keeping easy.

    But also those low-p ranges have alot of factors in them so getting them done in 1T chuncks from the begining was important, it helped reduce the dat files size ALOT and we wanted to insure that people would get them done in a reasonable time frame.

    Why?

    If you look at mikes pages, particularly this one http://www.aooq73.dsl.pipex.com/scores_p.htm

    And even further this table...

    Code:
     2^40 - 2^41 (   1T -    2T)             0.00%                0.00%            18387/18387
     2^41 - 2^42 (   2T -    4T)             0.00%                0.00%            17343/17343
     2^42 - 2^43 (   4T -    9T)             0.00%                0.00%            16275/16275
     2^43 - 2^44 (   9T -   18T)             0.00%                0.00%            15617/15617
     2^44 - 2^45 (  18T -   35T)             0.00%                0.00%            14907/14907
     2^45 - 2^46 (  35T -   70T)             0.00%                0.00%            14108/14108
     2^46 - 2^47 (  70T -  141T)             0.00%                0.00%            13784/13784
     2^47 - 2^48 ( 141T -  281T)             0.00%                0.00%            11750/11750
     2^48 - 2^49 ( 281T -  563T)             1.20%                1.01%            10926/11038
     2^49 - 2^50 ( 563T - 1126T)            51.07%               46.71%             5594/10498
     2^50 - 2^51 (1126T - 2252T)            99.72%               99.09%               96/10498
     2^51 - 2^52 (2252T - 4504T)            99.96%               99.25%               79/10498
    You can see that sieving 1T at a particular p level makes a difference with how many factors are found. (THIS IS THE HEART OF FACTOR DENSITY)

    The number of factors found are based strongly on %n of p=2^n sieved for a range.

    O.K. so what am I talking about????

    Each line of the above table represent a sieve range divided up into p=2^n, for example from n=47-48 (i.e. 141T-281T) we found 11750 factors or ~83 factors per 1T sieved. From 1T to 2T the same size range we would have recieved 18387 factors per 1T sieved.

    Thus far one can consider that we have sieved 991-50M upto about 70T so about 46n worth. And we have 4n remaining, the 1-20M dat has been sieve to >49.5n and less than 0.5n to go.

    What this basically means is that we could skip all p from 100T to current and not miss alot of factors, we would then later returning to these with when n approaches 20M. Or we run out of ranges with proth.

  10. #10
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    I think we will be able to finish regular sieve (preferably most of which will be with 991-50m dat) to 2^50 AND also resieve up to 2^50 before PRP reaches 20m. This is a timeframe of at least three years from now (unless we find a sieve or PRP client that is a couple of times faster, which would be cool of course). So, nothing to worry about yet.

  11. #11
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    I'd have to agree with you Nuri, the major push for doing the low-p ranges was to reduce the dat size and memory requirements so what we could use it for normal sieving. This effort has continued for quite some time now since we were finding missed factors at the low p.

    I will personally continue with the low-p until everything less than 100T is complete. However I have returned some of my slower machines to the high-p ranges and will probably migrate a few more in the future.

    It's also very tough not to work on that 300K score which should happen somewhere around 9.9-10.1M with a sieve p less than 990T. I'm going to grab that 999G range between you and death to fill the hole. I may also round out Joe's range.

    On that note, Joe has the best candidate thus far.

    Joe_O 999.029T 21181 9950372 309105.511
    Pixl97 1122.765T 33661 10010880 351627.875
    Death 996.127T 55459 10243894 326659.337

    Although HC-Grove has found a bunch with p-1... all of the following have enough p to score 300K.

    10223 9987017
    55459 9989014
    19249 9990338
    24737 9992911
    33661 9998160
    55459 9999046
    Last edited by vjs; 07-05-2005 at 05:33 PM.

  12. #12
    Member
    Join Date
    Dec 2002
    Location
    new york
    Posts
    76

    sieving speed...very simple

    as an aside.. i would be interested to hear if anyone had some substatiated figures about sieveing speed.

    I calculated two years ago that sieving should be extended to 2P before ANY further proth testing is performed. Then I left the project. Basically it was just speed of proth vs. speed of sieve in terms of candidates removed per day, per machine.

    I believe the method I used was to sieve a small range at 500T and see how many results I was getting. If I was getting more than one per day, then it was still faster than proth testing.

    Proth testing is also slowing down, which is probably why I extended my original estimate of 500T to 2P.

  13. #13
    yes but finding primes is the goal. Also many of the factors we find will not be used ... ever... we have only gotten to 10 million with PRP and half of the K values have been eliminated. Therefore much more tha nhalf of the factors that would have been found by sieving to such a deep depth would have been useless, not to mention that sieve was much slower back then and we would not have nearly as many participants if not for the publicity created by finding primes. Now if sieving were really going to change the completion time of the project (say if the proposed new supersiever were completed) then i would totally support more work being dedicated to sieving but i would hate to see PRP testing stopped. A steady flow of primes is what keep people coming back ot this project, people want to find primes... That is the goal.

  14. #14
    Member
    Join Date
    Dec 2002
    Location
    new york
    Posts
    76
    Thank you for the reply, I see your point about wasted sieves. I don't believe that PRP should be stopped indefinitely. What I am saying is, if you have a bunch of people doing PRP blindly, then we have a responsibility to tune their work for them aka sieving. Part of what you are saying is that we should run PRP tests "because it looks good." That may be true, the one year gap between primes was a little scary. But...could it have been done faster with more sieving? Or was 1 year actually fast because you *were* sieving?

    The last three primes were found at 1.3M, 5M, and 7.8M. I think we can agree that any factors below 10M are valid for the near future, factors more towards 50M may be useless. I will take this into account. And the double-check prime at 3M is something I have to look into.

  15. #15
    (hope this isn't totally OT but I feel rant mode /on...)
    Originally posted by Keroberts1
    and we would not have nearly as many participants if not for the publicity created by finding primes........A steady flow of primes is what keep people coming back ot this project, people want to find primes... That is the goal.
    Yes, I can testify on the validity of this claim! In fact, the entire TeamRetro team (which as you may have noticed is one of the top teams and has had a pretty much stable throughput for quite some time) came to be because it's leader, Cowering, noticed the surge of primes around 1m and became confident that this is a meaningful project that will sometime actually finish and produce something useful. After that, he had the means to gather other people like me and form a strong team, which may have not been here if this hadn't occured! Take this as a fact from an early member of TR, I know the circumstances that led to the formation of the team firsthand!
    Also, people can and will be disappointed and leave if no apparent progress is made for a long time, I suppose everyone lives with a little hope inside them that the next prime is just aroung the corner

    I have personally tried everything but P-1 factoring (since, having an Athlon XP, it was more suited to anything else but that), having taken a shot at sieving, first pass and second pass tests, according to my whim or whatever made more sense for me at the relevant time. This was always part of the fun, being dictated around or treated like a mindless sheep isn't always the best way, even if mathematical formulas say so! Fundamentally, the project has to do with the people running it and not only the solid maths and there are always different groups that have different interests.
    Some I can think of after reading the forums for quite some time (take this on the "slighly joking" side) :
    -Math lovers : they will always look for the best formulas to improve efficiency and they seem to be the most vocal in the forums. They will be the ones to come up with the most ideas/suggestions, form the core of the project but can't accomplish much without the other groups aboard, as they are only a (quite vocal!) minority.
    -Stats junkies: they are in it for the stats and they don't care at all what is more efficient for the project, only what gives more points. They'll post in the forums only to complain whenever their speed drops (passing a FFT boundary, switching to 2nd pass with a flawed speed unit...) but they still provide a major power to the project since they are the most likely to dedicate a farm of computers to it and see their stats climb skyhigh!
    -"Hopers": they are in it for the hope of finding a prime and becoming kind of famous. Their voice is heard very seldom, they tend to increase after a new glorious find and decrease at times of drought! If they stick around, they usually migrate to another category, the "hoper" is not a permanent status.
    -"Helpers": they try to go where they'll help. They adopt DC projects because they like the idea of putting a little something in as part of a community, especially if the project sounds meaningful or finishable within this century. Within SoB, they'll allocate resources as they feel it's more useful, but can be moved around with a bit of effort. Eg, someone posting a hundred times about how we need more sievers/2nd pass/P-1/first pass/whatever is likely to attract some undecided people, who just want to help, to his cause.

    If you half agree with this rough categorization of participants, you'll see that there's no definite way to make everyone happy OR make the project definitely more efficient, my (uneducated!) opinion is to offer a slight guidance but let everyone choose what they want to do most. Driving someone away, because the project takes a direction he doesn't like is inevitable, but at the same time some other types will be attracted. Anyone putting his CPU cycles on the project should be given a little liberty on what to do with them-he pays the electricity bills after all! As long as the project moves on, we should all be happy...let the kids play, even when they become unruly!

    /rant mode off

  16. #16
    Senior Member
    Join Date
    Jun 2005
    Location
    London, UK
    Posts
    271
    No need for the rant tag, I think that was put absolutely perfectly.
    Quad 2.5GHz G5 PowerMac. Mmmmm.
    My Current Sieve Progress: http://www.greenbank.org/cgi-bin/proth.cgi

  17. #17
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    factors more towards 50M may be useless.
    Not sure what to say about this it sort of contradicts your other posts, perhaps I'm not understanding correctly. A while back estimates were made that there would be approx three k's remaining at n=50M.

    I and a couple other people,see the high n sieve page, did some calculations on %eff with the client we had. It seemed like we could acutally increase the factor output by about 120% with only a 15% decrease in speed. I believe the optimal n-range was 53M and decreased dramatically by 55M.

    So the point was if we are going to finish this project we may as well start the large dat now (then).

    Regardless you may wish to read that thread.

  18. #18
    Senior Member
    Join Date
    Jun 2005
    Location
    London, UK
    Posts
    271
    proth_sieve isn't as efficient as it could be, which is why Joe and Chuck are throwing so much effort into improving it (and rewriting lots of it).
    Quad 2.5GHz G5 PowerMac. Mmmmm.
    My Current Sieve Progress: http://www.greenbank.org/cgi-bin/proth.cgi

  19. #19
    I agree with maddog1, but basically you need to do your best not to annoy the members you have got. It's a lot easier to look after the ones you've got than try and find new ones.



  20. #20
    Matt: this was part of what I was trying to suggest, people onboard are here for lots of different reasons. I believe an important part of keeping them in, is to let them have the kind of "fun" they like best with the project and this will never be able to be perfectly described in maths, ie even if a proven formula for the perfect efficiency ever surfaces, it just *might* be better to still leave some room for people who want to crunch at their personal whim/style, any contribution to any aspect of the project should be more than welcome! Hell, even if one wanted to sieve on a P4, which is grossly inefficient AFAIK, one is able to and this is a good point for the project. If this makes someone happy enough to stay onboard, let him be, even if his resources aren't perfectly utilized...it's still some extra computer power towards the common goal.

    For the same reason, even if sieving is far more efficient maths-wise (which I also believe), we also want to be doing quite some PRP testing. We need the occasional prime to keep the public attention to the project, we need the progress towards highest n's to keep hopes up! It's definitely nearly impossible to satisfy everyone everytime and still take the most efficient route.
    In fact, the most efficient route for me is to let everyone participate the way he likes-just keep some loose control so that things don't go too much off (like the recent forced switch to 2nd pass, this proved quickly to be a good move, even if some stats-junkies complained or left the project alltogether)

  21. #21
    The ideal way to accomodate this is a unified PRP/sieve/P-1 client. People can choose between first-pass, second-pass, sieve or factoring as they choose for themselves and scoring is unified with it. However, most people will probably leave it as the default - which is 'the server decides the most important work for the client to perform right now'. So changes in what people choose (or in error-rates) can be reflected in what the server hands out to other folks. A balance between the flexibility for the individual and efficiency for the project.

  22. #22
    I agree completely with Vato. My dream of V3 is a GUI (though without graphics, what is it called?) with buttons for every single option. And a button "best for the project. The download speed restrictions should disappear from now to the moment of V3 release.
    Not meant that I am in hurry. I wish Louie and the other guys as much spare time as possible without caring about work and computers.
    H.

  23. #23
    Member
    Join Date
    Dec 2002
    Location
    new york
    Posts
    76
    vato: The ideal way to accomodate this is a unified PRP/sieve/P-1 client.

    Absolutely. Sieve coordination is lovely for the small team of knowledgeable sievers that we have, but a one-click siever with packetized work units would allow us to access the rest of the machine pool.

  24. #24
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    The only problem with that is we do not have much left to sieve, even if we include the remaining 991-50m ranges (it will take only a couple of months to finish it all if we use hundreds of computers there). This comment is valid unless we have a sieve client that can go beyond 2^50, of course.

  25. #25
    Understood. I was talking about the theoretical best efficiency for the project whilst keeping the punters happy - not if it was actually viable :-)

    A combined client/server would then stop handing out sieving work (or do a double-check sieve run) until a new release supports sieving to 2^51 or greater.

    But, it's all moot because we don't have a combined client yet. It may actually turn out that factoring is the only function that may need to be added by then time we get one. (Or maybe we'll have found all 17 primes by then...)

    I also understand that I'm talking about something that would require a lot of volunteer effort to achieve that I'm simply not qualified to assist with.

  26. #26
    Senior Member
    Join Date
    Jun 2005
    Location
    London, UK
    Posts
    271
    A combined client is a lovely idea, but it is a huge amount of work.

    They'd be combining code from 4 (PRP, Sieve, P-1, ECM) different people written in slightly different styles. I've looked at the source for a couple of these and I can see many problems in trying to combine them.

    A couple of programs take advantage of the fact that they do not run endlessly and that when they exit all memory used will be given back to the OS. If you want to make this program persistent then you have to go through and find all of the bits of memory it has allocated and remember to free them when you want to move to a different bit of work.

    Another option is a wrapper program that makes it look like it does everything but just runs one of the 4 underlying binaries depending on what it wants to do.

    This won't look as clean as one single binary but it removes many of the headaches.

    Network comms and/or manual configuration for those without net connections then only need to be added to one binary (the wrapper).

    Still a large amount of work!
    Quad 2.5GHz G5 PowerMac. Mmmmm.
    My Current Sieve Progress: http://www.greenbank.org/cgi-bin/proth.cgi

  27. #27
    Member
    Join Date
    Dec 2002
    Location
    new york
    Posts
    76
    The only problem with that is we do not have much left to sieve

    That's true, we have sieved to the limits of our preferred software. However, if it only takes a couple months to sieve (while proth testing is projected to take another 3 years), this underscores how little sieving we have been doing. My gut says the ratio of months spent sieving : proving should be better than 2:36.

    But forget my gut, a simple calculation tells me that when measured against the computing power we have on proth testing, we have actually only done a single month's worth of sieving in the past two years. We could sieve another 900T by new year's if we had a network-enabled client that could sieve high p at current rates.


    This comment is valid unless we have a sieve client that can go beyond 2^50, of course.

    Is 2^50 equal to 1100T? Weren't the 1100T+ ranges sieved with Nbegon instead of Sobsieve?

  28. #28
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    Originally posted by dudlio
    (while proth testing is projected to take another 3 years)
    Where did you get this figure from??

    It looks to me like we're looking at a time span that can be measured in decades... if we're not incredibly lucky, of course.

    With current client and current computing power, even reaching n=20m might take five to ten years. That being said, I believe we should consider ourselves lucky if we find three of the eight primes up until 20m. Anyways, may be I should revisit my probabilities file before giving more comments.

  29. #29
    Senior Member
    Join Date
    Jun 2005
    Location
    London, UK
    Posts
    271
    From: http://www.prothsearch.net/sierp.html

    We see that:

    From the above tables of primes and currently known search limits we infer that:

    f(x) is the number of k for which their first prime for an exponent n is in the interval 2^x <= n < 2^x+1

    ...
    f13 = 11
    f14 = 18
    f15 = 12
    f16 = 5
    f17 = 5
    f18 > 2

    These figures are correct up to where SoB started (17 k values remaining).

    46157 : 698207 = f19
    44131 : 995972 = f19
    65567 : 1013803 = f19
    69109 : 1157446 = f20
    54767 : 1337287 = f20
    4847 : 3321063 = f21
    5359 : 5054502 = f22
    28433 : 7830457 = f23
    27653 : 9167433 = f24

    So now we have:-

    f13 = 11
    f14 = 18
    f15 = 12
    f16 = 5
    f17 = 5
    f18 = 2
    f19 = 3
    f20 = 2
    f21 = 1
    f22 = 1
    f23 = 1
    f24 = 1

    with 8 k remaining.

    If it was nice and simple and we continue at 1 k per interval (such a big IF) then the final k would be in f32) where the minimum n is 4294967296.

    Ignoring the fact that each iteration would take much longer as the FFT size would have to be increased and pretending that the time to perform a test scaled linearly with n then if a current test at n=10M takes 6 days on a certain PC, a test running at the same speed for n=2^32 would take at least 2577 days.
    Quad 2.5GHz G5 PowerMac. Mmmmm.
    My Current Sieve Progress: http://www.greenbank.org/cgi-bin/proth.cgi

  30. #30
    I think what you call a wrapper would be the best idea, because it can be made modular. Like: You download the basic package, it is able to psp. Then you want to sieve, click a button, and it starts the download of the next module, and the dat-file.
    But I agree it is a large amount of work. Are we speaking about a possible project or about our dreams?
    Me personally I am unable to do the actual programming work because I know nothing but simple programming techniques. But if there is somebody in Europe willing to sacrify some weeks of his next universitary holiday, I think I could be of help for the general conception.

    Anyway, there are so many spectacular people around here, if it is possible, it will be done sooner or later.

    We'll see.
    H.

  31. #31
    Senior Member
    Join Date
    Jun 2005
    Location
    London, UK
    Posts
    271
    I'd love to see this being written however there are several problems.

    1) Lots of people are willing to start working on a project like this, not many projects like this get finished.

    Enthusiasm is good but that soon needs to be replaced with some hard graft to actually finish off the project.

    2) To do it properly it needs to be fully integrated into the current SoB framework.

    I'm not knocking Matt's excellent work on his sieve reservation site but I don't think we need Yet Another Website to coordinate factoring, and handle the automatic sieve reservations.

    In my opinion it needs to be implemented on the existing SoB server (sb.pns.net). All interaction (from users) should be done through the existing website. This means controls over ranges reserved, progress of current ranges, factor submission directly from client to DB, etc.

    Even if the majority of work is done by other volunteers, this requires a huge amount of work from the SoB admins themselves.
    Quad 2.5GHz G5 PowerMac. Mmmmm.
    My Current Sieve Progress: http://www.greenbank.org/cgi-bin/proth.cgi

  32. #32
    Member
    Join Date
    Dec 2002
    Location
    new york
    Posts
    76
    In my opinion it needs to be implemented on the existing SoB server (sb.pns.net). All interaction (from users) should be done through the existing website. This means controls over ranges reserved, progress of current ranges, factor submission directly from client to DB, etc.

    Agreed, agreed. My personal opinion is that the sieving client would be easier to write than the proth client that the admins wrote for us in the beginning. It is a simpler algorithm with a simpler division of work units. I haven't seen the internals of our network client, so you're right that the admins would have to get involved. I have C and web/db experience however and I would be willing to help.

  33. #33
    Member
    Join Date
    Feb 2003
    Location
    Lucerne, Switzerland
    Posts
    30
    Originally posted by Greenbank
    46157 : 698207 = f19
    44131 : 995972 = f19
    65567 : 1013803 = f19
    69109 : 1157446 = f20
    54767 : 1337287 = f20
    4847 : 3321063 = f21
    5359 : 5054502 = f22
    28433 : 7830457 = f23
    27653 : 9167433 = f24

    So now we have:-

    f13 = 11
    f14 = 18
    f15 = 12
    f16 = 5
    f17 = 5
    f18 = 2
    f19 = 3
    f20 = 2
    f21 = 1
    f22 = 1
    f23 = 1
    f24 = 1

    i would say

    f16 = 5
    f17 = 5
    f18 = 2
    f19 = 3
    f20 = 2
    f21 = 1
    f22 = 2
    f23 = 1

    it looks slightly better now. And of course, there is still hope that f22 and f23 will increase.

  34. #34
    I started a little bit thinking about the imaginary client, and found then out that a lot of things have already been thaught. (as usual).

    Consider this page:
    http://wiki.seventeenorbust.com/index.php/VersionThree

    I wonder when it might appear. And if it is worth investing some work for a provisional thing.

  35. #35
    Senior Member
    Join Date
    Jun 2005
    Location
    London, UK
    Posts
    271
    Originally posted by dudlio
    My personal opinion is that the sieving client would be easier to write than the proth client that the admins wrote for us in the beginning. It is a simpler algorithm with a simpler division of work units. I haven't seen the internals of our network client, so you're right that the admins would have to get involved. I have C and web/db experience however and I would be willing to help.
    The algorithm for the proth_client is VERY simple. It's just calculating for a given k,n pair:

    a^((N-1)/2) mod N

    where N = k*2^n+1 and a is typically 3 (although I have feeling it does multiple a values at the same time).

    If the resulting value is 0 then that k,n pair is prime. If it isn't then the residue is the lowest 64 bits of the result.

    However, the technical implementation is very complicated. It's implemented (if I remember correctly) via a highly optimised FFT written in assembly based on Woltman's code. I've never seen the code to the PRP client but I've seen similar blocks of code for the core FFT stuff.

    The sieving algorithm is a more complex algorithm (see my recent posts on how sieving is performed (Discrete Logs, BSGS, SPH, etc) but it's implementation is easier to understand than the PRP client, sieving deals with much smaller numbers and so FFT multiplications are not requried.

    The main code for proth_sieve is 97kb of source (3500 lines) with various core functions coded in assembly.

    My simplified source is down to 3000 lines (after cleaning up lots of the code), I'm sure Joe_O and Chuck's version is even more readable. My goal is to rewrite the entire codebase (this helps me to understand every part of the code) although this is duplicating the work of Joe_O and Chuck. Their code will almost certainly be better but there is no better way to learn about something than to rewrite it. Whatever G4/G5 assembly I produce will be forwarded to Joe_O and Chuck for them to include in their new siever.

    Anyway, lots of (real) work to do today, and we had a power problem at work over the weekend which has scuppered my plans. I lost 2 days of sieving when my diskless box (hard drive died months ago so I just run things from a ramdisk) went off, the other machine restarted fine when it eventually came back on. Both 1T ranges are now due to finish in 5d0h45m and 6d12h0m, smack bang in the middle of the weekend.
    Quad 2.5GHz G5 PowerMac. Mmmmm.
    My Current Sieve Progress: http://www.greenbank.org/cgi-bin/proth.cgi

  36. #36
    Member
    Join Date
    Dec 2002
    Location
    new york
    Posts
    76
    Nuri: >(while proth testing is projected to take another 3 years)

    >Where did you get this figure from??

    Just based on the fact that we've gotten halfway in 3 years. I meant it for comparison purposes (not going to take less right?)


    Greenbank: >A combined client is a lovely idea, but it is a huge amount of work.

    >They'd be combining code from 4 (PRP, Sieve, P-1, ECM) different people written
    >in slightly different styles. I've looked at the source for a couple of these and I
    >can see many problems in trying to combine them.

    Well it may be too much to write a fully-integrated client right off. Why don't we start with a sieving-only client that behaves the way the proth client does with respect to the central database? That would eliminate our manual coordination, and allow noobish users to sieve. After that, an integrated client will be just gravy.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •