Optimierung einer Primzahlfunktion

Gausi · Verfasst: Fr 26.08.05 14:33

Amateur hat folgendes geschrieben:

die größte primzahl is ja irgendwas mit 2^6000 -1 oder so...

"Oder so" ist richtig: :lol:

de.wikipedia.org/wiki/Mersenne-Primzahl: hat folgendes geschrieben:

Im GIMPS-Projekt wurde die 42. Mersenne-Primzahl entdeckt: 2 hoch 25.964.951 -1 hat 7.816.230 Stellen.

Eine größte Primzahl gibt es übrigens nicht - es gibt ja bekanntlich unendlich viele.

_________________
We are, we were and will not be.

Amateur · Verfasst: Fr 26.08.05 14:48

Gausi hat folgendes geschrieben:

Amateur hat folgendes geschrieben:

die größte primzahl is ja irgendwas mit 2^6000 -1 oder so...

"Oder so" ist richtig: :lol:

de.wikipedia.org/wiki/Mersenne-Primzahl: hat folgendes geschrieben:

Im GIMPS-Projekt wurde die 42. Mersenne-Primzahl entdeckt: 2 hoch 25.964.951 -1 hat 7.816.230 Stellen.

Eine größte Primzahl gibt es übrigens nicht - es gibt ja bekanntlich unendlich viele.

ja ok viell doch nen bisschen größer.. ich meinte natürlich die größte bekannte bzw. gefundene primzahl...sry.

naja aber wie will man sowas abspeichern? nen variablentyp in delphi der so ne zahl speichert is mir net bekannt...

kann man das also umgehn? denn sonst bringt son primzahl algorithmus ja eh nix... lässt man seinen pc die ganze laufen und spamt seine platte mit ner riesen textdatei voll voller primzahlen und im endeffekt wird man eh keine größere finden können da nen normaler hauspc gar net so große zahlen speichern kann...

bringt also im endeffekt nix außer dass man sagen kann ich hab nen primzahlenalgoritmus geschrieben...

oder?

_________________
"Kein dummes Gerede. Kein Rumrätseln. Denkt an nichts anderes mehr, nur noch an das, was vor euch liegt. Das ist die wahre Herausforderung. Ihr müßt euch vor euch selbst schützen, Leute." (Rennes in "Cube")
Beiträge: >700

F34r0fTh3D4rk · Verfasst: Fr 26.08.05 15:38

man kann das auf ganz viele interger64 aufteilen

Amateur · Verfasst: Fr 26.08.05 18:20

F34r0fTh3D4rk hat folgendes geschrieben:

man kann das auf ganz viele interger64 aufteilen

ok und wie willste die dann wieder zusammenmachen? wie soll das gehn?
wenn du jetzt ne zahl hast die zu groß is willste die dan in zwei hälften teilen zum beispiel 100000 teilste in 100 und 000 oder wie? dann musste die ja wieder zusammenfügen und dazu brauchste ne variable die so große zahlen speichert und die gibts ja net.. denn in 50000*2 kann man ja net aufteilen da das mit primzahlen net geht..

also da seh ich grad 0 durch...

_________________
"Kein dummes Gerede. Kein Rumrätseln. Denkt an nichts anderes mehr, nur noch an das, was vor euch liegt. Das ist die wahre Herausforderung. Ihr müßt euch vor euch selbst schützen, Leute." (Rennes in "Cube")
Beiträge: >700

F34r0fTh3D4rk · Verfasst: Fr 26.08.05 18:50

nein du sollst die zwei zahlen auch nicht zusammenfügen, das ginge auch garnicht, sonst würde man sich die mühe ja gleich sparen :lol:

Normalerweise würde man die zahl in primzahlen zerlegen, was hier wohl nichts bringt, um bytes zu sparen könnte man aber auch noch das zahlensystem wechseln, ich weiß nicht ob da was zu holen ist, zb das hexasystem, dort wäre dann aber ein zeichen 1 byte groß, die zahl wäre aber trotzdem größer. bin mir nicht sicher ob das was bringen könnte, hab da nicht so die ahnung von :lol:

aufteilen auf mehrere int64 sollte aber irgendwie machbar sein, also zb eine zahl auf 2 int64 aufspalten, dann hätte man die doppelte menge an bytes. ich werde mal schauen.

GTA-Place · Verfasst: Fr 26.08.05 18:54

Du kannst die beiden dann in einen String umwandeln und dann wieder zusammensetzten

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

AXMD · Verfasst: Fr 26.08.05 18:54

GTA-Place hat folgendes geschrieben:

Du kannst die beiden dann in einen String umwandeln und dann wieder zusammensetzten

Ineffetkiver gings kaum ^^

AXMD

F34r0fTh3D4rk · Verfasst: Fr 26.08.05 18:57

hab oben bissl was editiert

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

type
  Int128 = record
    Int1: Int64;
    Int2: Int64
end;

die frage : wie damit rechnen ?

negaH · Beiträge: 17

@Phantom1:

so es is Wochenende und ich habe mir mal deinen Algo genauer angeschaut.
Vorweg: unsere beiden Siebe unterscheiden sich an wesentlichen Punkten, sind also nicht identisch, wenn auch die mathematische Grundlage identisch scheint.

Bevor wir aber weiter versuchen deinen Algo zu optimieren, müssen wir ihr erstmal korrekt lauffähig bekommen.
D.h. als erstes habe ich überprüft ob dein Algo korrekt arbeitet. Leider ist dies nicht der Fall.

Mein Testcode dazu ist:

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:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:

function SavePrimes(MaxPrime: Cardinal): Cardinal;
const
  CACHE = 64*1024;
  STEMPEL: array[0..7] of Byte = (1, 7, 11, 13, 17, 19, 23, 29);
  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);
var
  Primes, PrimesLUT: array of Byte;
  Count,FailsIndex,FailsNonPrime,P,Q,Index, i, j, k, PrimeLen, PrimeBits, Num, Num2, m, mbit, s: Cardinal;
  QisPrime: Boolean;
  f: TextFile;
begin
  Index := 1;
  FailsIndex := 0;
  FailsNonPrime := 0;
  Count := 0;

  SetLength(PrimesLUT, Trunc(Sqrt(MaxPrime)/30)); // max 2184 Byte für 2^32 ;-)
  PrimesLUT[0]:=$01;
  PrimeLen:=Length(PrimesLUT);
  PrimeBits:=PrimeLen*30;
  for i:=0 to Trunc(Sqrt(PrimeBits)/30) do
    for j:=0 to 7 do
      if PrimesLUT[i] and (1 shl j)=0 then
      begin
        s:=STEMPEL[j];
        Num:=i*30+s;
        Num2:=Num*Num;
        mbit:=Num2 mod 30;
        m:=(Num2-mbit) div 30;
        while m<PrimeLen do
        begin
          PrimesLUT[m]:=PrimesLUT[m] or MODS[mbit];
          Inc(m, i);
          Inc(mbit, s);
          if mbit>29 then
          begin
            Dec(mbit, 30);
            Inc(m);
          end;
        end;
      end;

  SetLength(Primes, CACHE);
  PrimeLen:=Length(Primes);
  PrimeBits:=PrimeLen*30;
  for k:=0 to MaxPrime div PrimeBits do
  begin
    FillChar(Primes[0], PrimeLen, 0);
    for i:=0 to Trunc(Sqrt((k+1)*PrimeBits)/30) do
      for j:=0 to 7 do
        if PrimesLUT[i] and (1 shl j)=0 then
        begin
          s:=STEMPEL[j];
          Num:=i*30+s;
          if k=0 then Num2:=Num*Num
            else Num2:=Trunc(k*PrimeBits/Num)*Num+Num;
          mbit:=Num2 mod 30;
          m:=(Num2-mbit) div 30-k*PrimeLen;
          while m<PrimeLen do
          begin
            primes[m]:=Primes[m] or MODS[mbit];
            Inc(m, i);
            Inc(mbit, s);
            if mbit>29 then
            begin
              Dec(mbit, 30);
              Inc(m);
            end;
          end;
        end;


     for I := 0 to PrimeLen-1 do
       for J := 0 to 7 do
       begin
         Q := k * PrimeBits + I * 30 + Stempel[J];
         if Q > MaxPrime then Break;
         if not ((I = 0) and (J = 0) and (K = 0)) and (Primes[I] and (1 shl J) = 0) then
         begin
           P := Prime.Primes[Index];
           if Q <> P then
           begin
             QisPrime := Prime.IsPrime(Q);
             Inc(FailsIndex);
             if not QisPrime then Inc(FailsNonPrime);
             WriteLn('Fails: ', FailsIndex:5, '/', FailsNonPrime:5,  ', Index: ', Index:12, ', Q: ', Q:12, ', ',QisPrime:6, ', P: ', P:12, ', ', Prime.IsPrime(P):6);
             while (Q > P) and (Index < Prime.Primes.MaxIndex) do
             begin
               Inc(Index);
               P := Prime.Primes[Index];
               if P <> Q then
               begin
                 Inc(FailsIndex);
                 WriteLn('Fails: ', FailsIndex:5, '/', FailsNonPrime:5,  ', Index: ', Index:12, ', Q: ', Q:12, ', ',QisPrime:6, ', P: ', P:12, ', ', Prime.IsPrime(P):6);
               end;
             end;
             WriteLn;
             if QIsPrime then Inc(Index);
           end else Inc(Index);
           Inc(Count);
         end;
       end;
  end;
  Result := count;
end;

Wie du siehtst habe ich das ganze Dateihandling rausgenommen, da es irrelevant ist. Dafür habe ich aber die Anzahl der Primzahlen integriert und später dann mein eigenes Sieb parallel arbeitend integriert, um die Resultate direkt vergleichen zu können.

Ein Ausschnitt des obigen Algo. in meiner Console sieht dann so aus:

markieren

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:

Fails:     1/    0, Index:            1, Q:            7,   TRUE, P:            2,   TRUE
Fails:     2/    0, Index:            2, Q:            7,   TRUE, P:            3,   TRUE
Fails:     3/    0, Index:            3, Q:            7,   TRUE, P:            5,   TRUE

Fails:     4/    1, Index:    203233127, Q:   4293918781,  FALSE, P:   4293918787,   TRUE
Fails:     5/    2, Index:    203233128, Q:   4293918791,  FALSE, P:   4293918793,   TRUE
Fails:     6/    3, Index:    203233131, Q:   4293918877,  FALSE, P:   4293918883,   TRUE
Fails:     7/    4, Index:    203233132, Q:   4293918887,  FALSE, P:   4293918907,   TRUE
Fails:     8/    5, Index:    203233133, Q:   4293918913,  FALSE, P:   4293918953,   TRUE
Fails:     9/    6, Index:    203233133, Q:   4293918947,  FALSE, P:   4293918953,   TRUE

....

Fails: 38283/38280, Index:    203280214, Q:   4294967101,  FALSE, P:   4294967111,   TRUE
Fails: 38284/38281, Index:    203280214, Q:   4294967107,  FALSE, P:   4294967111,   TRUE
Fails: 38285/38282, Index:    203280219, Q:   4294967213,  FALSE, P:   4294967231,   TRUE
Fails: 38286/38283, Index:    203280220, Q:   4294967273,  FALSE, P:   4294967279,   TRUE

....

Fails: 38287/38284, Index:    203280222, Q:           15,  FALSE, P:            0,  FALSE
Fails: 38288/38285, Index:    203280222, Q:           21,  FALSE, P:            0,  FALSE
Fails: 38289/38285, Index:    203280222, Q:           37,   TRUE, P:            0,  FALSE
Fails: 38290/38285, Index:    203280223, Q:           61,   TRUE, P:            0,  FALSE
Fails: 38291/38286, Index:    203280224, Q:           75,  FALSE, P:            0,  FALSE
Fails: 38292/38287, Index:    203280224, Q:           81,  FALSE, P:            0,  FALSE

....

Fails: 113112/105327, Index:    203288004, Q:       917403,  FALSE, P:            0,  FALSE
Fails: 113113/105328, Index:    203288004, Q:       917425,  FALSE, P:            0,  FALSE
Fails: 113114/105329, Index:    203288004, Q:       917433,  FALSE, P:            0,  FALSE
Fails: 113115/105330, Index:    203288004, Q:       917463,  FALSE, P:            0,  FALSE
Fails: 113116/105331, Index:    203288004, Q:       917467,  FALSE, P:            0,  FALSE
Fails: 113117/105332, Index:    203288004, Q:       917497,  FALSE, P:            0,  FALSE

Aufruf: mit SavePrimes($FFFFFFFB) -> $FFFFFFFB = 4294967291 ist höchste Primzahl < 2^32 mit Primzahlindex 203280221.

Fails: gibt ab wieviele Fehlresultat der Algo macht -> Anzahl Indexfehler/Anzahl fehlerhafter Primzahlen (sind also zusammengesetzte Zahlen die dein Algo als Primzahlen ausgibt).
Index: der Index der Primzahl in der Primzahltabelle.
Q: die Zahl die dein Algo als Primzahl ausgibt, danach FALSE/TRUE je nachdem ob Q tatsächlich eine Primzahl ist.
P: die Primzahl die mein Algo. zum Index berechnet, FALSE/TRUE jenachdem ob P eine Primzahl ist

Die ersten 3 Zeilen können wir ignorieren, da dein Algo keine direkte Berechnung zu den ersten 3 Primzahlen bietet.

Ab Primzahlindex 203233127 erzeugt dein Algo nun Zahlen die keine Primzahlen sind, er arbeitet ab da falsch.
Das geht bis Primzahlindex 203280220 was exakt der Moment ist wo der Algo im Grunde terminieren müsste.

Bis zu diesem Bereich hat dein Algo also 38287 Zahlen als Primzahlen erzeugt die aber zusammengesetzte Zahlen sind.
Der letzte Block ab dem P= 0 ist, hätte dein Algo bei der Zeile

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

     for I := 0 to PrimeLen-1 do
       for J := 0 to 7 do
       begin
         Q := k * PrimeBits + I * 30 + Stempel[J];
         if Q > MaxPrime then Break;                    // <---

schon längst terminieren müssen. Er rechnet aber weiter da wie man sieht Q nun < $FFFFFFFB ist, sprich ein Integer Überlauf dazu führt das der Algo noch mehr falsche Zahlen berechnet. Da er aber nicht terminiert beendet sich der Algo erst mit der äußersten Schleife k und erzeugt somit 113117 falsche Antworten.

Nun zur Performance:

ich habe mit nachfolgendem Source getestet. Auch hier wieder die Dateioperationen und Stringkonvertierungen entfernt, dafür aber unterschieden ob man nur die Anzahl der Primzahlen oder auch die Primzahlen wertmäßig exakt berechnen möchte. Diese Unterscheidung ist wichtig beim direkten Vergleich der unterschiedlichen Verfahren.

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:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:

function SavePrimes1(MaxPrime: Cardinal; CalcPrimes: Boolean): Cardinal;
const
  CACHE = 64*1024;
  STEMPEL: array[0..7] of Byte = (1, 7, 11, 13, 17, 19, 23, 29);
  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);
var
  Primes, PrimesLUT: array of Byte;
  Count, i, j, k, PrimeLen, PrimeBits, Num, Num2, m, mbit, s: Cardinal;
begin

  SetLength(PrimesLUT, Trunc(Sqrt(MaxPrime)/30)); // max 2184 Byte für 2^32 ;-)
  PrimesLUT[0]:=$01;
  PrimeLen:=Length(PrimesLUT);
  PrimeBits:=PrimeLen*30;
  for i:=0 to Trunc(Sqrt(PrimeBits)/30) do
    for j:=0 to 7 do
      if PrimesLUT[i] and (1 shl j)=0 then
      begin
        s:=STEMPEL[j];
        Num:=i*30+s;
        Num2:=Num*Num;
        mbit:=Num2 mod 30;
        m:=(Num2-mbit) div 30;
        while m<PrimeLen do
        begin
          PrimesLUT[m]:=PrimesLUT[m] or MODS[mbit];
          Inc(m, i);
          Inc(mbit, s);
          if mbit>29 then
          begin
            Dec(mbit, 30);
            Inc(m);
          end;
        end;
      end;

  SetLength(Primes, CACHE);
  PrimeLen:=Length(Primes);
  PrimeBits:=PrimeLen*30;
  for k:=0 to MaxPrime div PrimeBits do
  begin
    FillChar(Primes[0], PrimeLen, 0);
    for i:=0 to Trunc(Sqrt((k+1)*PrimeBits)/30) do
      for j:=0 to 7 do
        if PrimesLUT[i] and (1 shl j)=0 then
        begin
          s:=STEMPEL[j];
          Num:=i*30+s;
          if k=0 then Num2:=Num*Num
            else Num2:=Trunc(k*PrimeBits/Num)*Num+Num;
          mbit:=Num2 mod 30;
          m:=(Num2-mbit) div 30-k*PrimeLen;
          while m<PrimeLen do
          begin
            primes[m]:=Primes[m] or MODS[mbit];
            Inc(m, i);
            Inc(mbit, s);
            if mbit>29 then
            begin
              Dec(mbit, 30);
              Inc(m);
            end;
          end;
        end;

     if CalcPrimes then
       for I := 0 to PrimeLen-1 do
         for J := 0 to 7 do
         begin
           if (k * PrimeBits + I * 30 + Stempel[J]) > MaxPrime then Break;
           if not ((I = 0) and (J = 0) and (K = 0)) and (Primes[I] and (1 shl J) = 0) then
             Inc(Count);
         end;
  end;
  Result := count;
end;

procedure TestPrimes;
var
  I,P: Cardinal;
begin
  StartTimer;
  Primes.IndexOf($7FFFFFFF);
  Writeln(Secs:10:2, ' sec');

  StartTimer;
  SavePrimes1($7FFFFFFF, False);
  Writeln(Secs:10:2, ' sec');

  I := 1;
  StartTimer;
  repeat
    P := Primes[I];
    Inc(I);
  until P >= $7FFFFFFF;
  Writeln(Secs:10:2, ' sec');


  StartTimer;
  SavePrimes1($7FFFFFFF, True);
  Writeln(Secs:10:2, ' sec');
end;

Laufzeiten:

markieren

Quelltext

1:
2:
3:
4:
5:

Primes.IndexOf($7FFFFFFF)         =  12.74 sec
SavePrimes($7FFFFFFF, False)      =  51.38 sec

loop Primes[i] until >= $7FFFFFFF =  30.64 sec
SavePrimes($7FFFFFFF, True)       =  67.98 sec

auf einem P4 1.5GHz 512Mb und Delphi 5.

Die gravierenden Performanceunterschiede zum AMD sind für mich nur durch die Anwendung der Opcodes BTS/BTC in meinen Bitarray[] Funktionen erklärbar. AMD Prozessoren sind mit diesen Operationen wesentlich langsammer als Pentium CPU's. Für AMD's müsste man diese Opcodes durch indizierte Array[] Zugriff + AND/OR Bitmasken per SHL/SHR ersetzen.

Alledings, als erstes muß man den Algorithmus sauber lauffähig bekommen, denn Speed nutzt nur dann etwas wenn die berechneten Resultate auch wirklich mathematisch korrekt sind.

Gruß Hagen

Amateur · Verfasst: Fr 26.08.05 22:50

F34r0fTh3D4rk hat folgendes geschrieben:

hab oben bissl was editiert

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

type
  Int128 = record
    Int1: Int64;
    Int2: Int64
end;

die frage : wie damit rechnen ?

tja wie damit rechnen? genau das is nämlich das problem... der ansatz is sicher net schlecht aber bringe ntuts aus meiner sicht nix denn um ne vollständige zahl die man auf teilbarkeit überprüfen kann zu bekommen, müsste man ja sowas schreiben:

markieren

Delphi-Quelltext

1:
2:
3:

var endzahl:string; endzahl2:integer;
endzahl:=int128.int1+int128.int2;
endzahl2:=strtoint(endzahl);

und diese endzahl2 kann man auf teilbarkeit prüfen, d.h. ob es ne primzahl is oder net...
so aber diese endzahl2 kann ja kein integer sein und kein int64 sondern muss von nem größeren variablentyp sein...

und da fängt das prob von vorne an, woher nehm ich son variablentyp...?

ich find bevor man weiter an optimierungen für die algorithmen feilt, die ja sowieso mit 2,5 sekunden für 500k zahlen schnell genug sind im moment sollte man erstma diese frage klären...
denn sonst hat das ganze ja keinen sinn...

wär genauso als wollte man das best getunte auto bekommen, hat aber nur nen vw käfer der zwar superschnell läuft aber trotzdem nie der beste wird... da kann man noch soviel geld reinstecken

you know?!?

_________________
"Kein dummes Gerede. Kein Rumrätseln. Denkt an nichts anderes mehr, nur noch an das, was vor euch liegt. Das ist die wahre Herausforderung. Ihr müßt euch vor euch selbst schützen, Leute." (Rennes in "Cube")
Beiträge: >700

Amateur · Verfasst: Sa 27.08.05 00:11

ok damit das hier net völlig vom thema abweicht hab ich hier nen extra thread eröffnet um die problematik der variablengröße zu diskutieren und lösungen zu finden:

www.delphi-forum.de/....php?p=286547#286547

es sollten alle mal vorbeischauen und lösungen posten falls sie welche kennen...

und hier in dem thread heißt es back 2 topic!!! optimiert den algorithmus weiter...

und baut ne lösung für größere zahlen ein falls es eine im anderen thread gibt...

_________________
"Kein dummes Gerede. Kein Rumrätseln. Denkt an nichts anderes mehr, nur noch an das, was vor euch liegt. Das ist die wahre Herausforderung. Ihr müßt euch vor euch selbst schützen, Leute." (Rennes in "Cube")
Beiträge: >700

GTA-Place · Verfasst: Sa 27.08.05 09:00

Hab dir schon eine Lösung gepostet. Nennt sich "HugeInt" und speichert so viele Zahlen, wie der Speicher zulässt.

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

alzaimar · Verfasst: So 28.08.05 19:10

Falls es jemanden interessiert: Ich den 'Sieve of Atkins' aus der PrimeGen-Library in Delphi übersetzt. Die Version findet alle Primzahlen bis 500.000.000 in 850ms, gemessen auf einem Pentium 4 M 1.5 Ghz.

Im Anhang: Kleines Testprogramm und Verfahren, einfach mal nach "PrimeGen" googeln.

Einloggen, um Attachments anzusehen!

Horst_H · Verfasst: Mi 07.09.05 14:36

Hallo,

ich bin bei diesem Programm etwas ueber die Anzahl der Primzahlen erstaunt, da diese meiner Meinung nach zu gross ist.
800 Mhz Duron:

1: Time = 2232
2: Time = 2448
3: Time = 2458
4: Time = 2434
5: Time = 2365
6: Time = 2315
7: Time = 2240
8: Time = 2598
9: Time = 2773
10: Time = 2875
29595801 primes up to 500660190 in 2474 tics

Mein Programm von www.softgames.de/for...t=20789&start=30 für Turbo Pascal stimmt mit den Daten von did.mat.uni-bayreuth...Seminar/HTML/pz5.htm ueberein.

ERATOSTHENES SIEB bis: 1000000000

Es sind 50847534 Primzahlen bis 1000000000

Es dauerte 1835 100.stel Sekunden
Fertig mit Zahl<Enter>
Aber ich erhalte viel weniger Primzahlen.
ERATOSTHENES SIEB bis: 500660190

Es sind 26388846 Primzahlen bis 500660190

Es dauerte 967 100.stel Sekunden
Fertig mit Zahl<Enter>

29595801 primes up to 500660190 in 2474 tics
Es sind 26388846 Primzahlen bis 500660190

Da liegen 3 Mio Zahlen dazwischen (mehr als 10%)!

Da bedarf es einiger Korrekturen.

Gruss Horst

EDIT Softgames hat sich verkürzt.

Einloggen, um Attachments anzusehen!

Phantom1 · Beiträge: 390

Das was Horst_H sagt stimmt, ich habe das eben mal mit dem originalen ecprime überprüft -> Es sind 26388846 Primzahlen bis 500660190

mfg

Horst_H · Verfasst: Do 08.09.05 09:15

Hallo,

falls Du es gesehen hast, gibt es ein Wiederholungsfeld, indem alle Vielfachen von 2,3,5,7,11,13 schon ausgestrichen sind
Den Stempel gibt es auch hier
Ältere Version
www.qsl.net/w2gl/blackkey.html

Gruss Horst
P.S.:
Ich habe eben mal
www.delphi-forum.de/download.php?id=1201
PrimFinder.zip
.. Bei mir(=Phantom1) braucht dieses Programm 2930ms....
ausgeführt und der braucht auch 8,07 sec, ist also nur 19% schneller als meine Uraltversion fuer Turbo Pascal.
Ich hatte vermutet, die Kompression der Daten von 30 Byte auf 1 byte haette groessere Auswirkungen.

EDIT:
Anbei ein Programm, was qsl.net in etwa nachahmte, aber einen kompletten Bereich abklappert, statt kurze, cache-freundliche Abschnitte.
Es funktioniert bis 82e9 bei Belegung von fast 2 Gbyte ( 1300 Sekunden) , unter Auslassung aller Vielfacher von 2,3,5,7,11,13.
Wenn man 17 auch noch weglässt funktioniert es bis 86e9 wird aber noch langsamer.Da nichts mehr ( Zahlen-feld) in den Level I Cache passt

markieren

Quelltext

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

    2   3   5   7  11  13
Zahlen    :60060 Byte
DiffFeld  :5760 Byte
MulFeld   :184 Byte
SuchFeld  :575424580 Byte
Maxzahl   :24000000190
 cMaxPos 799200
MaxPos 24000000000
MaxPos 23999999999 
MaxPos 4603396603 cMaxPos 23999976000
Anzahl Streichungen 6236659378

Zeit in Sekunden 276.952000
Bis 24000000000 Sind es 1050186367 Primzahlen

real  4m37.715s
user  4m36.377s
sys  0m0.343s

Edit..: devalco ist jetzt anders verlinkt

Einloggen, um Attachments anzusehen!

alzaimar · Verfasst: Do 08.09.05 21:17

Mann, seit ihr pingelig! Die paar Primzahlen extra, was wollt ihr überhaupt? Die sind umsonst! Persönliche Zugabe! :dunce:

Im Ernst: In der inneren Schleife ist das "inc (k,q)" beim Optimieren eine Zeile hochgerutscht. Jetzt stimmts.

Einloggen, um Attachments anzusehen!

Phantom1 · Beiträge: 390

alzaimar hat folgendes geschrieben:

Mann, seit ihr pingelig! Die paar Primzahlen extra, was wollt ihr überhaupt? Die sind umsonst! Persönliche Zugabe! :dunce:

Im Ernst: In der inneren Schleife ist das "inc (k,q)" beim Optimieren eine Zeile hochgerutscht. Jetzt stimmts.

Durch diese "Kleinigkeit" braucht der Code jetzt 1312ms anstatt 726ms :shock:

mfg

alzaimar · Verfasst: Do 08.09.05 21:35

Er rechnet doch auch die doppelte Anzahl von Primzahlen aus, oder?

Horst_H · Verfasst: Fr 09.09.05 09:01

Hallo,

jau , und es läuft auch in nicht einmal der doppelten Zeit bei mir (ca. 4,1 sec). :-)

Jetzt fehlt nur noch eine Kleinigkeit, um bei der richtigen Zahl zu stoppen und nicht so merkwürdig krummen Zahlen.

Gruss Horst

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme