Primzahlen

Einführung  

Da Visual Basic nicht gerade die "schnellste" Programmiersprache ist, sondern in diesem Bereich eher einen schlechten Ruf hat, spielt Algorithmus Optimierung eine große Rolle. Und das nicht nur in Visual Basic. Die Frage warum ich diese Programme nicht in C++ oder Assembler geschrieben habe, soll hier nicht behandelt werden, ist aber dennoch berechtigt. Wie gesagt kann man diese Programme auch in einem anderen Dialekt verfassen. Welches ich vielleicht nachreichen werde.

Die Rechenzeit ist natürlich noch stark von der Hardware des PCs abhängig. Ich besitze einen
700MHz AMD Athlon
256 MB RAM
Geforce 256 mit 32 MB RAM
20 GB Festplatte mit 5400 U/Min

Beispiele

Bevor wir uns mit dem Programmcode beschäftigen, sollten wir aber die Benutzeroberfläche erstellen. Dazu sollte uns klar sein, dass je umfangreicher die Funktionalität des Programms ist, desto langsamer und komplexer der Code wird; also wollen wir ein simples Programm. Eine Listbox für die Primzahlen, einen Commandbutton, eine Textbox zum Beinhalten der maximalen Primzahlen und eine Textbox zum Beinhalten der Zeitmessung. Das sollte ungefähr so aussehen:

Beispiel 1  

Dim i As Long, j As Long, test As Long
    xtime.Calibrieren            ' Sollte für uns keine Rolle spielen. Zum Berechnen
    xtime.Start                    ' der Zeit.
    For i = 1 To Text1.Text     ' Die Schleife testet von 1 bis zur Zahl von Text1.
        test = 0                ' Zum testen auf Primzahlen.
        For j = 2 To i - 1        ' Der Beginn des Hauptalgorithmus der auf Divisoren
            If i Mod j = 0 Then    ' testet und somit der Variable test den Wert Ja = 1
                test = 1        ' zuweist.
            End If
        Next j
        If test = 0 Then
            List1.AddItem I        ' Wenn nach dem Test immer noch kein Divisor
        End If                    ' gefunden wurde fügt das Programm die Variable
    Next I                        ' i zur Listbox hinzu.
    xtime.Halt                    ' Zum Zeitstoppen, aber ohne Bedeutung für uns.
    ShowTime (1)

Dieser Algorithmus sieht für den VB Anfänger schon recht "schnell" aus, ich werde Ihnen aber im Laufe dieses Tutorials das Gegenteil beweisen. Denn testen wir dieses Programm bis zu einer Zahl von 1000, so erhalten wir eine Rechenzeit von: 599,03 ms - was ca. einer halben Sekunde entspricht. Nun möchte ich Ihnen die Fehler in diesem Programm offenbaren. Dazu sollten wir das Programm analysieren.

• Der Code erstellt eine Schleife, die von eins bis zum Wert von Text1 geht.
• Die Variable test setzt die Primzahlenabfrage auf Wahr.
• Die folgende j- Schleife soll das Gegenteil beweisen und testet komplett durch.
• Konnte nicht das Gegenteil bewiesen werden, wird die Zahl als Primzahl akzeptiert.

In unserem Programm läuft die Hauptschleife gegen 1000, die innere Schleife immer gegen den Wert der Primzahl. Mathematisch heißt das für uns, dass unsere innere Schleife n*(n-2) mal durchlaufen wird. Das verwendete n steht für die Anzahl der zu berechnenden Primzahlen. Dazu noch eine Visual Basic-Informatikregel: Lesen wir den Endwert für die Schleife aus einem Objekt aus, so benötigt VB wesentlich mehr Zeit als aus einem festgelegten Wert oder einer Variable. Also legen wir nun die Variable "bis" fest, um den Endwert der Hauptschleife nicht aus der Textbox auszulesen. Der folgende Code sieht nun so aus:

Beispiel 2  

Dim i As Long, j As Long, test As Long, bis As Long
   xtime.Calibrieren
   xtime.Start
   bis = Text3.Text                'Dies ist die bisher einzige Änderung. Anstatt den 
   For i = 1 To bis                'Endwert der Schleife aus der Textbox zu lesen
       test = 0                    'nehmen wir in aus der Variable "bis".
       For j = 2 To i - 1
           If i Mod j = 0 Then
               test = 1
           End If
       Next j
       If test = 0 Then
           List3.AddItem i
       End If
   Next i
   xtime.Halt
   ShowTime (0)

Sehen wir nun, was sich tut. Wir erhalten eine Rechenzeit von: 305,78 ms, welches 50% der vorherigen Rechenzeit darstellt. Eine beträchtliche Beschleunigung unseres Codes. Aber das soll uns noch lange nicht genügen, den wir haben gerade erst begonnen. Eine kleine Sache fällt mir noch auf. Wenn wir den Codeteil:

If i Mod j = 0 Then
    test = 1
End If

Ändern zu:

If i Mod j = 0 Then test = 1

Ist die Rechenzeit nur noch 270,45 ms . Das liegt daran, dass Visual Basic nur nicht mehr aus 3 Zeilen sondern aus einer lesen muss. Das ist allerdings nicht viel, deshalb bauen wir eine Break Anweisung in die j- Schleife ein. Denn sobald die j- Schleife bewiesen hat, dass i keine Primzahl ist, rechnet die j- Schleife völlig umsonst weiter. Um diese Variation des Codes erneut mathematisch darzustellen, betrachtet man die innere Schleife. Allerdings ist es sehr schwer für den Code mit der Exit- For Anweisung eine Formel zu finden, da Primzahlen sehr unregelmäßig auftauchen. In konkreten Zahlen heißt das, wir haben die innere Schleife von 5070 auf 838 Schleifendurchläufe getrimmt. Genug um eine offensichtliche Optimierung des Codes zu erzeugen. Also bauen wir eine Break Anweisung ein.

Beispiel 3  

Dim i As Long, j As Long, bis As Long
Dim test As Boolean
    xtime.Calibrieren
    xtime.Start
    bis = Text1.Text
    For i = 1 To bis
        test = True
        For j = 2 To i - 1
            If i Mod j = 0 Then
                test = False
                Exit For                ' Das ist die Änderung die uns ganz besonders
            End If                    ' beschäftigen soll. In dem Zeitpunkt wo wir 
        Next j                    ' zwischen i und j einen Divisor gefunden haben
        If test = True Then            ' bricht die Schleife ab den weitere Berechnungen
            List1.AddItem I            ' sind nicht mehr von Nöten. So gewinnen wir 
        End If                    ' wesentlich mehr Zeit  in der j- Schleife.
    Next i
    xtime.Halt
    ShowTime (1)

Die Rechenzeit vermindert sich auf ganze: 61,21 ms .

Dadurch sind wir aber nicht mehr in der Lage die obere Verbesserung zu verwenden. Was uns aber egal sein sollte, da wir mehr Zeit gewinnen als durch die Verkleinerung der If... Then Verzweigung.

Wertzuweisungen machen unser Programm aber sehr langsam, deshalb verlassen wir uns auf die Optimierung via Modularisierung. Wir wollen uns eine Boolesche Funktion überlegen, um besser zu analysieren, ob die zu testende Zahl eine Primzahl ist oder nicht. Also schreiben wir uns die Funktion, die der j- Schleife sehr ähnlich ist.

Beispiel 4  

Private Function Primzahl(ByVal Prim As Long) As Boolean    ' Die Funktion liefert einen
    Dim i As Long                        ' Booleschen Wert zurück. Der 
    For i = 2 To Prim - 1                    ' Parameter Prim bildet die Basis 
        If Prim Mod i = 0 Then                    ' der Funktion. Ansonsten gilt die
            Primzahl = False                    ' Struktur der alten j- Schleife.
            Exit Function                        ' Prim stellt die zu testende 
        End If                            ' Primzahl dar, was aber klar sein
    Next I                            ' sollte.
    Primzahl = True
End Function

Die Hauptfunktion sieht dann so aus:

Dim i As Long, bis As Long
    xtime.Calibrieren                        ' Unwichtig
    xtime.Start                            ' Unwichtig
    bis = Text2.Text
    For i = 1 To bis
        If Primzahl(i) = True Then List2.AddItem I        ' Test auf Primzahl durch 
    Next I                            ' Boolesche Funktion.
    xtime.Halt                            ' Unwichtig
    ShowTime (2)

Durch diese Vorgehen erhalten wir eine neue Geschwindigkeit von 37,70 ms . In diesen Bereichen der Optimierung kommen wir langsam an unser Limit. So das wir unser Programm kaum noch programmiertechnisch ändern können. Also überlegen wir uns noch etwas auf der elementar mathematischen Ebene. Da (Insofern man in der Schule aufgepasst hat) wir gelernt haben, dass wir mit der Wurzel den Rechenaufwand verkürzen können bauen wir sie in die Funktion ein was dann so aussieht:

Beispiel 5  

Private Function Primzahl (ByVal Prim As Long) As Boolean
    Dim i As Long
    For i = 2 To Sqr(Prim - 1)                    ' Hier wird die Wurzel eingesetzt.
        If Prim Mod i = 0 Then
            Primzahl = False
            Exit Function
        End If
    Next i
    Primzahl = True
End Function

Und wieder einmal die Hauptfunktion, welche sich allerdings nicht geändert hat:

Dim i, bis As Long
    xtime.Calibrieren                        ' Unwichtig
    xtime.Start                            ' Unwichtig
    bis = Text2.Text
    For i = 1 To bis
        If Primzahl(i) = True Then List2.AddItem I        ' Test auf Primzahl durch 
    Next I                            ' Boolesche Funktion.
    xtime.Halt                            ' Unwichtig
    ShowTime (2)

Beim Testen ergibt sich ein Wert von: 16,84 ms .

Ein weiterer Einwand bezieht sich darauf, dass Primzahlen nie gerade sind. Sonst könnte man sie schließlich durch 2 teilen. Durch eine Änderung in der Hauptschleife, außerhalb der Funktion, können wir sicher ein paar Millisekunden einsparen. Dies gewährleistet die Step-Anweisung.

Beispiel 6  

Dim i As Long, bis As Long
    xtime.Calibrieren
    xtime.Start
    bis = Text6.Text
    For i = 1 To bis Step 2            'Hier fügen wir die Anweisung zum
        If Primzahl2(i) Then List6.AddItem I    'Überspringen der geraden Zahlen ein. 
    Next i
    xtime.Halt
    ShowTime (5)

Durch diese Änderung im Code gewinnen wir aber derart wenig Zeit, dass sich die Optimierung nur in Berechnungen bis 200000 deutlich macht. Hierzu die konkreten Werte:

Mit Berechnung der geraden Zahlen bis 200000: 3804,89 ms
Ohne Berechnung der geraden Zahlen bis 200000: 3687,32 ms

Im Vergleich dazu würden die vorherigen Algorithmen (die früheren wohl eher) abstürzen, oder unerträglich lange brauchen.

Beispiel 7  

Im nun vorliegenden Algorithmus habe ich einmal eine etwas andere Art verwendet um die Primzahlen zu berechen. Dazu verändere ich das Unterprogramm und erhalte eine Funktion vom Typ String:

Private Function prim(ByVal primzahl As Long) As String    'Funktion von Typ String
    Dim j As Long
    For j = 3 To Sqr(primzahl - 1) Step 2
        If primzahl Mod j = 0 Then Exit Function
    Next j
    prim = CStr(primzahl)                    'Konvertierung des 
End Function                                'Datentyps.

Hier die Hauptfunktion:

Dim i As Long, j As Long, bis As Long
Dim aufnahme As String
    bis = Text
    List.Clear
    xtime.Calibrieren
    xtime.Start
    For i = 1 To bis Step 2
        aufnahme = prim(i)                        'Nimmt Prim auf.
        If aufnahme <> "" Then List.AddItem aufnahme
    Next i
    xtime.Halt
    ShowTime (8)

Dies ist einmal eine ganz andere Technik um unser Ziel zu erreichen, zudem habe wir hier eine sehr effektive Technik erhalten. Die genauen Ergebnisse betrachten wir noch einmal gegen Ende des Tutorials. Der Zeitwert ist erst einmal: 9,35 ms .

Beispiel 8  

Kommen wir nun zu dem vorletzten Beispiel. Wobei ich einen Visual Basic typischen Aspekt ansprechen möchte: Die Benutzeroberfläche, oder auch Graphical User Interface. Jedesmal wenn wir eine Primzahl entdecken, aktualisiert unser Programm die Listbox. Das macht unseren Algorithmus nicht direkt langsam, dafür aber unser gesamtes Programm. Verstecken wir nun die Listbox und zeigen sie dann anschließend wieder an, aktualisiert das Programm die Listbox anstatt ca. 100- nur einmal. Sehen wir uns mal die Änderung in der Hauptschleife an:

Dim i As Long, bis As Long
    xtime.Calibrieren
    xtime.Start
    bis = Text7.Text
    List7.Visible = False    'Hier wird die Liste versteckt um das ständige Aktualisieren zu 
    For i = 1 To bis Step 2    'verhindern.
        If Primzahl2(i) = True Then List7.AddItem i
    Next i
    List7.Visible = True    'um unser Ergebnis zu betrachten müssen wir die Liste wieder
    xtime.Halt            ‚sichtbar machen.
    ShowTime (6)

Durch das Verhindern dieses Problems erhalten wir eine Zeit von: 7,40 ms . Welche eine gute Verbesserung des vorherigen Codes darstellt. Zu guter Letzt möchte ich eine ganz andere Struktur der Primzahlenberechnung ansprechen. Welche mit Hilfe von Tobias Franz entstanden ist. Dazu einen Exkurs über die Mathematik:

Beispiel 9  

Das Sieb des Eratosthenes von Kyrene (griechischer Mathematiker, ca. 276 bis ca. 194 v. Chr.) beschreibt ein praktikables Verfahren, aufeinanderfolgende Primzahlen, beginnend mit der Primzahl 2, der Größe nach bis zu einer beliebigen oberen Grenze N zu erzeugen. Angenommen, man sucht sämtliche Primzahlen, die kleiner als 200 sind. Dazu legt man eine Tafel mit den ersten 200 natürlichen Zahlen an, aus der zunächst alle Vielfachen von 2, außer der 2 selbst, herausgestrichen werden, dann alle Vielfachen von 3, außer der 3, dann alle Vielfachen von 5 (4 wurde als Vielfaches von 2 bereits gestrichen), anschließend alle Vielfachen von 7 (6 wurde als Vielfaches von 2 bereits gestrichen), usw. Zurück bleiben alle natürlichen Zahlen, die nur triviale Teiler, also die Zahl 1 und die Zahl selbst, besitzen und somit Primzahlen sind.

Eigentlich passt dieses Problem nicht ganz in das Thema der Algorithmus Optimierung. Ganz einfach aus dem Grund, weil wir unsere Struktur beibehalten wollen. Ich würde eher sagen Alternative Algorithmen. Diese Lösung hat mich aber dermaßen fasziniert, dass ich mich entschlossen habe es in das Tutorial aufzunehmen. Hier liefere ich den Code welcher aber ganz anders aufgebaut wurde:

Dim i As Long, bis As Long
    bis = Text7.Text
    Dim Sieb() As Boolean
    ReDim Sieb(bis + 1)
    For i = 0 To bis + 1
     Sieb(i) = True
    Next i
    
    Dim currentPrim, viel As Double
    currentPrim = 2
    
    While (currentPrim < (bis + 1) / 2)
     viel = currentPrim + currentPrim  'Vielfache initialisieren
     If Sieb(currentPrim) Then 'Ueberpruefen, ob mit einer Primzahl gesiebt wird, wenn ja:
       For i = 2 To bis + 1
         Sieb(viel) = False 'Vielfache heraussieben, das sind keine Primzahlen
         viel = viel + currentPrim
         If viel > bis + 1 Then Exit For
       Next i
     End If
     currentPrim = currentPrim + 1
    Wend
    Dim ColCount As Double
    ColCount = 0  'eine Spaltenzaehlvariable wird initialisiert.
     Dim intervallAnfang As Integer
     intervallAnfang = 2
    For i = intervallAnfang To bis + 1 ' { //gemaess d. Eingabe bis z. Ende ausgeben
      If Sieb(i) Then     'wenn es sich um eine Primzahl handelt.
       ColCount = ColCount + 1  'danach wird die naechste Spalte vorgemerkt,
       List7.AddItem i           ' //Die Primzahl ausgegeben
      End If
    Next i

Sollten wir aber die Primzahlen nur bis 1000 testen, ist Algorithmus 7 schneller als 8. Aber in höheren Regionen z.B. bis 200000 ergibt sich eine sichtbare Leistungssteigerung:

Algorithmus 7 bis 1000: 7,71 ms
Algorithmus 8 bis 1000: 8,20 ms
Algorithmus 7 bis 200000: 2601,47 ms
Algorithmus 8 bis 200000: 1160,14 ms

Bei diesem beeindruckendem Ergebnis sollte sich jeder selbst ein Bild machen. Ich denke, dass man noch ein paar Schritte weiter gehen kann, vielleicht mache ich das auch noch. Dies soll aber erst einmal genügen.

Fazit, Analyse  

Hier möchte ich noch einmal alle Zahlen auflisten, um noch einmal die Effektivität der einzelnen Algorithmen zu bewerten. Der kursive Wert ist immer die schlechteste Zahl und der fett gedruckte Wert immer die beste Zahl in dem angegebenen Bereich.

Als letzten Algorithmus habe ich noch unsere Stringroutine mit der Bildfunktion gekoppelt und bin gerade in den unteren Zahlenbereichen auf eine sehr gute Zeit getroffen. Im oberen Zahlenbereich ist aber das "Sieb des Eratosthenes von Kyrene" eine zu optimierte Routine für die anderen Algorithmen. Dennoch ist interessant, dass jeder einzelne von ihnen einen eigenen Charakter der Zeitentwicklung besitzt.

Nachwort  

Mit diesem Tutorial wollte ich zeigen das man seinen Code, egal welcher Dialekt, immer optimieren kann. Und natürlich auch wie man dieses Umsetzen kann. So ist man sogar in der Lage C++ Programme die wenig optimiert sind zu "überholen". Beigelegt zum Tutorial habe ich den Quellcode der Primzahlen Programme und ein C++ Programm auf der Stufe des 6ten Algorithmus. Erstaunt habe ich erkannt das Visual Basic gar nicht mal so lange für die Berechnung benötigt. Ich hoffe, dass ich eine eigentlich für Assembler typische Domäne auch Visual Basic-Programmierern näher bringen konnte. Ein weiterer interessanter Aspekt ist die Frage, ob die Zahlen 1 und 2 überhaupt Primzahlen sind, denn beide Zahlen sind nur durch 1 und durch sich selber teilbar. Gerade an solch, banalen, Fragen scheitern mache Mathematiker, was mich angeht, ich sehe sie als Primzahlen. Für Anregungen oder Kritik bin ich natürlich auch offen.
(Anmerkung der Redaktion: Die vom Autor verwendete Definition einer Primzahl ist irreführend. Eine Primzahl ist eine natürliche Zahl größer 1, welche nur durch 1 und sich selbst teilbar ist. Folglich ist die Zahl 1 keine Primzahl.)

Projekt als Download [58082 Bytes]

Ihre Meinung  

Falls Sie Fragen zu diesem Tutorial haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.