Optimierung einer Primzahlfunktion

hans mans · Beiträge: 38 Win XP, SuSE 10.0 D7 Pers, D2005 Pers

Oh Mist... Hab irgendwie übersehen, das es mehrere Seiten gibt :oops:

Naja, ich glaub mein Programm is doch gegenüber den hier genannten anderen Lösungen sehr langsam. Genaue Messwerte hab ich aber nicht.

Tilo · Verfasst: Mi 13.07.05 09:20

hans mans hat folgendes geschrieben:

Also ich hätte hier ein (wenn auch sehr einfaches) recht schnelles Programm:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:

Program primzahlen;
{$APPTYPE CONSOLE}

uses
  SysUtils;

Const max = 1000000;
Var primzahl    : Array[1..max] Of Integer;
    ergebnis    : Boolean;
    zahln,index : Integer;
    testzahlen  : Array[1..max] Of Integer;
    
Procedure primtest(testzahl : Integer);
Var zaehler : Integer;
Begin
  ergebnis := false;
  If (testzahl<3) Then exit;
  zaehler := 1;
  Repeat
    zaehler := zaehler + 1;
    If (testzahl Mod zaehler) = 0 Then ergebnis := true  
                                  Else ergebnis := false;
  Until (ergebnis) Or (zaehler >= SQRT(testzahl))
End;

Begin
  index := 1;
  For zahln := 2 To max Do
  Begin
    primtest(zahln);
    If Not(ergebnis) Then
    Begin
      primzahl[index] := zahln;
      index := index + 1
    End
  End;
  For zahln := 2 To max Do testzahlen[zahln] := zahln;
  For zahln := 1 To index-1 Do
    Begin
      Write(primzahl[zahln]:8);
      If zahln Mod 5 = 0 Then Writeln
    End;
  Readln
End.

Das wichtige ist, dass bei dem Programm nicht geprüft, ob die zu testende Zahl durch jede kleinere Zahl, sondern nur durch jede Primzahl, die kleiner ist, als die zu testende Zahl.

zur der letzten Behauptung: Nein
Den Zähler mit dem zu testest wird in deinem Code immer 1 erhöht. Dadurch testest du die Zahl auf Teilbarkeit mit allen Zahlen bis zur Wurzel. Du muss den Zähler schon aus deinem Feld der gefundenen PRimzahlen auslesen.

Weitere Verbesserung für den Int64 Bereich (2^64) reicht es ein Feld bis zur Zahl 2^32 auf zu bauen. Alle Primzahlen, die größer als 2^32 sind werden nicht benötigt um den gesamten int 64 Bereich abzudecken, es sein denn man möchte Zahlen größer als 2^64 testen.

FinalFantasy · Verfasst: Mi 13.07.05 14:40

Hallo,

Ich hab mich auch schonmal mit Primzahlberechnung beschäftigt, allerdings hab ich das damals noch mit C (ohne ++) gemacht. Ich bin zu ähnlichen Ergebnissen gekommen, wie ihr hier.
ABER: Was mir gerade so durch den Kopf geschossen ist (da ich seit kurzem einen P4 mit HT habe), könnte man das ganze parallelisieren? So dass das ganze auch mehrere (logische oder physische) CPUs nutzt? Da man die gefundenen Primzahlen ja speichert und zum überprüfen wieder benötigt, ist eine Aufteilung nach dem Motto CPU1 rechnet von 0 bis 100, CPU2 rechnet von 101 bis 200 nicht mehr möglich.
Ausserdem würden mich mal Ergebnisse auf einem 64Bit System interessieren. Da ja hier massiv mit INT64 oder ähnlichem gerechnet wird, sollte doch ein 64-Bit System deutliche Geschwindigkeitsvorteile bringen.

hans mans · Beiträge: 38 Win XP, SuSE 10.0 D7 Pers, D2005 Pers

Oh, Mist... :oops:

Auch noch falsches Programm gepostet...

Phantom1 · Beiträge: 390

@hans mans: ich habe deinen Code mal getestet: für 10 mio testzahlen, braucht dein code über 94 sekunden (ohne ausgabe der primzahlen). Zum vergleich, schau mal auf Seite 6 (weiter unten auf der seite), dort findest du ein Code von mir, welcher weniger als 0,3 sekunden für 10 mio testzahlen braucht :wink:

getestet mit CPU: AthlonXP-M@2000mhz

ManuelGS · Verfasst: Mi 13.07.05 16:31

den code kannst du noch schneller machen, wenn du die wurzelfunktion selbst schreibst, so dass sie nur eine ganzzahl zurückliefert. bis jetzt sind es ja zig stellen nach dem komma...
das implementieren überlass ich den mathematikern...

_________________
"Leben ist gänzlich Bühne und Spiel; so lerne denn spielen
und entsage dem Ernst - oder erdulde das Leid." - Palladas von Alexandria

Gekko · Beiträge: 49 Win XP, Vista Visual C# Express, Python Ruby

www.hardtware.de/products/braingrid.php
Habt ihr das schon gesehen?

enyaw_ecurb · Beiträge: 16

8 Seiten zum Durchlesen, ganz schön lang.

Ich hab noch ein paar Ideen für die Leute, denen die Programme immer noch nicht schnell genug
sind.

Wenn man beim Sieb des Erastothenes die Vielfachen einer Zahl wegstreichen will, kann
man davon ausgehen das alle noch nicht weggestrichenen Zahlen bis zum Quadrat dieser Zahl Primzahlen sind.
Z.B.:
Alle Vielfachen von Zwei werden weggestrichen, nächste Primzahl anvisiert, die 3
und alle ungeraden Zahlen bis zur 9 sind Primzahlen.
Das bringt bei großen Zahlen einen nicht erheblichen Speed-Kick.

Außerdem kann man, was ich bei meinem Programm gemacht hab, die Primzahlen in einem Boolean
Array speichern. Man streicht die Zahlen weg indem man den Wert auf 1 oder halt eben 0 setzt.
Das Problem liegt bei der Ausgabe. Man kann zwar die Anzahl der Primzahlen sehr gut
feststellen, aber bei der Ausgabe wird die Zeit wieder rausgeholt.
Es bringt halt eben nur vom Speicher was, besonders wenn man es Bitweise packt.

Ich vermute das ihr das irgendwo in diesen 8 Seiten bestimmt schon erwähnt habt und
falls ich irgendetwas wiederhole tut es mir Leid.

PS: Mein Programm schafft die Primzahlen bis 100 Millionen in 2,7 Sekunden und hat bei
Bitweiser Speicherung einen Verbrauch von 10MB. (AthlonXP 2200+)

Tilo · Verfasst: Do 14.07.05 10:13

enyaw_ecurb hat folgendes geschrieben:

Wenn man beim Sieb des Erastothenes die Vielfachen einer Zahl wegstreichen will, kann
man davon ausgehen das alle noch nicht weggestrichenen Zahlen bis zum Quadrat dieser Zahl Primzahlen sind.
Z.B.:
Alle Vielfachen von Zwei werden weggestrichen, nächste Primzahl anvisiert, die 3
und alle ungeraden Zahlen bis zur 9 sind Primzahlen.

Die bisher geposteten schnellen Programme/Routinen verwenden eine abgewandelte und schnellere Form des Siebes. Die gefundenen Primzahlen werden in ein Array gespeichert. Zutestende Zahlen werden nun auf Teilbarkeit mit Primzahlen bis zur Wurzel der zutestenden Zahl geprüft.Wenn keine teilbarkeit, dann neue Prim. Bei Teilbarkeit wird sofort abgebrochen und es kann die nchste Zahl getestet werden. Dieses Verfahren ist bis jetzt das schnellste gewesen.

BEi Vielfachen "wegstreichen" hast man ein Problem. Erst werden z.b. alle Vielfache von 7 weggestrichen, dann alle von 11. Da ergibt sich ein unnützer Aufwand durch die Vielfachen von 77.(jede 11. Zahl bei Eleminieren von x7 werden nochmals beim Eleminieren von x11 bearbeitet.)

Phantom1 · Beiträge: 390

Tilo hat folgendes geschrieben:

Die bisher geposteten schnellen Programme/Routinen verwenden eine abgewandelte und schnellere Form des Siebes. Die gefundenen Primzahlen werden in ein Array gespeichert. Zutestende Zahlen werden nun auf Teilbarkeit mit Primzahlen bis zur Wurzel der zutestenden Zahl geprüft.Wenn keine teilbarkeit, dann neue Prim. Bei Teilbarkeit wird sofort abgebrochen und es kann die nchste Zahl getestet werden. Dieses Verfahren ist bis jetzt das schnellste gewesen.

BEi Vielfachen "wegstreichen" hast man ein Problem. Erst werden z.b. alle Vielfache von 7 weggestrichen, dann alle von 11. Da ergibt sich ein unnützer Aufwand durch die Vielfachen von 77.(jede 11. Zahl bei Eleminieren von x7 werden nochmals beim Eleminieren von x11 bearbeitet.)

Welche geposteten Routinen meinst du? von GTA-Place?, er benutzt kein Sieb.

Die schnellsten bisher hier geposteten Routinen waren die nach dem Sieb des Erathotenes.

@enyaw_ecurb: nicht schlecht nur 2,7 sekunden für 100 mio testzahlen. Könntest du den Code posten? ich würde gern wissen wie du das gemacht hast. Zum vergleich: mein code braucht dafür etwa 4 sekunden.

mfg
Phantom1

ScorpionKing · Beiträge: 1150 Win XP

2,7 Sekunden! :shock:

Das ist doch verdammt schnell! Geht das überhaupt?

_________________
Aus dem Urlaub zurück!

enyaw_ecurb · Beiträge: 16

Korrektur:
Ich habe einen AthlonXP 2800+ mit 2200Mhz, habs vertauscht.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

while i < bisw do           //Wurzel von bis                                          
begin                                                                 
i := i+i + 2*i*i;             //Das Quadrat von i ausrechnen, hab ich oben erklärt
 while i < bis do                                                 
 begin                                                            
  if Primfeld.bits[i] = false then
  begin
  Primfeld.bits[i] := true;  
  l := l+1;
  end;
  i := i + x;                                                 
 end;                                                             
i := z + 1;                                                           
 while Primfeld.bits[i] = true do                                 
 begin
 i := i+1;                                                           
 end;                                                             
z := i;                                                               
x := i+i+1;                                                           
end;

Der Code ist nicht wirklich optimiert, ich meine vom Syntax her, da ich kein
sonderlich guter Delphi-Programmierer bin.
Wichtig ist, dass mein Feld nur die Ungeraden enthält und mit 0 beginnt, d.h. Index No 1
ist Zahl 3. i+i+1 entspricht der wirklichen Zahl von i. l zählt die Primzahlen, bzw.
l zählt welche Zahlen keine sind und bei der Ausgabe muss subtrahiert werden.
x enthält immer die wirkliche Zahl von i.

Bei der Ausgabe der Zahlen muss natürlich mit i+i+1 umgewandelt werden und
deshalb dauert das ein wenig länger.

Zusätzlich ist mir noch eingefallen, dass man noch ein paar Stempel benutzen kann,
hat glaube ich noch niemand erwähnt.
Hier ist ziemlich gut erklärt was Stempel sind:

www.devalco.de/sieb_des_Ulam.htm

Bei meiner Variante wäre ein Stempel zu umständlich, da die Indexberechnung ja schon ohne
die Vielfachen von zwei kompliziert ist.

Falls ich irgendwelche Fehler oder Wiederholungen eingebaut hab tuts mir wie gesagt
Leid.

Moderiert von raziel: Code- durch Delphi-Tags ersetzt.

Phantom1 · Beiträge: 390

@enyaw_ecurb: danke für den Code, leider bekomme ich ihn nicht zum laufen!

Hier dein Code, so wie ich ihn verwenden wollte:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

procedure SavePrimes1(MinPrime, MaxPrime: Cardinal; const FileName: String = '');
var                                  //
  i, l, x, z: Cardinal;
  SL: TStringList;
  Primfeld: TBits;
begin
  Primfeld:=TBits.Create;
  Primfeld.Size:=MaxPrime;
  i:=0; l:=0; x:=0; z:=0;
  while i < Trunc(Sqrt(MaxPrime)) do begin          //Wurzel von bis
    i:=i+i + 2*i*i;             //Das Quadrat von i ausrechnen, hab ich oben erklärt
    while i < MaxPrime do begin
      if Primfeld.bits[i] = false then begin
        Primfeld.bits[i] := true;
        l:=l+1;
      end;
      i:=i+x;
    end;
    i:=z+1;
    while Primfeld.bits[i] = true do
      i:=i+1;
    z:=i;
    x:=i+i+1;
  end;

  //
  // Ausgabe
  //

  Primfeld.Free;
end;

Wozu dient die Variable l ? auf diese wird in dem Code nicht mehr zugegriffen.

mfg
Phantom1

Tilo · Verfasst: Do 14.07.05 17:05

Phantom1 hat folgendes geschrieben:

Welche geposteten Routinen meinst du? von GTA-Place?, er benutzt kein Sieb.

Die schnellsten bisher hier geposteten Routinen waren die nach dem Sieb des Erathotenes.

Die schnellen Codes verwenden alle ein Array, in dem die bisher gefundenen Primzahlen gespeichert werden. Nur diese Zahlen werden dann bei Primzahlentest berücksichtigt. Das ist meiner Meinung nach eine abgewandelte Form des Siebes des Erathotenes. Da werden ja auch Vielfache der Primzahlen eleminiert.

enyaw_ecurb · Beiträge: 16

Ich bin schon ein Trottel, muss ich natürlich dazusagen:

x:=drei, l:=null, i:=eins, z:=drei

dann müsste es eigentlich laufen.
Wegen der Variable l zählt einfach die Primzahlen mit.
Steht eigentlich schon oben...
Brauchst du bei der Ausgabe. Es gibt soundsoviele Primzahlen im Zahlenraum von...

Tilo · Verfasst: Do 14.07.05 17:18

Phantom1 hat folgendes geschrieben:

@enyaw_ecurb: danke für den Code, leider bekomme ich ihn nicht zum laufen!

Hier dein Code, so wie ich ihn verwenden wollte:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

procedure SavePrimes1(MinPrime, MaxPrime: Cardinal; const FileName: String = '');
var                                  //
  i, l, x, z: Cardinal;
  SL: TStringList;
  Primfeld: TBits;
begin
  Primfeld:=TBits.Create;
  Primfeld.Size:=MaxPrime;
  i:=0; l:=0; x:=0; z:=0;
  while i < Trunc(Sqrt(MaxPrime)) do begin          //Wurzel von bis
    i:=i+i + 2*i*i;             //Das Quadrat von i ausrechnen, hab ich oben erklärt
    while i < MaxPrime do begin
      if Primfeld.bits[i] = false then begin
        Primfeld.bits[i] := true;
        l:=l+1;
      end;
      i:=i+x;
    end;
    i:=z+1;
    while Primfeld.bits[i] = true do
      i:=i+1;
    z:=i;
    x:=i+i+1;
  end;

  //
  // Ausgabe
  //

  Primfeld.Free;
end;

Wozu dient die Variable l ? auf diese wird in dem Code nicht mehr zugegriffen.

mfg
Phantom1

Durch Optimierung wird Zeile 15 übersprungen. i bleibt immer 0. Endlosschleife.

BenBE · Verfasst: Do 14.07.05 17:48

i wird in Zeile 19 initialisiert.
Zeile 15 ist nur für die Zählung der Primzahlen zuständig.

Insgesamt kann man an der Routine kaum noch was optimieren.

BTW: Du nutzt bereits einen 2er-Stempel.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

enyaw_ecurb · Beiträge: 16

Exakt, ich benutze schon einen 2-Stempel.
Ich meinte nur, dass man noch größere Stempel benutzen kann.
Das Programm ecprime von Walisch Kim hat einen Stempel, der
die Vielfachen von 2,3,5,7,11 und 13 eliminiert und schafft die Primzahlen
bis 1 Milliarde auf meinem Rechner in 0,4 Sekunden!!

ScorpionKing · Beiträge: 1150 Win XP

enyaw_ecurb hat folgendes geschrieben:

Exakt, ich benutze schon einen 2-Stempel.
Ich meinte nur, dass man noch größere Stempel benutzen kann.
Das Programm ecprime von Walisch Kim hat einen Stempel, der
die Vielfachen von 2,3,5,7,11 und 13 eliminiert und schafft die Primzahlen
bis 1 Milliarde auf meinem Rechner in 0,4 Sekunden!!

ich habe die selbse funktion ausprobiert. bei mir brauch die 4 sek!

_________________
Aus dem Urlaub zurück!

Phantom1 · Beiträge: 390

@enyaw_ecurb: So, jetzt konnte ich deinen Code mal direkt vergleichen, dein Code braucht bei mir 5,4 sekunden für 100 mio testzahlen (ohne ausgabe). Somit ist dein Code leider doch langsamer als meiner (bei mir 3,7 sekunden für 100 mio testzahlen). Schade eigentlich, ich dachte ich könnte meinen Code noch verbessern.

EDIT: zeitwert korrektur

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme