Seventeen or Bust
Van DPC wiki
Consult the User's Guide for information on using the wiki software.
Inhoud |
[bewerk] Algemeen
[bewerk] Doel van het project
[bewerk] Wat is Seventeen-or-Bust?
De SoB-cliënt zorgt ervoor dat jouw computer meedoet aan een wiskundig project met als doel het bewijs leveren dat 78557 het kleinst bestaande Sierpinski getal is en daarmee tevens de oplossing is voor het Sierpinski probleem. Om te begrijpen wat een Sierpinski getal is, moet je eerst weten wat priemgetallen zijn en wat samengestelde getallen zijn.
Priemgetallen: Een priemgetal is een getal groter dan 1 dat alleen deelbaar is door 1 en zichzelf en een geheel getal als uitkomst heeft. 11 is een priemgetal, want het kan alleen gedeeld worden door 1 en 11 indien de uitkomst een geheel getal moet zijn. 12 is geen priemgetal, want het kan gedeeld worden door 1, 2, 3, 4, 6 en 12 en toch nog een geheel getal als uitkomst hebben. Samengestelde getallen: Een samengesteld getal is het product van één of meerdere priemgetallen. Elk getal wat geen priemgetal is, is een samengesteld getal.
[bewerk] Maar wat is nu een Sierpinski getal en wat is het 'probleem'?
Stel:
- k is een positief oneven getal (1, 3, 5, 7 …)
- n is een positief geheel getal (1, 2, 3, 4 …)
Als je voor k een waarde vindt waarbij (k * 2^n) + 1 als uitkomst altijd een samengesteld getal geeft dan heb je een Sierpinski-getal gevonden.
Anders gezegd. Als het resultaat van deze berekening nooit priemgetallen zijn (voor elke n dus) dan is een k een geldig Sierpinski getal.
Het Sierpinski probleem is het zoeken naar een sluitend bewijs dat je het kleinste Sierpinski getal gevonden hebt. Van sommige Sierpinski getallen kan de juistheid bewezen worden en de kleinste is 78557. Maar er zijn 39276 oneven gehele getallen tussen 0 en 78557. Hoe zit het daar dan mee?
Wiskundigen hebben een heel sterk vermoeden dat 78557 echt het allerkleinste Sierpinski getal is. Maar een sluitend bewijs hier voor vinden, is een tweede. De enige manier om dit te bereiken, is om te bewijzen dat alle oneven gehele getallen kleiner dan 78557 geen Sierpinski getallen zijn. In begin 2002 waren op 17 getallen na, alle mogelijkheden uitgesloten. De 17 overgebleven getallen waren:
4847, 5359, 10223, 19249, 21181, 22699, 24737, 27653, 28433, 33661, 44131, 46157, 54767, 55459, 65567, 67607 en 69109.
De rode k waarden zijn de resterende 6 in voortgang. Zie de onderste tabel op de SoB statistiek pagina voor de Current Test Ranges ter beoordeling van de huidige voortgang.
[bewerk] Hoe kan je deze laatste 17 getallen nu elimineren?
Om te bewijzen dat deze 17 getallen geen Sierpinski getallen zijn, pakken we één van deze 17 getallen, vullen deze als k in in de formule (k * 2^n) +1 en verhogen we n terwijl we controleren of de uitkomst een priemgetal is. Als één enkele uitkomst een priemgetal is, dan is die k-waarde geen Sierpinski getal en kunnen we hem van de lijst van 17 overgebleven getallen halen. Als alle getallen een keer een priemgetal als uitkomst opleveren, dan is het probleem opgelost en blijft 78557 het kleinst bewezen Sierpinski getal.
Echt een probleem voor Distributed Computing dus. Het project heeft sinds 2002 al aardig wat resultaat geboekt, want van de 17 overgebleven kandidaten zijn er reeds 11 uitgeschakeld te weten:
46157 (27-nov-2002)
65567 (03-dec-2002)
44131 (10-dec-2002)
69109 (10-dec-2002)
54767 (25-dec-2002)
5359 (15-dec-2003)
28433 (02-jan-2005)
27653 (15-jun-2005)
4847 (19-okt-2005)
19249 (05-mei-2007)
33661 (30-okt-2007)
Het aantal overgebleven kandidaten komt daarmee op 6.
[bewerk] Worden alle nog openstaande k-waarden getest bij elke waarde van 'n'?
Nee, een deel van de mogelijke n-waarde is al getest voor aanvang van dit project en naast het het werk wat de SoB-cliënt doet, ook het proth-testing of PRP-ing genoemd zijn er ook subprojecten te weten Factoring en Sieving. Bij deze subprojecten wordt door middel van ontbinden in factoren getracht kandidaat k/n-paren te elimineren die geen priemgetal opleveren. Deze subprojecten hebben samen eigen stats die niet als DPCH gepost worden. Voor Sieving wordt Prothsieve of Sobsieve gebruikt en voor Factoring wordt SBFactor gebruikt. Het is de bedoeling van de organisatie om deze subprojecten te integreren in het hoofdproject met één client en één statspagina.
[bewerk] Wie is de organisatie achter dit project?
Het project is opgezet door Louis Helm, student aan de universiteit van Michigan en David Norris, medewerker aan de universiteit van Illinois. In maart 2002 begonnen zij tezamen met het project waarna het al snel door de DC community werd opgenomen en velen er werk van hebben gemaakt. De belangrijkste zijn Michael Garrison, computer consultant, die de noodzakelijke hosting heeft geregeld en George Woltman die razendsnelle code heeft gemaakt. Hier kan je wat meer over deze 3 personen lezen.
[bewerk] Client
[bewerk] Wat zijn de systeemeisen voor dit project?
- De SoB-cliënt gebruikt niet veel geheugen. Het exacte aantal kan fluctueren en ligt tussen de 10 en 50 MB.
- <5 MB vrije ruimte op je harde schijf voor het programma zelf, daarbij komt nog een temporary file voor iedere test. Naarmate de n-waarde toeneemt, neemt het ook ietsje meer HD-ruimte in beslag maar met 10MB moet je een een Quad Core makkelijk van 4 tests kunnen voorzien.
- Een internetverbinding om testen op te halen en te versturen.
- Eén van de volgende besturingssystemen: Windows, Linux, FreeBSD 4.x/5.x, Mac OS X.
[bewerk] Hoe moet ik mij aanmelden voor dit project?
Om je aan te melden voor SoB kun je onderstaand stappenplan volgen:
1) Ga naar de SoB website. Kies een unieke username, dit is de publieke referentie naar je account. In de stats van het project zul je onder deze naam verschijnen. Vervolgens heb je de mogelijkheid om je echte naam in te vullen. Deze naam is prive informatie en zal nergens op de site verschijnen. Hij zal enkel gebruikt worden door de organisatie. Tot slot wordt er gevraagd om een geldig email adres. Je email zal enkel gebruikt worden om je eenmalig je wachtwoord door te seinen. Het zal niet gebruikt worden voor SPAM doeleinden en zal nimmer worden doorgegeven tenzij het moet van de wet in de VS.
2) Zodra je dit wachtwoord ontvangen hebt log in je in op de website en klik je in het linkermenu bovenaan op "Preferences". Vervolgens klik je onder "Team Affilation" op 'click here' en volg je de stappen om DPC te joinen.
3) Pas eventueel andere instellingen aan en log uit.
4) Download de client voor jouw OS en kies de juiste installatie (GUI/service, zie volgende paragraaf).
5) Vul de bij stap 1 gekozen username in (eventueel kun je bij de windows client als Team naam DutchPowerCows invullen zodat je rechtstreeks naar de DPC pagina doorgelinkt wordt (dit is echter optioneel en niet voldoende om lid te worden van DPC, zie daarvoor stap 2)).
[bewerk] Hoe installeer en configureer ik de cliënt?
Per 18 maart 2009 is er een nieuwe client (zie hieronder een ruwe copy/paste van de seventeenorbust website
http://www.seventeenorbust.com/download/
Latest News !! BRAND NEW CLIENT SOFTWARE !! (posted by louis helm) Wednesday, 18 Mar 2009
Prime95 client for SB Seventeen or Bust users can now run a specially configured version of Prime95 directly on our server!
This represents a huge step forward in terms of speed and efficiency so we're recommending that anyone with previous versions of SB migrate to the new software.
Major Enhancements
- Mac OS X (intel) clients now available!
- Full multi-core support
- 64-bit processor support
- 15% faster per thread than SB v2.5.0
- P-1 factoring (with cEM credit for factors)
- Separate network thread - no delays
- Now communicates on port 80
- 98.2% less network traffic
- Better save-file handling (no registry keys in windows!)
Remember though, this is not a "drop-in" replacement for previous SB clients. This is brand new software. So even if you're a current user, you still have to follow the instructions in "Step 3" on the download page. Also, if your current version of SB is about to finish a full test, try to let it complete before removing SB because you can't migrate workunits.
Windows, Mac OS X, and Linux clients are all available now so Download and setup the new client!
Special thanks to George Woltman whose work made this release possible.
And drop by the forums if you run into any trouble or have questions about the new client. Thanks for your continued support and for crunching SB!
Download de laatste stabiele cliënt van de officiële site of een beta van het forum
[bewerk] Wat zijn de mogelijkheden van de cliënt?
Wil iemand dit invullen...
[bewerk] Stats
[bewerk] Waar kan ik de stats vinden?
Dagelijks worden de statistieken gepost op ons forum alwaar ze voorzien worden van commentaar: http://gathering.tweakers.net/forum/list_topics/5. Tevens worden er problemen gemeld indien die op voorhand bekend zijn. Het is ook de locatie waar je terecht kunt met vragen en opmerkingen.
Wil je zelf stats bouwen dan kun je de tab-seperated stats hier vandaan halen: http://www.seventeenorbust.com/stats/textStats.mhtml (Pas wel op met 'teveel' downloaden (meer dan 48 keer per dag) zodat je niet wordt geblocked voor 48 uur. Eventueel kun je contact opnemen met de organisatie om jezelf op een whitelist te laten zetten).
[bewerk] Kunnen er subteams gevormd worden bij dit project en zo ja hoe?
Er is een mogelijkheid om subteams te maken. Om een subteam te starten moet je een naam bedenken, en deze naar een van de statsbouwers (QiK SoB stats: http://sob.qik.nl en/of Speedkikker SoB stats: http://tadah.mine.nu/?prefix=sob ) mailen of op GoT posten.
Voor de QiK sob stats kan iedere user zichzelf registreren en een subteam uitkiezen. Speedkikker heeft de voorkeur voor een bericht in de shoutbox. Het is ook mogelijk de statsbouwers direct te benaderen via mail/messenger of een post op GoT. N.b. onderling worden de users regelmatig rechtgetrokken, meestal 1 keer in de week.
Onthoud dat zodra je lid bent van een subteam jouw persoonlijke stats verdwijnen. Op beide statssites wordt je wel in het subteam zelf vermeld zodat er toch nog persoonlijke stats zijn.
Vergeet niet dat deze mogelijkheid alleen op bovengemoende stats beschikbaar is, op de officiele site zul je hier dus niets terug vinden van deze subteams.
[bewerk] Hoe worden de punten geteld?
Een test is onderverdeeld in een aantal blokken. Een blok heeft nu de waarde van ongeveer 250McEM. Het aantal blokjes in een test (of WU) is afhankelijk van de n-waarde van de test: een test met een n-waarde van ~6 miljoen bevat ~1200 blokjes en is dus ongeveer 0.3TcEM waard. Een test met een n-waarde van ~14 miljoen bevat ~12000 blokjes en is dus ongeveer 3TcEM waard.
Hier volgt (een nog te vertalen) uitleg:
"cEMs are the pronouncable acronym for corrected Exponentiation Modulus's. To understand the origin of this unit, you have to understand a little about the origin of SB. Historically, the first versions of SB (v0.1 - v0.90) used GMP as an underlying math lib. Anyone involved with SB back in April 2002 might remember the first month or so where we simply used EMs (http://web.archive.org/web/20020731004953/www-personal.engin.umich.edu/~lhelm/primes/oldskool/). An EM was equal to one pass through the squaring (exponentiation) and modulus loop in the original GMP versions of SB. When we had vital systems of SB working, we went back and decided to redefine the work measurement. This is because the speed of the EM is not constant or linear with respect to the input size. The larger the number under test becomes, the longer a single EM takes. For GMP, the steps supposedly grow as O(n ln n) the input length of the numbers. However, we found that the FFT multiplication routines in GMP were dominated by many sub-routines which ran in O(n^2) time. Therefore, we added a correction factor and redefined EMs as cEMs. Specifically, the forumula to calculate cEMs for an entire test is:
cEMs = n^2 / 1 billion. (n^3/10E9 for current n values).
cEMs were great. They worked really well.
Now, fast forward half a year later. George Woltman appoaches the SB team. He offers his math routines from PRP which are highly superior to GMP's more general routines. We integrate PRPs routines but don't immediately change units. However, the unit should probably change for several reasons. For one, PRP techincally doesn't even do a modulus operation anymore... making it a little inappropriate for the unit itself to refer to modulus'. [For those interested, the modulus is done "for free" as a side-effect of the discrete weighted transforms used to square numbers.] Also, the routine is not O(n^2)... it's closer to O(n ln ln ln n). So to make things even more confusing, it turns out the PRP routines are not only faster, they also "slow down slower" as the size of their inputs increases. This means that cEMs artifically inflate slightly as test sizes increase.
Currently, Dave has isolated specific test points in the database which we are using to create a new unit the doesn't skew over time. Unless something changes, cEMs will eventually be replaced by Flops (Floating-Point Operations). Once an appropriate correction factor is decided on, Flops will replace cEMs. EMs made sense for a month. cEMs made sense for a couple more months. And now, Flops make sense going forward so we'll change as soon as possible... making this entire question on the FAQ only a depreciated curiosity. "
Explanation by Louie
Sinds v0.9.8 is het 100McEMs per blok.
Sinds v0.9.9 is het 250McEMs per blok.
[bewerk] Algemeen goed leesvoer
Uitleg Sierpinksigetallen[1]
Wiki over priemgetallen [2]
Prothsearch.net (technischer info) [3]
