2004/10/06 : I'm still sieving, don't worry. :-) It's just one machine, and I'm only sieving exponent 262144, which presently isn't in demand yet. Wow - I've been sieving solidly for more than two and a half years!
2003/sometime : Everyone apart from me has stopped sieving - hopefully to test some ranges.
2003/10/06 : I'm still sieving, don't worry. :-)
2003/07/05 : I've changed a few things on the reservation system, so if you saw any outage, that was me mucking around. The filter files' URLs now look just like files, rather than CGI queries.
2003/07/05 : We have a new siever on board, Scott Murray, who brings our allocation back up to 5 (Michael, Kimmo, Scott, Michele, Me) again. Scott has been a GFN tester, and has kindly volunteered to join in the sieving effort. I've put him on 65536 at 80Q, thus a couple of months ahead of Kimmo's range. When they meet 65536 will be at well over 100Q. I've finally joined Michele on 262144. I've started at 90Q, which is more than 3 months away from Michele's 52Q, and this will just be let run. Michael's pushing 8192 amazingly. I will push 16384 as far as he pushes 8192. I get the feeling that I'll need to push 32768 a bit further as well too! Slow down Michael! Only joking!
2003/06/16 : 32768, sieved to 100Q, is now available. I'm not going to sieve that further although in theory more could be done. I shall shortly join Kimmo on 65536, but I've had a few PC hardware disasters recently, and I'm trying to get back on my feet again. Wow - have I really been doing GFN sieving for 15 months?
2003/06/16 : Extended range reservation database is now up and running. It's still in a slightly experimental form (with the emphasis on 'mental'), but seems functional. 8192, 16384, 32768 and 65536 are all reservable and downloadable. I still have to manually manage the marking of ranges as completed or are being returned.
2003/05/07 : 32768 reaches 65Q after 150 days! A huge thank you to Bo for giving up one of his machines for so long. I'm still plodding away at the 65-100Q zone. I'm up to 72Q5 (contiguously) by the looks of it, looks good. Thanks again Bo, good luck testing some now!
2003/04/04 : You may have noticed I've lost the inclination to update this so regularly, I've had my mind on other, more pressing, things. The status page always contains the latest information I have though (and Kimmo is very good at giving updates nearly daily for 65536). Since February I took 16384 to 70Q, and stopped there, and I now have all of my 3 machines running on 32768 with Bo. I'm doing 65-74-85-95Q, but before I finish that, in 40 days time, Bo will have reached 65Q. 100Q looks a breeze with 4 machines (1.25Q/day) we'll definitely want to push it beyond that though, as our removal rate is still pretty high.
2003/02/24 : You'll see 2 records for 65536 now, one the old sieve that isn't being continued, and one the new sieve being done by Kimmo. Our estimations are that at least 55M is testable, which means that there's a range of 54M extended candidates, rather than the old range of 19. It will take 2 months on the machine that Kimmo's using to get to the same level as before (and therefore have nearly 3 times as many candidates as before, equally well sieved). I honestly expect to join Kimmo before then, as I'm now _very_ close to finishing 16384. The 20-30Q machine has just completed, 30-40 was already done, and the 40-50 machine is at nearly 48Q! In 15 days time, give or take, I expect to be at 65Q, and to stop there. I'll then join Bo on 32768 for a big long push.
2003/02/22 : Oh - Michael Angel's record non-Mersenne is no longer the record. A large 3*2^n+1 Proth(Generalised Fermat Factor too) has crept ahead of it. No worry, the size difference is quite small, and I'm sure that our 131072 work will carpet-bomb the zone above it in the record tables. Until then, congratulations to John Cosgrave. Of course, Seventeen or Bust are still looking like the most likely to stamp dominance on the non-Mersennes next, and quite convincingly at that, when the next one finally appears.
2003/02/20 : Kimmo Herranen has joined us again, to redo 65536 with a wider range. I decided that 0-20M was such a small proportion of the testable range and it would want to be sieved to much further, it seems a waste to spend several CPU months doing something that's only a third as useful as it could be. That barely makes sense. I'll rewrite it when I wake up, my brain's dead.
2003/02/17 : Congratulations Michael Angel for finding the world's 5th largest prime at well over 600000 digits. It is also the largest non-mersenne, and topples George Wolmann and GIMPS's first find from 1996, which had 420000 digits. Yes, we (if I may say 'we') appear a little off the pace, but we are catching up, and that's all that matters!
2003/02/16 : There's news, but just not news of sieving progress... However, it's not public knowledge yet, so I'll leave you wondering what it is...
2003/02/10 : No news is still good news. My 16384 is up to 26G, and in 13 days will be up to 48G (as 30-40 is already done, and 40-50 is well under way). Better than that - extended 8192, 16384, 32768, and 65536 ranges all now have a few _very large_ users, as well as small 131072! After quite a lot of throught, planning and effort, all of the eggs are beginning to hatch! 2003 will be a good year for GFNs!
2003/01/29 : Wow, is it really that long since the last bit of news? Anyway, no news is good news. Sieving is progressing grandly. I'm still a month away from taking the extended 16384 range to 50Q.
2003/01/13 : 100 Quadrillion has been reached for the 131072 range! This probably counts as one of the largest sieving tasks ever undertaken. 100Q is 450GHz-days, i.e. well over a year's work. The remaining ~3150000 candidates have each passed a divisibility test against >380 billion primes. In plain old 'trial division' terms, that's the 3.15e6*380e9 = 1.2*10^18 divisibility tests that have been passed. Of course, we didn't use trial division, so it's not a fair comparison, save to emphasise the fact that the true sieve for 131072 is equivalent to 40 trial divisions per clock tick!
2003/01/08 : Hoorah! I have my first _big_ client for 131072. I've been able to deliver a large chunk sieved to 98Q. Predictions say that the chunk is realistically large enough to contain a prime. That also means that it's large enough to take a very long time. Good luck, my friend, good luck!
2003>/01/06 : 2 machines on the 16384 large range now ~500T/day to join David's ~500T/day. It doesn't take a professor to work out that's 1Q/day. It's going to be a very hectic month, with such a big push on that range, but by february they'll all be very high quality candidates indeed.
2003/01/04 : Happy New Year. The second machine last night finished its 131072 range, so I'll be moving that onto 16384 too soon, after I've done a few speed tests. 131072 is now up to 97Q. Not far to go (I'm going slower than expected as I've got fewer idle cycles currently - I'm using the machines as active work machines, and dear old emacs takes a few cycles (though not as many as winword!)).
2002/12/29 : Finally one of my machines has completed its 131072 work. So 131072's filtered up to >89Q. Not long to go now before I put it on hold. The machine's moved straight onto the 16384 extended ranges that David Underbakke started a month back. I started at 30Q, and will add mu other machines at 45Q and 55Q as they finish 131072. Michael Angel has come up with interesting ideas for statistics for seeing how much work is being done (saved) by this pre-sieving. I'll work those out when the next machine comes free (5 days max).
2002/12/16 : GRRRRR! I've just noticed that something calling itself 'winword' has been eating 99% of the CPU on a machine I personally never use. It's been like that for several days. If sieving does not progress as quickly as it could - blame Mickeysoft.
2002/12/11 : See the status pages for a shock! Exponents 8192, 16384 and 32768 are being brought back to life again, as Yves has expanded the searchable range, at an acceptable speed cost (it's still faster than an ordinary 'Proth' test).
2002/12/09 : Don't worry - I've not fallen asleep, it's just that we're on the long haul now, and there are few highlights. 131072 is coming to and end, finally, and there's a little surprise coming too, thanks to Yves' wizardry, and a few extra volunteers - though not where you first expect. More later
2002/11/16 : We have a new siever! Bo Xiao has volunteered a really fast machine to give 262144 a real boost. Splitting ranges over multiple machines means it's hard to pinpoint how far one gets by any point in time. 70Q by early next year should be possible. That's certainly past the trial-division efficiency cutoff. I'll have more figures regarding that when I get to run a few tests as my 131072 sieving draws to a close. Bo will join us in a week or so. I'll keep you all posted. (That's funny - I bet nobody but web-bots read this! However, it's good to have everything recorded.)
2002/11/04 : Web page(s) redesigned! Thanks Anna for helping me. Nonospaz has completed 40-50Q. I've done some analysis for 131072. The results are surprising! The jury's back, and the verdict is in.
2002/10/23 : If I had a penny for every time Windows crashed, I'd be a rich man.
I wonder if that's how Bill Gates made his money! Grrrr!
I think that 131072 is finally beginning to run dry. I'll let Gigaspaz (Dur1300,
50Q-60Q) and Nonospaz (Dur900, 40Q-50Q) complete their ranges (10 days) and then
move them to 262144 instead. Neospaz (Dur1300) will just run 60Q- (between crashes)
until its mean removal rate drops below a certain point.
2002/10/17 : Neospaz (that's the 'doze machine) has finished 27Q-40Q, which pushes the contiguous prime range to >46Q, and is now working on 60Q-. Why not? I seem to have time to push it a bit further. However, I mustn't forget 262144, of course. I'll start that in November, and I hope to have made reasonable progress by spring. I'll heat my flat with these Athlons!
2002/10/14 : I'll never finish the ranges if "The reliable Windows NT" keeps BSOD-ing. Twice in two days now... (since I started using that machine for audio, which I haven't done for a couple of months since the network mysteriously stopped working). I'd convert it to Linux like my other machines if it wasn't for the fact that Anna needs MS Office for her work.
2002/10/11 : Ooh, my first request for 131072! I'm not expecting a huge rush yet, but I'm still glad I am doing the big push that I am. Up to 38440T, which means that in 6 days' time, when I hit 40T, the contiguous sieve depth will jump to 46600T. I'm also hoping that the sieve ratio will drop below 16% when I do. I guess I'll stick the machine onto 60Q- after that. Can I have a volunteer, someone who is going to test a 131072 range, for 1 or 2 days to help me judge more accurately the depth I should sieve to?
2002/10/02 : Ah, back from holiday, and within 6 hours of getting home, the lowest-range machine is just completing its range. This means the lowest range is the 27Q-40Q machine, which is at 35820T. Note this isn't really further than I predicted before I left because, due to a mistake, I returned one day late! I'll get the just-finished machine now working on 50Q-, as it looks like sieving is still worthwhile. It's noticably less effective at the 43Q range (where one of the machines is currently) than it used to be in the twenties, but it's still noticably better than testing, which means it should continue to be sieved. I'll update the MISD stats tomorrow, but tonight I think it's time for bed!
2002/09/20 : I go on holiday to St. Petersburg (the real one, not that silly US fake one) for nearly a fortnight. When I return, the sieving depth for 131072 will have another quantum leap, as a range on one of the machines completes. Cross fingers I'll be able to change that 24650T to 35500T next time I update this page. Until then, I've left the rest of the 65536 range available for everyone to grab.
2002/09/14 : The machine taking 131072 from 13Q-17Q has completed and is
now working from 40Q-. I've merged the files together and updated the MISD
rating (meaningless indicator of sieve depth) - it's jumped past 67 with gusto.
It'll be 35 days before the 27Q- machine reaches 40Q. I'll decide what needs
to be done afterwards, but it really looks like I'll want to sieve it further.
Just while writing this paragraph, I've noticed that the useful candidate
removal rate is still 1 every ~40 minutes. (With the wider range I'm sieving, it's 1
every ~3 minutes, but presently the large numbers aren't testable as efficiently.)
To that end, I've re-evaluated my targets again.
2002/09/13 : Rumours are that a friend will help me sieve 262144 on his P4 while I'm pushing 131072. David's been working on making his sieve as fast on P4s as it is on Athlons (clock per clock) - cool!
2002/09/02 : 262144 has been suspended at just over 25Q. That's about the same effectiveness as 12Q5 on 131072 or 6Q2 on 65536, i.e. better than a kick in the teeth. I've put all my 3 machines onto 131072 for a big push. There's a Duron 900 on 13Q-17Q (@14Q9), a Duron 1300 on 17Q-27Q (@19Q), and now a Duron 1300 on 27Q-35Q. The 900 will reach 17Q in 11 days' time, and then I'll probably move it to 40Q-. The first 1300 will reach 27Q in 28 days, and I'll decide what needs to be done when I see what the removal rate is like then. Whatever happens (apart from fire, flood, etc.) by the end of the month, I'll have reached 35Q, a target impossible 9 months ago.
2002/08/25 : 131072 has now stomped past all the emergency ranges I
did in the past. That's a shame, as that was a month's work that nobody
made use of. However, it doesn't matter because as long as I'm pushing
the sieve limits higher, nothing else matters. To that end, I've moved
the machine that was doing 524288 to join the other on 131072.
Hmm, I see that the meaningless indicator of sieve depth for 131072 to over 66. Nope, I don't know what that means! (See
2002/08/09.)
2002/08/24 : Quickie - David Underbakke has just increased the sieve speed by nearly 10% on my Durons - bonzer!
2002/08/21 : No real news. It's great to see lots of new faces asking for ranges. it appears as if the usefulness of the sieving is finally kicking in. My machine allocation is broken - I need to boost 131072. I'll think of something.
2002/08/09 : I've been asked to provide a numeric indication of how well the sieving is going, so I've added the sieve ratio to the table of ranges. However, each exponent sieves differently, so I've tried to normalise it - can you help make the normalised value more meaningful?
2002/08/08 : David and I have agreed that at 25Q, it's time to put 65536 to bed. If it becomes possible to test the larger base range, then it will be worth restarting it. So a big thank you to David for that final big push on 65536.
2002/08/05 : Simply a progress report - see the summary above. David's pushed 65536 to nearly 25Q, and I've pushed 524288 over 10Q.
2002/07/15 : 65536 being "outsourced" again! I forgot to say a few
days ago that David Underbakke is taking on all sieving duties for 65536
now. David intends to be a big tester of this range and therefore
has a vested interest in seeing it very well sieved; he has thus
generously agreed to continue sieving the whole range 24/7 on a fast
machine and feed back all the results to me so everyone can benefit.
Thanks again, David.
Oh - I forgot to say look at the current 65536 depth! I had to
redo
Kimmo's 10-11Q range myself, but that was the only missing stage up to
16Q. :-D
2002/07/08 : Real Algorithmic Improvement! - Within 8 hours of me passing the information to David Underbakke and Jim Fougeron, David has already sent back a new executable with the improvements. So currently I'm running with David's sieve; thanks David. Jim has been a little quiet for a few days, so maybe he's on holiday?
2002/07/07 : Theoretical Algorithmic improvement! - In the last month, Bernhard Frey has been really dogged at trying to find shortcuts and optimisations. I think in total he's come up with 5 different ideas that might be useful. 4 of them I'd already thought of myself and turn out to not be useful. However, his latest is a stroke of genius. Pure simplicity. Pure brilliance. See below in the maths section.
2002/06/17 : The figures above say it all - as does this smiley :-D 10000T, 10000T, 10000T, 4300T. This is what we call progress! 65536 is going to have the last few drops squeezed out of it, and then we'll see what we can do with some of the other ranges.
2002/06/10 : Kimmo's returned some ranges, and 65536 is looking quite healthy. 0-6000T and 7000-10000T are done. We'll fill the gap, and we'll push it a bit further as this new algorithm is so fast at 65536.
2002/05/24 : No big news; it's going quite well. The anticipation of Kimmo's return is great - 65536 should soon be a very well sieved range indeed!
2002/05/15 : Sieving progresses. I left some machines on 131072 "too long", and they got to ~12000T :-) I'll upload them later today. I heartily recommend people to take a small 131072 range while Kimmo and I do 65536 further.
2002/05/09 : Kimmo's put more machines on 65536. By June we'll have the whole range to 16000T hopefully. Yup, 16000T. Big thanks to Kimmo. We haven't worked out if we should stop there or not. We'll make our mind up when we see what the removal rate is at that level.
2002/05/05 : I now know how far I can sieve the ranges and still be faster than the primality test! Due to my stoopid mistake, I got a p range incorrect on 2 of the 65536 files, which caused Kimmo to sieve at 30000T and 45000T rather than 3000T and 4500T. The candidate removal rates were ~6 minutes per candidate. Bearing in mind that only 1/50 of the numbers can actaully be tested, that still works out at 5 hours per testable candidate, and thus the cutoff point will be about HUGE. Kimmo's now corrected my mistake and is removing candidates 10 times more quickly...
2002/04/27 : New 131072 emergency ranges uploaded, all of 45-110k are usable, and some are very deep indeed. See here. It's not all good news. I'm out of a job next month, so my sieving will probably halve :-( . I guess I could buy myself a nice PC to cheer myself up... (welcome to the FatPhil school of managing your money). By the end of this weekend, 65536 will be at 2Q, 131072 and 262144 at 3Q - nice!
2002/04/24 : Change of plan! - Kimmo and I are going to try prime-band parallelisation of the 65536 sieve. I'll do 1Q5-3Q0, he'll do 3Q0 to 4Q5 and 4Q5 to 6Q0, and hopefully within 3 weeks we'll have reached 6Q (6000T) across the whole range! Wish us luck - note: it's a little hard to extract ranges while parallel sieving, as the files are on multiple sites and need to be merged. However, if you need a range just ask, and we'll see what we can do.
2002/04/21 : Kimmo Heranen has volunteered to help out with 65536
I hadn't originally planned to sieve that exponent, as I though I'd missed
the boat. However, with a few extra fast machines, he's doing some "emergency
sieving" to make sure that the next few range requests can be satisfied
with good candidates. My wide-sieving will take a few months to get to a
good level, so this was a very useful offer. Thanks, Kimmo.
2002/04/21 : I'm super-quintillious!
I may be supercillious too, but what I actually mean is that the entire
range for exponents 65536, 131072, 262144, and 524288 have been sieved to
1000000000000000!!! The middle two are over 2000T! This may sound impressive,
and in some ways is, but it's only scratching the surface. However, I'm happy,
as it's a psychological barrier that's been passed. You'll see the big grins
when I pass 5000T, and wild hoorahs when I reach 8000T!
Another hastily constructed page by Phil Carmody
Home /
Maths /
GFN Sieve /
news.html