Optimierung einer Primzahlfunktion

enyaw_ecurb · Beiträge: 16

Irgendwie komisch,
bei euch kommen ganz andere Zeiten raus.
Ich hab beides noch mal überprüft und die Zeiten von oben stimmen.
Liegt wohl an der Taktrate oder meine Uhr ist kaputt.
Eigentlich schade...

Phantom1 · Beiträge: 390

Ja, durch die verschiedenen Taktraten kommen auch unterschiedliche Zeiten raus. Wenn man aber alles auf einem Rechner testet, kann man es gut vergleichen. Für die Zeitmessung verwende ich QueryPerformanceCounter() im RealTime-Modus.

GTA-Place · Verfasst: So 07.08.05 09:15

Hab mal bisschen weitergeforscht und nochmal ne knapp eine Sekunde gespart, wenn ich als Rückgabewert Byte statts Boolean nehme (0 oder 1).

EDIT: Nach der Hilfe wird Booelan als Byte gespeichert und deshalb ist es ein bisschen langsamer, da das ja praktisch so aussehen würde:

markieren

Delphi-Quelltext

1:
2:
3:
4:

if Prim = True then
  Prim := 1
else
  Prim := 0;

Direkte Zuweisung ist dann ein bisschen schneller.

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

GTA-Place · Verfasst: So 07.08.05 11:36

Hab grad ne Funktion für das Sieb des Es.... geschrieben.
Wenn die Zahlen stimmen, dann ist diese Funktion über 10 Sekunden schneller!
Für 20.000.000 Zahlen statt 16 Sekunden nur noch 5 Sekunden.

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

Phantom1 · Beiträge: 390

Zum vergleich braucht meine optimierte Version funktion (nach dem Sieb d. E.) für 20 mio testzahlen nur 0,6 sekunden :wink:

Es gibt aber noch viel schnellere Algorythmen, dagegen ist unserer Code ziemlich langsam *g

mfg
Phantom1

GTA-Place · Verfasst: So 07.08.05 12:04

Ich hol dich auch noch ein ^^ Nur noch 3 Sekunden.

EDIT: 2 Sekunden :-)

EDIT: 1 Sekunde

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

Phantom1 · Beiträge: 390

Damit du selbst besser vergleichen kannst (da wir ja unterschiedliche Rechner haben), hier mein aktueller Code:

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:

procedure SavePrimes(MinPrime, MaxPrime: Cardinal; const FileName: string = '');
var
  isPrime: array of Cardinal;
  i, j: Cardinal;
  SL: TStringList;
begin
  SetLength(isPrime, MaxPrime shr 5);
  isPrime[0]:=$00000003; // bit 0 und 1 ist keine primzahl

  for i:=2 to Trunc(Sqrt(MaxPrime)) do
    if isPrime[i shr 5] and (1 shl (i mod 32)) = 0 then begin
      j:=i*i;
      while j<=MaxPrime do begin
        isPrime[j shr 5]:=isPrime[j shr 5] or (1 shl (j mod 32));
        Inc(j, i);
      end;
    end;

  if FileName<>'' then begin
    SL:=TStringList.Create;
    try
      for i:=MinPrime To MaxPrime do
        if isPrime[i shr 5] and (1 shl (i mod 32)) = 0 then
          SL.Add(IntToStr(i));
      SL.SaveToFile(FileName);
    finally
      FreeAndNil(SL);
    end;
  end;
end;

mfg
Phantom1

GTA-Place · Verfasst: So 07.08.05 12:44

Meine Funktion braucht jetzt auch 0,6 Sekunden (ohne das ich deine gesehen habe).
Ich mach jetzt mal ein Test mit deiner.

EDIT:
Deine: 0,9 Sekunden
Meine: 0,6 Sekunden

Wenn man mal mit meiner letzten vergleicht: 16 Sekunden -> 0,6 Sekunden = 96% schneller.

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

Phantom1 · Beiträge: 390

Ich würde den Code gerne mal sehen, wenn du nix dagegen hast :wink:

mfg
phantom1

GTA-Place · Verfasst: So 07.08.05 14:35

Klar, war bis jetzt immer OpenSource hier, allerdings versuch ich noch was zu optimieren.
Source gibts spätestens heute Abend.

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

GTA-Place · Verfasst: So 07.08.05 18:17

So hier der Source:

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:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:

var
  Start:    Single;
  Ende:     Single;
  ZList:    Array of Byte;
  CheckSch: Integer;
  NrCount:  Integer;
  PosCount: Integer;
  Zahl:     Cardinal;
  Max:      Cardinal;
  PrimF:    TStringList;
begin
  if (not (TryStrToInt(VonEdit.Text, Von))) OR
     (not (TryStrToInt(BisEdit.Text, Bis))) OR
     (Von < 0) OR (Bis < 0) OR (Von > Bis) then
  begin
    ShowMessage('Ungültige Eingabe(n)!');
    Exit;
  end;

  Max := (Bis div 2) + 1;
  SetLength(ZList, Max);

  PrimLab.Caption := 'Überprüfe Zahlen...';
  Application.ProcessMessages;

// ************************************************************************** //

  Start := GetTickCount;

  PosCount := 0;
  for CheckSch := Von + 1 to Bis + 1 do
  begin
    if odd(CheckSch) then
    begin
      ZList[PosCount] := 1;
      inc(PosCount);
    end;
  end;

  PosCount := 0;
  for CheckSch := 3 to Trunc(sqrt(Bis)) do
  begin
    if odd(CheckSch) then
    begin
      if ZList[PosCount] = 1 then
      begin
        Zahl    := CheckSch;
        NrCount := ((Zahl * Zahl) - 3) div 2;

        while (NrCount <= Abs(Max)) do
        begin
          if ZList[NrCount] = 1 then
            ZList[NrCount] := 0;
          inc(NrCount, Zahl);
        end;
      end;

      inc(PosCount);
    end;
  end;

  Ende := GetTickCount;
  DauerLab.Caption := 'Diese Überprüfung hat ' +
                      FloatToStr((Ende - Start) / 1000) +
                      ' Sekunden gedauert.';
  Application.ProcessMessages;

// ************************************************************************** //

  PrimF := TStringList.Create;

  if Von < 3 then
    PrimF.Add('2');

  PosCount := 0;
  for CheckSch := 3 to Bis do
  begin
    if odd(CheckSch) then
    begin
      if ZList[PosCount] = 1 then
        PrimF.Add(IntToStr(CheckSch));

      inc(PosCount);
    end;
  end;

  PrimF.SaveToFile('Paket.prim');
  PrimF.Free;

  PrimLab.Caption := 'Fertig. Warte auf Eingabe...';
end;

Statistiken:

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

Phantom1 · Beiträge: 390

Dein Code berechnet nur die hälfte der Testzahlen :!:

Also schau bitte nochmal nach.

mfg
Phantom1

GTA-Place · Verfasst: So 07.08.05 18:44

Oh, da ist wohl grad was schief gelaufen. Einen Moment...

EDIT: Finde den Fehler erstmal nicht und bin ab Morgen ja weg, also werde ich in einer Woche weitersuchen.
Ich bitte euch erstmal keinen Source mehr zu posten bzw. meinen zu verbessern und die Diskussion bis zu meiner Rückkehr einzustellen. Danke!
(Ich mags nicht, wenn man an so einem wichtigen Thema ohne mich diskutiert :wink:

)

EDIT2: Fehler gefunden und verbessert. Source oben.

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

Phantom1 · Beiträge: 390

@GTA: dein Code ist tatsächlich schneller ;O) allerdings solltest du beachten, das die komplette Zeit inkl dem speicher reservieren und freigeben gemessen werden sollte!

Ich konnte es so natürlich nicht lassen und hab mich nochmal rangesetzt, diesmal benutze ich einen 30er Stempel (auch Bit-komprimiert wie mein bisheriger Code) das spart schonmal eine menge RAM. Ich hab den Code jetzt zwar noch nicht auf schnelligkeit optimiert, aber das resultat ist trotzdem nicht schlecht ;O)

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:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:

procedure SavePrimes(MaxPrime: Cardinal; const FileName: String = '');
const
  Stempel: array[0..7] of Byte = (1, 7, 11, 13, 17, 19, 23, 29);
var
  isPrime: array of Byte;
  i, j: Cardinal;
  f: TextFile;

  procedure PrimSieve(n, nbit: Cardinal);
  var Num, Num2, m, mbit: Cardinal;
  begin
    Num:=n*30+nbit;
    Num2:=Num*Num;

    mbit:=Num2 mod 30;
    m:=(Num2-mbit) div 30;

    for Num2:=Num to Trunc(MaxPrime/Num) do begin
      case mbit of
        1: isPrime[m]:=isPrime[m] or 1;
        7: isPrime[m]:=isPrime[m] or 2;
       11: isPrime[m]:=isPrime[m] or 4;
       13: isPrime[m]:=isPrime[m] or 8;
       17: isPrime[m]:=isPrime[m] or 16;
       19: isPrime[m]:=isPrime[m] or 32;
       23: isPrime[m]:=isPrime[m] or 64;
       29: isPrime[m]:=isPrime[m] or 128;
      end;
      Inc(m, n);
      Inc(mbit, nbit);
      if mbit>29 then begin
        Dec(mbit, 30);
        Inc(m);
      end;
    end;
  end;

begin
  SetLength(isPrime, Trunc(MaxPrime/30));

  for j:=1 to 7 do
    PrimSieve(0, Stempel[j]);

  for i:=1 to Trunc(Sqrt(MaxPrime)/30) do
    for j:=0 to 7 do
      if isPrime[i] and (1 shl j) = 0 then
        PrimSieve(i, Stempel[j]);

  if FileName<>'' then begin
    AssignFile(f, FileName);
    try
      ReWrite(f);
      WriteLn(f, '2');
      WriteLn(f, '3');
      WriteLn(f, '5');
      for i:=1 to 7 do
        WriteLn(f, IntToStr(Stempel[i]));
      for i:=1 To Trunc(MaxPrime/30) do
        for j:=0 to 7 do begin
          if i*30+Stempel[j]>MaxPrime then
            Break;
          if isPrime[i] and (1 shl j)=0 then
            WriteLn(f, IntToStr(i*30+Stempel[j]));
        end;
    finally
      CloseFile(f);
    end;
  end;
end;

Hier der direkte Vergleich:

bei 20 mio testzahlen:
GTA-Place Code: 526ms (RAM-Verbrauch: 9,5 MB)
mein alter Code: 583ms (RAM-Verbrauch: 2,4 MB)
mein neuer Code: 303ms (RAM-Verbrauch: 0,6 MB)

bei 100 mio testzahlen:
GTA-Place Code: 2889ms (RAM-Verbrauch: 47,7 MB)
mein alter Code: 3621ms (RAM-Verbrauch: 11,9 MB)
mein neuer Code: 2404ms (RAM-Verbrauch: 3,2 MB)

bei 500 mio testzahlen:
GTA-Place Code: 15765ms (RAM-Verbrauch: 238,4 MB)
mein alter Code: 20896ms (RAM-Verbrauch: 59,6 MB)
mein neuer Code: 14207ms (RAM-Verbrauch: 15,9 MB)

Die zeiten wurden wie immer im RealTime-Mode gemessen und mit hilfe vom RDTSC (ist noch etwas genauer als der QueryPerformanceCounter). CPU = AtlhonXP-M@2000MHz

So langsam machen wir ja fortschritte ^^ aber an ecprime kommen wir noch lange nicht ran (ecprime braucht bei 500 mio testzahlen nur lächerliche 230ms !).

PS: Ich habe spaßeshalber mal mit meinem Programm alle primzahlen bis 2^32 gespeichert, die Datei war anschließend 2,2 GB groß :shock:

mfg
Phantom1

alzaimar · Verfasst: Mi 17.08.05 20:51

Und ich hab die Performance nochmal um ca 60% eingedampft :mrgreen:

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:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:

procedure AlzSavePrimes(MaxPrime: Cardinal; const FileName: String = '');
const
  Stempel: array[0..7] of Byte = (1, 7, 11, 13, 17, 19, 23, 29);
  P2 : Array [0..7] of byte = (1,2,4,8,16,32,64,128);
var
  isPrime: array of Byte;
  i, j: Cardinal;
  f: TextFile;

  procedure PrimSieve(n, nbit: Cardinal);
  Const
    Mods : Array [0..29] of Byte = (0 , 0, 0, 0, 0, 0, 2, 0, 0, 0,
   4, 0, 8, 0, 0, 0,16, 0,32, 0,0, 0,64, 0, 0, 0, 0, 0, 0,128);

  var Num, Num2, m, mbit: Cardinal;
  begin
    Num:=n*30+nbit;
    Num2:=Num*Num;

    mbit:=Num2 mod 30;
    m:=(Num2-mbit) div 30;

    for Num2:=Num to MaxPrime div Num do begin
      isPrime[m]:=isPrime[m] or mods[mbit];
      Inc(m, n);
      Inc(mbit, nbit);
      if mbit>29 then begin
        Dec(mbit, 30);
        Inc(m);
      end;
    end;
  end;

begin
  SetLength(isPrime, Trunc(MaxPrime/30));

  for j:=1 to 7 do
    PrimSieve(0, Stempel[j]);

  for i:=1 to Trunc(Sqrt(MaxPrime)/30) do
    for j:=0 to 7 do
      if isPrime[i] and p2[j] = 0 then
        PrimSieve(i, Stempel[j]);

  if FileName<>'' then begin
    AssignFile(f, FileName);
    try
      ReWrite(f);
      WriteLn(f, '2');
      WriteLn(f, '3');
      WriteLn(f, '5');
      for i:=1 to 7 do
        WriteLn(f, IntToStr(Stempel[i]));
      for i:=1 To Trunc(MaxPrime/30) do
        for j:=0 to 7 do begin
          if i*30+Stempel[j]>MaxPrime then

            Break;
          if isPrime[i] and (1 shl j)=0 then
            WriteLn(f, IntToStr(i*30+Stempel[j]));
        end;
    finally
      CloseFile(f);
    end;
  end;
end;

[edit]den Rat von Phantom1 befolgt und 54 in 64 verbessert[/edit]

Phantom1 · Beiträge: 390

@alzaimar: ich hab den code zwar noch nicht probiert, aber ein fehler ist vorhanden: In der P2 Array deklariation, da steht bei dir 54, es müsste aber 64 sein.

EDIT:
So hab den Code jetzt getestet: er ist leider 15% langsamer. Ist eigentlich auch logisch, da ein zugriff auf ein Array länger dauert als ein direktes "case of".

alzaimar · Verfasst: Mi 17.08.05 21:50

Lustig, bei kleinen N (10000000 M) ist mein Algo ca. doppelt so schnell.
Bei N=32000000 ist der Unterschied am Deutlichsten, hier ist meine Variante um 60% Schneller.
Aber dann: Bei N=80000000 sind beide Varianten gleich schnell, aber dann wird meine Variante langsamer...

Lustig, liegt das an der Sprungvorhersage (Case-Anweisungen werden als if then-Ketten codiert), oder woran? Vielleicht kann man das ja rauskriegen?

Ansonsten, wirklich Schade.

Edit: Ich hab mal ein kleines Vergleichsprogramm mit TChart geschreben, das das Laufzeizverhalten der beiden Algorithmen vergleicht. Man sieht ganz deutlich einen Knick im zeitlichen Verlauf bei etwa 32.Mio.

Einloggen, um Attachments anzusehen!

Phantom1 · Beiträge: 390

In dem Mods Array sind auch noch falsche werte, so sollte es aussehen:

markieren

Delphi-Quelltext

1:	Mods: Array [0..29] of Byte = (0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 4, 0, 8, 0, 0, 0, 16, 0, 32, 0, 0, 0, 64, 0, 0, 0, 0, 0, 128)

Zumdem wäre es besser dieses Array schon direkt bei SavePrimes als const zu deklarieren, weil sonst das Array bei jedem durchlauf von PrimSieve neu angelegt werden muss.

Hier mal ein paar neue ergebnisse:

bei 1 mio testzahlen:
mein Code: 11ms
von dir modifizierter Code: 7ms

bei 32 mio testzahlen:
mein Code: 631ms
von dir modifizierter Code: 600ms

bei 100 mio testzahlen:
mein Code: 2431ms
von dir modifizierter Code: 2442ms

bei 500 mio testzahlen:
mein Code: 14282ms
von dir modifizierter Code: 15177ms

alzaimar · Verfasst: Do 18.08.05 16:59

Ich habe mein Testprogramm auf meinem Athlon 64bit 3000+ getestet, und da ist meine Routine auch bei 500 Mio Testdaten noch schneller, und zwar auch bei 500 Mio (15800 zu 12200 ms, oder knapp 35% schneller)...

Also liegt es an der Adressierung bei den 'kleinen' CPU und nicht am Algo. Wenn man jetzt das Bitarray in jeweils ca. 1MB grosse Stücke unterteilt, dürfte diese Macke der CPU ausgehebelt werden.

F34r0fTh3D4rk · Verfasst: Do 18.08.05 17:39

GTA-Place hat folgendes geschrieben:

Hab mal bisschen weitergeforscht und nochmal ne knapp eine Sekunde gespart, wenn ich als Rückgabewert Byte statts Boolean nehme (0 oder 1).

du meinst bits oder ? weil

1 bit = 1 oder 0

8 bits = 1 byte

würdest du bytes nehmen kannst es ja auch noch auf bits optmieren :wink:

eigentlich gibt es ja noch keine formel um primzahlen zu berechnen, weil es eben kein system gibt, jetzt stelle ich einfach mal die behauptung 999999999999991 sei eine primzahl und jemand beweise mir das gegenteil.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme