Primzahlen

Die Berechnung von Primzahlen ist nur eine von vielen verschiedenen Möglichkeiten, um die Leistung von Programmen zu vergleichen.
Alle hier vorgestellten Beispiele wurden so ähnlich wie möglich programmiert.

Zum Vergleich kann man u.a. diese Daten verwenden:
Rechenzeit, Datei-Größe, Aufwand zur Installation, Portabilität, Sicherheit.
Zeitbedarf und Kosten der Programmierung sind von den verfügbaren Kenntnissen abhängig.
Quelle: Wikipedia (modif.)
Primzahlen lassen sich trotz intensiver Suche nach einem Algorithmus nicht berechnen sondern 'nur' suchen bzw. testen.

Der hier verwendete Algorithmus zur systematischen Suche nach Primzahlen wurde von Eratosthenes von Kyrene (Έρατοσθένης) ca. 300 Jahre vuZ. entdeckt und nach ihm benannt:
Sieb des Eratosthenes. Der Algorithmus (Rechen-Vorschrift) ist bei Wikipedia gut dokumentiert.

Es gibt auch andere Primzahlen-Such-Algorithmen, dieser ist jedoch am bekanntesten und wird oft für Trainings-Beispiele verwendet.

Browser-Daten (HTML-Quelltext)

• Die vom Browser erhaltenen Daten werden auch mit einem Menü-Befehl des Browsers und/oder mit Rechtsklick in die Webseite angezeigt. In den Beispielen werden die Primzahlen bis 100 berechnet und angezeigt: Der HTML-Quelltext enthält die jeweiligen Ergebnis-Zahlen. Einzig der Quelltext der Javascript-Version enthält keine Ergebnisse, weil diese Live mit → DOM-Methoden eingetragen werden.

Programm-Quelltext

Der C/C++ Quelltext ist weder am Server noch am Client-PC verfügbar, sondern nur am Entwicklungs-PC. Er wird hier nur ausnahmsweise angezeigt:   primzahlen.txt
Perl-Quelltext:   primzahlen.pl
PHP-Quelltext:   primzahlen.php
Die C/C++, Perl- und PHP-Programme sind zur Ausführung auf die Zusammenarbeit mit einem Webserver angewiesen.
Javascript-Quelltext:   primzahlen.html
Einzig das Javascript-Programm kann man am eigenen PC speichern und unabhängig vom Betriebssystem an jedem gängigen PC verwenden.

Programmierung der Beispiele


Ergebnisse

Dieser Abschnitt wird nur dann angezeigt, wenn bereits ein Auftrag bearbeitet wurde.
Er enthält eine Liste aller gefundenen Primzahlen.
Diese Liste kann sehr lang sein. Daher wird die Zusammenfassung ausnahmsweise nicht - wie üblich - erst nach der Berechnung angezeigt, sondern schon oberhalb, wo sie besser sichtbar ist.
Die Übertragung der Ergebnisse vom Server zum Arbeits-PC und der Aufbau der Webseite brauchen für dieses Beispiel meist mehr Zeit als die Berechnung. Das gilt nicht für die professionelle Berechnung riesiger Primzahlen.

übergabe der Zusammenfassungs-Daten

Nach Berechnung der Ergebnisse folgt ein weiteres <script>-Element, in dem die Zusammenfassung der Ergebnisse von der jeweiligen Programmiersprache an globale Javascript-Variable übergeben wird.

onload-Ereignis

Dieses Ereignis (Event) des <body>-Elements tritt nach dem vollständigen Laden der Webseite ein. Zu diesem Zeitpunkt sind alle Ergebnisse berechnet. Sie werden mit einer einfachen Javascript-Funktion vom Ende der Webseite in den Abschnitt der Zusammenfassung kopiert.



Die Primzahlen-Beispiele sind in einem Punkt abweichend programmiert:

Da die Liste der Ergebnisse sehr lang werden kann, wird die Zusammenfassung oberhalb der Liste angezeigt.

Die Daten der Zusammenfassung sind noch nicht bekannt, wenn dieser Teil der Webseite erzeugt wird. Daher sind einige zusätzliche Maßnahmen notwendig:

• Die Daten der Zusammenfassung werden am Ende der Webseite in unsichtbare HTML-Elemente eingetragen, wie z.B. in ein <script>-Element.
• Im Quelltext der Seite muss ein kleines Javascript-Programm enthalten sein, welches die Ergebnis-Daten liest und in den sichtbaren Abschnitt kopiert.
• Das Javascript-Programm muss nach dem vollständigen Laden der Webseite automatisch ausgeführt werden, d.h. mit dem onload-Ereignis des <body>-Elements.

Diese Abweichung von der Standard-Programmierung wurde in Kauf genommen, weil einem guten User-Interface in diesem Fall Priorität gegenüber der einfachen Programmierung eingeräumt wurde.



Javascript erfordert - abgesehen von einem Browser - überhaupt keine Resourcen. Man kann sogar auf Netzwerk und Webserver verzichten und die in einer Webseite (*.html) enthaltenen Programme am eigenen Client-PC ausführen.
Javascript-Programme kann man transportieren (USB-Stick, Mail, ...) und auf jedem (!) beliebigen PC ausführen.

Quelltext-Dateien der Programmiersprachen → C/C++ (*.c   *.cpp) werden bereits am Entwickler-PC in ausführbare Programme (Windows: *.exe) übersetzt.
Man muss für jedes Betriebssystem eigene ausführbare Programme erzeugen. Diese laufen besonders schnell, sind jedoch nur auf (Server)-PC der gleichen Betriebssysteme übertragbar.
Ein Browser am eigenen Arbeits-PC kann derartige Programme nicht verwenden.
Änderungen sind nur im Quelltext möglich. Danach muss man alle Programm-Versionen neu übersetzen (compilieren) und auf die jeweiligen Webserver transportieren.



Vorteile:
Der Server-PC wird schon bei 1maliger Anforderung entlastet: Die Javascript-Version ist in einer statischen Text-Datei enthalten, daher kann der Server die Datei sofort senden, ohne vorher Programme auszuführen.
Wiederholte Anforderungen betreffen den Server überhaupt nicht.
Am Client-PC fällt die Ladezeit nur 1mal an.
Jede (weitere) Berechnung erfolgt am eigenen PC mit sehr hoher Geschwindigkeit, vergleichbar mit jener von C/C++, jedenfalls weit schneller als mit typischen Server-Programmen.

Nachteile:
Die geringe Sicherheit wird oft angeführt: Man kann Javascript-Programme kopieren oder manipulieren. Allerdings trifft dieser Nachteil auf typische Rechen-Programme nicht zu, denn durch Manipulation kann man sich nur selbst schaden.


Mit einem durchschnittlichen PC kann man in ca. 30 Minuten alle Primzahlen bis zu 10 Dezimalstellen berechnen. Das entspricht etwa der Primzahl (2^31-1), die von Leonhard Euler im Jahr 1772 gefunden wurde - lediglich mit Bleistift & Papier. Die Berechnung aller Primzahlen bis zu 13 Stellen würde mit PC ca. 1 Monat dauern, bis zu 14 Stellen ca. 1 Jahr.

Die größte bis 2016 öffentlich bekannte Primzahl
274207281 - 1
hat mehr als 22 Mio Dezimalstellen.

Zeitnehmung


Grenzen

Der Algorithmus verlangt, dass zur Prüfung einer Zahl alle kleineren (vorher gefundenen) Primzahlen verfügbar sind. Der Bedarf an Speicherplatz steigt daher kontinuierlich mit der Größe der untersuchten Zahlen.

Die Programme fordern den benötigten Arbeitsspeicher vom Betriebssystem an.
Wenn der benötigte Arbeitsspeicher fehlt oder verweigert wird, dann kann es je nach PC schon bei 2...20 Mio Primzahlen zu Fehlermeldungen kommen, im Extremfall sogar zum Absturz der Beispiel-Programme.

Der Absturz eines Webserver-Hilfsprogramms (z.B. Primzahlen-Berechnung) kann eine Verzögerung des Webservers hervorrufen, sollte jedoch keinesfalls zu dessen Störung führen.

Wenn man nur wenige Ergebnisse (Primzahlen) anfordert, dann wirken sich einmalige Effekte (Initialisierung) stärker aus. Daher sinkt zunächst die durchschnittliche Rechenzeit pro Primzahl. Mit zunahmender Größe der Zahlen wird der Algorithmus allerdings immer langsamer, so wie zu erwarten ist.


Arbeits-(Client)-PC

Die Wartezeiten am Arbeits-PC rechtfertigen keine Entscheidung für eine der Programmiersprachen, soferne die Berechnung nicht wesentlich aufwändiger ist als in diesem Beispiel.
Die 'Schmerzgrenze' von 1 Sekunde wird mit Perl oder PHP erst bei ca. 100000 ... 10 Mio Primzahlen erreicht, mit C++ oder Javascript bei ca. 1 Mio ... 100 Mio Primzahlen.



Die Lösung mit Javascript ist für ein typisches Rechenprogramm wie das hier gezeigte Beispiel mit großem Abstand überlegen:
Die (geringe) Rechenzeit fällt nämlich nicht am Server-PC an, sondern am jeweiligen Arbeits-(Client)-PC. Dadurch vervielfacht sich die Rechenleistung des gesamten Systems aus Server + Clients.
Sauber programmierte Javascript-Lösungen sind unbeschränkt portabel. Lediglich auf Resourcen des Servers (Datenbanken) kann man damit nicht direkt zugreifen sondern nur mit → AJAX.

Mit C++ programmierte Lösungen laufen mit maximaler Geschwindigkeit, d.h. fast so wie mit Maschinensprache (Assembler) programmiert.
Dem steht der hohe Aufwand zur Herstellung und Änderung von C++ Programmen gegenüber. Sie sind darüber hinaus nur sehr begrenzt portabel: Man muss für jedes Betriebssystem eine eigene Version herstellen.
C++ Programme werden oft als Konsolen-Programme erstellt und verzichten daher auf Grafik und User-Interface.

Script-Programme wie Perl oder PHP sind typisch 10..100mal langsamer als C++ oder Javascript-Programme. Sie sind jedoch viel einfacher herzustellen oder zu ändern.
Die Portierung auf beliebige andere Server ist bei sauberer Programmierung problemlos.
Die Sicherheit ist für normale Anwendungen zufriedenstellend, setzt allerdings gute System-Administration und saubere Programmierung voraus.