Abgabe Effiziente Programme WS04/05

Sie können ein beliebiges Beispiel wählen. Wer nicht unbedingt etwas anderes vorhat, soll dieses Jahr ein Programm zum Zählen von Primzahlen entwickeln und optimieren. Und zwar sollen Primzahlen bis 20.000.000.000 gezählt werden können.

Für diese Aufgabe gibt es mindestens zwei Algorithmen:

Sieb des Erathostenes: Da die zu zählenden Zahlen nicht alle auf einmal in das RAM passen, wird man das Sieb wohl in mehrere Stücke aufteilen müssen. Das Byte-Sieve.
Das Inklusions/Exklusions-Prinzip: ist etwas schneller, aber dafuer kann man sich die Primzahlen nicht ausgeben lassen.

Diese beiden Algorithmen werden als separaten Klassen gewertet (für den Wettbewerb um das effizienteste Programm). Um zu ermitteln, ob ihre Ergebnisse Richtig sind, hier einige Zahlen (p(x) ist die Anzahl der Primzahlen von 2 bis x):

x            p(x)
10^6 	    78,498
10^7 	   664,579
10^8 	 5,761,455
10^9 	50,847,534
10^10  455,052,511

Natürlich können Sie, wenn Sie wollen, auch die Implementierung eines anderen Problems optimieren; allerdings hat das einige Nachteile: Sie müssen einen Teil der Zeit Ihrer Präsentation für die Erklärung des Problems und des Algorithmus aufwenden, und die Ergebnisse sind nicht direkt vergleichbar.

Bereiten Sie eine 15-20-minütige Präsentation vor. Da Sie dabei nicht soviel Zeit haben wie ich in der Vorlesung, präsentieren Sie die meisten Schritte nur im Überblick (also eventuell nur, wieviel er gebracht hat), und nur ein paar besonders interessante Schritte mit mehr Details. Besonders interessant sind u.a. die Schritte, die unerwartet viel oder wenig bringen.

Um einen Vergleich zwischen den verschiedenen Lösungen zu ermöglichen, messen Sie mit papiex oder perfex auf der b3 die Zyklen für Ihre verschiedenen Varianten.

Aufgaben vom [WS02/03 | WS03/04]

Anton Ertl