Page 3 of 5 FirstFirst 12345 LastLast
Results 81 to 120 of 179

Thread: High n-range sieving

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

    Thanks for point this out... there are two things to consider here.

    First how much will this speed up the client?

    Bringing the lowest n up from 991 to 25,000 will speed up the client, but not by much.

    speed increase = [100 x (25000-991)]/50000000 = 0.05%


    Second the dat in addition to being the (paramemter file) to run sieve is also an archieve of all unfactored k/n pairs n<50M. So if one decides to factor these small numbers they always know which k/n pairs are left by downloading the latest dat.


    So I don't think the speed increase is worth the sacrifice of maintaining two files, dats, or a seperate k/n archieve, etc.

    Your thoughts?

  2. #82
    Sieve it, baby!
    Join Date
    Nov 2002
    Location
    Potsdam, Germany
    Posts
    959
    I think it's just a design decision without "right/good" or "wrong/bad".

    There definitely is next to no performance increase. And the use of the sieve.dat as a factorization repository has its merit, no doubt.
    It's just my addiction to optimization, I guess.

  3. #83
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    addiction to optimization

    I'm with you one that one, eventually we will change the 991<n<50M dat to a different size that's for sure. It depends on alot of factors (wow sometimes I kill myself); how many missed factors we find through the resieve, if we eliminate the 1.8M<n<20M dat and go to stickly n<=50M, when we find the next prime, if we find missed prime, the error rate etc...

    But until then I'd like to get as many people to use the 991<n<50M dat as possible followed by prp-secondpass. Thanks for commenting on and following this thread Mystwalker it's great to have your input.

  4. #84
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    The most recent version of the 991<n<50M dat is available here...

    http://www.teamprimerib.com/vjs/

    There is no logon etc, hopefully this will make things easier.

    The proth programs are also mirrored here since Klassons site is not resolving today.

  5. #85
    There is an updated link to Klasson's site:
    http://mklasson.com/proth_sieve.php
    which resolves to:
    http://85.8.4.99/proth_sieve.php
    I don't think the university one works anymore...

  6. #86
    Moderator Joe O's Avatar
    Join Date
    Jul 2002
    Location
    West Milford, NJ
    Posts
    643
    Keep those factrange.txt (and fact.txt for the 991<n<50M) files coming. Here is a picture of the results: (Updated to reflect the new dat)
    Attached Images Attached Images
    Last edited by Joe O; 05-05-2005 at 12:51 PM.
    Joe O

  7. #87
    Moderator Joe O's Avatar
    Join Date
    Jul 2002
    Location
    West Milford, NJ
    Posts
    643
    O yes, we are active for p <100T as well: (Updated to reflect the new dat)
    Attached Images Attached Images
    Last edited by Joe O; 05-05-2005 at 12:52 PM.
    Joe O

  8. #88
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Joe,

    correct me if I'm wrong here but those green and light blues below 20M are missed factors correct?

    If so very cool and nice chart.

  9. #89
    Moderator Joe O's Avatar
    Join Date
    Jul 2002
    Location
    West Milford, NJ
    Posts
    643
    Originally posted by vjs
    Joe,

    correct me if I'm wrong here but those green and light blues below 20M are missed factors correct?

    If so very cool and nice chart.
    VJS,
    They *were* missed factors, but we found them! <G>
    Joe O

  10. #90
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    joe, do you have anything in table format?

  11. #91
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Nuri,

    What were you looking for exactly I may have it...

  12. #92
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    This is just to see the number of missed factors through main sieve effort (hopefully not much).

    What I have in mind is something like the one below. Please feel free to change anything that would make it easier for you to create the table.
    Attached Images Attached Images

  13. #93
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    Ooops, 50T<p column would distort the data. There's no need for that.

  14. #94
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Hey Nuri, I think I have just the thing to make that work. Joe sent me an out with

    n vs p vs # factors found.... I'm actually going to cut this file at 25T however and be warned, we are not entirely sure how accurate it is, let me explain.

    What the table will represent is those factors we found for p<25T and n<20M, however the question remains were these factors actually missed? Well, the k/n pair existed in the dat this is true so one would think it eliminated a test. But the dat is formed and updated from the results.txt output file which has been cropped at p>25T for size purposes. So the question remains did the test exist in the server que???

    In some case we have a very strong feeling that the test did exist in the que b/c the old client versions were missing certain ?? j ?? or covering set (Joe could explain more). Or the people only sieved one range and dissappeared.

    Example...

    12000-12100 Nuri [complete]
    12100-12150 Mr. newbie OneTimer [complete]
    12150-12200 Louie [complete]

    And we find a pile of factors between 12148-12150

    But in other instances people who you wouldn't expect to miss a factor have?

    _____________

    Regardless, we are still finding missed factors above 25T, where we definetly know they are missed factors. These factors found above 25T we can say 100%, hey they were missed and yes they are new. Now we can try to come up with reasons for them (users, clients, server, computer, etc) then predict patterns and gaps, we may offer these ranges to people in the future... I'm not sure if there is that much interest in these types of special projects.

    Joe, Mike and I have been doing this factor prediction with quite a bit of sucess a some failures. Regardless when we repeat the range we always find factors from 20M-50M using the 991<n<50M dat.

    O.K. let me get to he table.

  15. #95
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    ARRGHH!!!

    I had a huge write up and lost it on submission... sorry.

    I'll have to come back to it later perhaps others can spot the trends and we can discuss. Can someone explain the table as well. I seriously ran over on message size.

  16. #96
    Target Butt IronBits's Avatar
    Join Date
    Dec 2001
    Location
    Morrisville, NC
    Posts
    8,619
    Originally posted by vjs
    I had a huge write up and lost it on submission... sorry.
    Notepad is your friend when doing more than a quick reply
    Sorry you lost it all!

    Ya think that TABLE is large enough to read at about 100 yards

  17. #97
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Yes, I generally crtl-a crtl-c before I submit which I did as well but for some reason it didn't copy? Also you can't preview pictures... Free-DC fourms are great and stable. My fault ... the picture was 3MB in size

    Regardless here is an excel version.

    Points to watch for

    n<3M, n<1M, the 300K<n<3M and 3M<n<20M dats, 7T-8T, 14T-15T, 19T-20T.

    I didn't think there were any mistakes in the data but my day is rough, thanks Ironbits.
    Attached Files Attached Files
    Last edited by vjs; 05-05-2005 at 05:48 PM.

  18. #98
    Target Butt IronBits's Avatar
    Join Date
    Dec 2001
    Location
    Morrisville, NC
    Posts
    8,619

    missed test

    Look ok? Send me anything you want and I'll size it anyway you want - files that is.
    Attached Images Attached Images

  19. #99
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Well I looked through the lastest stats some gap analysis that Joe sent me and there are two "high possibility" missed factor ranges <75T.

    Is anyone interested in doing a T or two that encompasses either of these gaps?

  20. #100
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    what are their sizes?

  21. #101
    Target Butt IronBits's Avatar
    Join Date
    Dec 2001
    Location
    Morrisville, NC
    Posts
    8,619
    Originally posted by vjs
    Is anyone interested in doing a T or two that encompasses either of these gaps?
    Yes, if it will help you guys out...
    24/7/365 crunching going on over here

  22. #102
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Originally posted by Nuri
    what are their sizes?
    It doesn't really work that way, the size of the acutal gap is quite small but where is it exactly? (this would be too easy).

    It's the matter of resolution to the method that's not great.

    Let me give you an example, a gap was predicted around a low 33T-34T (can't remember exactly.

    While a sieve of 32-33T and came up with the following missed factors at particular n-level,

    n-range (#missed factors)
    1M-2M 1
    2M-3M 5
    3M-4M 0
    4M-5M 2
    5M-6M 1
    6M-20M 0

    9 total missed in 1T. Not great I guess, but 31-32T had one missed factor and 33-34T had 2.

    Another gap was predicted around between 38T-40T

    So far I we found 32 factors between 38-40T and 1M<n<20M, at this rate its almost better than first pass sieve.

    I'll make another table like the last one once we have everything less than 40T done.

    --------------------------

    What I offered before was a test the prediction model, I can't say 100% that there will be any missed factors but it's more than likely. For the near term it's probably worth pecking at some ranges between 50T-100T as opposed to continuing from 44T up (at least from the standpoint of missed factors). For this and administative purposes 1T chunks at a time are probably best.

  23. #103
    I love 67607
    Join Date
    Dec 2002
    Location
    Istanbul
    Posts
    752
    I see, thx..

  24. #104
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Here's an example of a "High probablility missed range"

    99.929T 19249 19579982

    It would have taken weeks to test this pair twice, found it in two days with sieve probably more to come.

    Not to mention all of the n>20M stuff.

    Re-doing the low ranges now is really only benifital if we find a few of these from time to time.

    Probably wound't have found it using p-1 and there was obviously no other factor <45T or no other one that we found between 45T to ~800T.

    99 928888 301542 = 2 x 3 x 43 x 387231 272099

  25. #105
    Old Timer jasong's Avatar
    Join Date
    Oct 2004
    Location
    Arkansas(US)
    Posts
    1,778
    Originally posted by vjs
    Regardless, we are still finding missed factors above 25T, where we definetly know they are missed factors. These factors found above 25T we can say 100%, hey they were missed and yes they are new. Now we can try to come up with reasons for them (users, clients, server, computer, etc) then predict patterns and gaps, we may offer these ranges to people in the future... I'm not sure if there is that much interest in these types of special projects.

    Joe, Mike and I have been doing this factor prediction with quite a bit of sucess a some failures. Regardless when we repeat the range we always find factors from 20M-50M using the 991<n<50M dat.
    I've heard a little about some accounts, called "garbage" and "secret" I think, that I'd be willing to try if I had any instructions.

    I don't care much about points, but I LOVE to crunch. If you have anything unusual that doesn't require programming or compiling and has instructions that can be followed by your average college student, I'm game to do it. I won a computer in a drawing by my team, Free-DC, so I'll have some extra crunching power in a week or two.

  26. #106
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    The secret and supersecret accounts are old accounts that have been replaced by QQQsecondpass.

    So if you wanted to run secret or supersecret the best bet is use your usernameQQQsecondpass. Both of those account basically ran secondpass anyways.

    What you have to do is edit the registry look at the lost test thread second down main forum. In the registry you should see your user name jasong

    edit it to jasongQQQsecondpass.

    Now garbage is another matter, here you just log-on (change your username with the main client) to garabge. I'm not sure if this account is really doing anything useful currently. It may be double or even tripple checking. Until that's straightned out or explained fully then I'd suggest not running the garbage account at all.

    There is another special account holepatch, it's currently running lost tests or something strange there isn't many tests there about 1300 and they are all between 1.8M and 3M.

    I'm doing a few using the username holepatch just to finish off that que.

    In all reality it's probably best to run the QQQsecondpass IMHO.

  27. #107
    I have got a stupid question. Soon, the so called 'high range sieving' (the range isn't that high, anymore) will have dropped the factor density sufficiently to change the server settings to accept factors for n>20 000 000. My belief is that one day, this will happen.
    Is somebody considering stopping the 'normal' sieving and swiching to 'high range sieving' completely? At least when the server accepts all factors? Or are there important reasons to continue with the dat file used until now?
    The only reason why not everybody is using the new large dat seems to me to be the factor acception thing.
    Correct me if I am wrong, please. H.

  28. #108
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    hhh,

    Your correct, I think the dat would be used more if the server would accept, but ultimately it will be Louies call about accepting the factors. Alot of "older" sievers are using 991<n<50M now for main effort ranges. All those factors n<20M are accepted through the server and it's not difficult to zip and mail those above 20M.

    I'd like to hear from others about using 991<n<50M. Also if we would completely switch it might be to a 1.9M<n<50M dat, at this time it's hard to say. There is some interest in those low-n's

  29. #109
    Moderator Joe O's Avatar
    Join Date
    Jul 2002
    Location
    West Milford, NJ
    Posts
    643

    It's DAT time again!

    I've started processing the fact.txt, factrange.txt, and factexcl.txt, files submitted since the last DAT was created. The following graph shows what is new since the last time. If anyone has factrange.txt files from the 20M effort, please send them to factrange at yahoo dot com. Those of you using the 991<n<50M dat please submit your fact.txt and factexcl.txt files as well as your factrange.txt files. Thank you.
    Attached Images Attached Images
    Joe O

  30. #110
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Joe I'll have 40-44T done in about a week with 991<n<50M.

    <edit> pushing that range a little hard trying to send it by the weekend. I'll also send out the partials from my higher ranges.
    Last edited by vjs; 06-08-2005 at 10:58 AM.

  31. #111
    my range should be completed within 2 days.

  32. #112
    Moderator Joe O's Avatar
    Join Date
    Jul 2002
    Location
    West Milford, NJ
    Posts
    643
    Just to complete the picture from my previous post, here is the primary sieve range. Note the places where people used the 991<n<50M dat. 250% more pairs sieved for 10% more effort.
    Attached Images Attached Images
    Joe O

  33. #113
    I've switched to this larger DAT file and speed has decreased from ~550kps to ~430kps



  34. #114
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    That's a little higher than expected Matt generally people see 10-20% decrease with the average around 15% in speed, I think Joe is being over optimistic.

    You have to remember however that you are actually sieving a range that is over 250% larger. So your increasing overall production by 220%.

  35. #115
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Code:
    Lower	Upper	k/n's	k/n's	Current	Update	Update	Update
    (n>)	(n<)	25T	Found	Dat	12-May	6-Jun	44T+
    991	2M	53303	244	52944	155	89	115
    2M	9M	183438	598	182840	316	64	218
    9M	10M	26223	168	26055	66	3	99
    10M	20M	262951	746	262205	391	66	289
    20M	30M	289470	6285	283185	2866	1846	1573
    30M	40M	290320	6244	284076	2778	1877	1589
    40M	50M	291558	6323	285235	2923	1838	1562
    50M	100M	1554759	2370	1552389	967	778	625
     	Sum	2952022	23093	2928929	10462	6561	6070
    							 
    Lower	Upper	k/n's	k/n's	Current	Update	Update	Update
    (n>)	(n<)	25T	Found	Dat	12-May	6-Jun	44T+
    991	2M	53303	244	52944	155	89	115
    dat	%	-	0.46	99.33	0.29	0.17	0.22
    2M	20M	472612	1512	471100	773	133	606
    dat	%	-	0.32	99.68	0.16	0.03	0.13
    991	50M	1397263	20608	1376540	9495	5783	5445
    dat	%	-	1.47	98.52	0.68	0.41	0.39
    20M	50M	871348	18852	852496	8567	5561	4724
    dat	%	-	2.16	97.84	0.98	0.64	0.54
    50M	100M	1554759	2370	1552389	967	778	625
    dat	%	-	0.15	99.85	0.06	0.05	0.04
    991	100M	2952022	22978	2928929	10462	6561	6070
    dat	%	-	0.78	99.22	0.35	0.22	0.21
    Last edited by vjs; 06-13-2005 at 04:20 PM.

  36. #116
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Well Joe just sent me some stats from the latest dat run, I'll be processing these thoughout the day.

    These stats above are a continuation from the 25T stats update earlier. Currently all p<44T have been sieved with the 991<n<50M dat file. Since the all p<25T update we have managed to eliminate another 18852 k/n pairs between 20M<n<50M reducing the total number of tests by an additional 2.16%. With this 25T<n<44T p range interestingly enough we have also eliminated 0.2% of the tests above 50M using factrange.txt.

    Next, I'll work on tabulating the missed factors n<20M, doublecheck portion of this sieve effort.

    Note that update May-12 and Update 6-Jun were non-public updates but I have included them regardless.
    Last edited by vjs; 06-13-2005 at 04:21 PM.

  37. #117
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    O.K. here is the table of factors missed by previous sieve efforts later found using the 991<n<50M between 25T-44T.

    Our double check sieve effort removed a total of 314 factors with n<20M from 25T<p<44T.

    This can be broken down between firstpass and secondpass tests, other factors found are below the double check effort.

    163 secondpass tests
    71 firstpass tests

    Looking at the stats it certainly looks like the effort was worth it for the 25-44T range.
    Attached Images Attached Images

  38. #118
    Interesting update VJS...
    I was just wondering, is there a specific known reason for the large number of missed factors @38 & 43T?
    I mean, was it a faulty PC, a careless user who forgot to submit all finds or something else I'm missing?
    In any case, good effort for your team...congrats

  39. #119
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Several reasons for the missed factors and why there are so many ...
    Looking at the table there are quite a few things to consider.

    First those factors less than 300K were never looked for in the first place so those 0M-1M are artifically high (not a double check etc.) Second there are some problems regarding the 300K<n<3M and 3M<n<20M dat and range resevations at the time. It seems like some people were using the 300K<n<20M were they should have been using 1M<n<20M. So some regions were never sieved for n<3M or 3M<n<20M.

    Missing the factors for n<3M are currently not that critical but missing n=10M-20M factors, WOW!!!

    This is part of the reason why we are redoing the sieve effort using a complete 991<n<50M, we will get all of them all including those 20M<n<50M.

    Second when one of these 3M<n<20M ranges or 300K<n<20M ranges are found or someone didn't submit 20G worth of factors etc. The shear number of factors we find is very high. This is due to the factor denisity at low p.

    When we were sieving around 45T we were getting something like 400 factors per 1000G sieved, now we get roughly 15 factors per 1000G sieved (in the 1M-20M range). So missing a 10-20G sieve range didn't seem like much then, only 4-8 factors, but that translates into 250-500G of todays sieve.

    Of course there were other problems early on where proth or the sieve client at the time just missed factors. I believe we are beyond this point now (p=44T) but several ranges above 44T were sieved and we found factors there as well. Why I don't know but we are still finding some.

    I think what's important is to continue this low-p high-n effort until the number of missed factors decreases to a point of being inefficient. I also encourage people to sieve main ranges (i.e. the current effort) with the 991<n<50M dat.

    I did a very rough calculation...

    I would have taken me a little more than a year to sieve this entire range by myself ~380days. However to test all of these missed k/n pairs would have taken me in excess of 3 years, that's a pretty vaild arguement for the effort in my eyes.

  40. #120
    Moderator vjs's Avatar
    Join Date
    Apr 2004
    Location
    ARS DC forum
    Posts
    1,331
    Specifically 38 and 43T they were larger holes Joe will probably post a graph soon.

Page 3 of 5 FirstFirst 12345 LastLast

Posting Permissions

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