Das Sieb des Eratosthenes

Eine ungerade ganze Zahl N ist eine Prim­zahl, wenn sie nicht durch ihre un­ge­ra­den Vor­gän­ger {3,5,..,N-2} teil­bar ist. Da­zu ei­ne Ada-Spie­le­rei als schie­rer Selbstzweck.

Es soll hier nicht etwa ein neuer Prim­zahl­zwil­ling ge­fun­den wer­den - nein, es soll schlicht der obi­ge Al­go­rith­mus mit Sprac­hmit­teln der Pro­gram­mier­spra­che Ada modelliert werden - wie ge­sagt, der schie­re, aber schö­ne Selbst­zweck.

Wie könnte man das Problem elegant angehen?

Eleganz schließt hier aber auch die prak­ti­sche Nutz­lo­sig­keit ein, denn für we­nig Rech­ne­rei wä­re der Ver­wal­tungs­auf­wand doch er­heb­lich - nichts des­to­trotz!

Eine zu überprüfende Zahl N wird durch eine Ket­vte von Tasks ge­schickt, je eine Task für je eine Prim­zahl, wobei jede Task über­prüft, ob die ein­ge­gan­ge­ne Zahl ein Viel­fa­ches der ei­ge­nen Prim­zahl ist; ist sie das, wird die ein­ge­gan­ge­ne Zahl ver­wor­fen und die näch­ste Zahl ent­ge­gen ge­nom­men; ist sie kein Viel­fa­ches, wird sie an die näch­ste Task wei­ter­ge­reicht. Die Tasks fil­tern oder eben sie­ben also den ein­ge­hen­den Strom an Zah­len.

Die Kette wird aufgebaut, indem mit den Zah­len 3,5,7,9,.. be­gon­nen wird. Die Task am je­wei­li­gen En­de der Ket­te er­zeugt dy­na­misch eine wei­te­re Task für die näch­ste Primzahl mit einem zu­ge­hö­ri­gen Puf­fer. Als letzte zu über­prü­fen­de Zahl wird schließ­lich die Zahl N in die Rohrleitung ('pipe­line') ge­schickt.

Damit sich das Task-System ans­tän­dig ver­ab­schie­den kann, wird ei­ne 0 als Kenn­zei­chen durch die Task-Kette geschickt als Bot­schaft, dass die Ar­beit getan ist und sich die einzelnen Tasks nun ver­ab­schie­den kön­nen.

Vom Hirn in die Hand

Für die siebenden Tasks wird ein Task-Typ Sie­ve_­Task_­Type de­fi­niert: Jede Task wird ein Ein­gangs­puf­fer, der CPU-Kern, auf dem sie ab­lau­fen soll, und die Prio­ri­tät übergeben.

Neue Task­ob­jek­te wer­den mit­tels ei­ner task-­ex­ter­nen Funk­tion (Zei­len 58-59) er­zeugt ('Task­fabrik'). Im Taskrumpf selbst kön­nen neue Task­in­stan­zen nicht direkt mittels eines 'new Sieve_­Task_­Type' dy­na­misch er­zeugt wer­den ("task type cannot be used as type mark within its own spec or body").

Im Rumpf des Task-Typen wird gleich ein Aus­gangs­puf­fer be­reit­ge­stellt, der auch Ein­gangs­puf­fer für das nächste, noch zu er­zeu­gen­de Task­objekt sein wird.

Die allererste Zahl, die eine Sieb-Task dann aus dem In­put_­Buf­fer (Zeile 15) erhält, ist ihre 'ei­ge­ne' Prim­zahl.

Wird nun die nächste Primzahl gefunden, so wird so­gleich ei­ne neue Task er­zeugt (Zeile 56) und da­bei der neu­en Task der Ein­gangs­puf­fer mit über­ge­ben - der Aus­gangs­puf­fer der ak­tu­el­len Task­in­stanz ist der Eingangspuffer der näch­sten Task in der Task-­Kette.

Die neue Task erhält auch sogleich ihre ei­ge­ne Prim­zahl (Zei­le 58) über den Aus­gangs­puf­fer mit­ge­teilt.

Anschließend werden neue Zah­len zur Über­prü­fung ent­ge­gen ge­nom­men (Zeile 63). Falls eine 0 da­bei ist, wird aus der Schlei­fe aus­ge­stie­gen (Zei­le 65). Die Überprüfung findet in Zeile 67 statt. Prim­zahl-Kan­di­da­ten werden in der Zeile 70 wei­ter­ge­reicht.

Noch einmal nachgedacht

Eine spannende Geschichte - viel besser als Su­do­ku. Solch ei­ne sie­ben­de Task und der ihr zu­ge­ord­ne­te Aus­gangs­puf­fer ge­hö­ren ei­gent­lich zu­sam­men - könnte man meinen. Ich habe die bei­den zu einem Kettenglied ('chain member') zu­sam­men­ge­fasst. Die Ket­ten­glie­der werden dann mit­tels Zei­ger (in Ada-Sprache: über Zu­griffs­ty­pen) zu ei­ner Ket­te verbunden:

Die Task und der Puffer werden zu ei­nem Ver­bund-Ty­pen, zu ei­nem Record, na­mens Sieve_­Chain_­Member_­Type zu­sam­men­ge­fasst. Die Da­ten­struk­tur referenziert sich selbst, da der Task ein Zei­ger auf den Behälter mittels einer Dis­kri­mi­nan­te über­ge­ben wird. Ein nütz­li­ches Kon­strukt!

Auf die Puffer kann auf zwei­er­lei Wei­se zu­ge­grif­fen wer­den: Die ak­tu­el­le Task greift über den Zei­ger Chain_­Mem­ber auf ih­ren Ein­gangs­puf­fer zu, die Task, die diesen Behälter erzeugt, ver­wen­det ei­nen Zei­ger auf diesen Be­häl­ter, um Zu­griff auf den Aus­gangs­puf­fer zu erhalten.

In der Anwendung sieht das dann mit den Zeile 61 und 67 so aus:

Es funktioniert,  ja im Prinzip

Für N=2*6400 klappte das Programm auf mei­nem Vier-Kern-Rech­ner noch, bei N=3*6400 stieg es aus. Ich habe nur die Prim­zahl­zwil­linge auf die Kon­so­le aus­gegeben:

Es funktioniert? Ja, aber ...

Eine neue Erfahrung für mich: Wäh­rend der Ent­wick­lung stieg das Pro­gramm des öf­te­ren gleich nach dem Starten aus - of­fen­sicht­lich kann es leicht zu 'Wett­renn­be­din­gun­gen' (ra­ce con­di­tion) kom­men, dann steht eine Ressource noch nicht zur Verfügung, wenn sie be­nutzt wer­den soll. Solche Wettrennen traten etwa auf, wenn man ein Sieb-Taskobjekt gleich im De­kla­ra­tions­teil er­zeug­te.

Oder: Am Ende aller Konsolenausgaben sollten die Sieb-Tasks ein­mal die Meldung aus­ge­geben, der Be­nut­zer möge bitte den Wa­gen­rück­lauf aus­lö­sen. Da­zu habe ich eine globale ato­ma­re Va­ri­ab­le Done spen­diert, die nach der ersten Meldungs­aus­ga­be auf Fal­se wird, womit wei­te­re Aus­ga­ben un­ter­blei­ben sollten. Nun denn: Anfänglich gab es ge­nau 2 Aus­gaben.

Hinweis: Die Zeilennummern stim­men nicht un­be­dingt mit denen in den obi­gen Code-Aus­schnit­ten überein.

•  Der Quellcode, gezippt    Mein GNAT-Projekt (1)

•  Der Quellcode, gezippt    Mein GNAT-Projekt (2)

•  GNAT-Ada-Compiler        von AdaCore

Das gute, alte Buch

John Barnes
Programming in Ada 2005
Addison-Wesley, 2006

Alan Burns, Andy Wellings
Concurrent and Real-Time Programming in Ada 2005
Cambridge University Press, 2007

Dank an die drei Herren!