Optimierung einer Primzahlfunktion

hallo · Verfasst: Do 18.08.05 19:04

Da hat es schon größere Zahlen gegeben!
Die größte bekannte Primzahl hat einige Millionen Stellen!

Was man jedoch auch beachten soll: Wenn man schon geschaut hat ob die Zahl durch 3 teilbar ist, darf man nicht mehr schauen ob sie auch durch 6 9 etc. geht!

_________________
Der beste je Programmierte Trojaner: Windows XP
Wäre es nicht adequat, den Usus heterogener Termini zu minimieren?

F34r0fTh3D4rk · Verfasst: Do 18.08.05 19:22

mir ist nur aufgefallen, dass alle zahlen die aus Neunen bestehen und am ende eine 1 haben immer primzahlen zu sein scheinen, demnach wäre das hier auch eine:

Zitat:

99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
1

GTA-Place · Verfasst: Do 18.08.05 19:30

hallo hat folgendes geschrieben:

Da hat es schon größere Zahlen gegeben!
Die größte bekannte Primzahl hat einige Millionen Stellen!

Was man jedoch auch beachten soll: Wenn man schon geschaut hat ob die Zahl durch 3 teilbar ist, darf man nicht mehr schauen ob sie auch durch 6 9 etc. geht!

Bist aber ein ganz schlauer.

1. Wissen wir das.
2. Beim Sieb des E. kommt Prüfung durch 6 oder 9 nicht vor, da ich ja schon durch 3 geteilt habe.

F34r0fTh3D4rk hat folgendes geschrieben:

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:

Ne ich mein schon Bytes, aber wenns auch Bits bei Delphi gibt, dann kann ich das noch etwa optimieren.

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

zemy · Beiträge: 207 Win XP Prof. D7

F34r0fTh3D4rk hat folgendes geschrieben:

mir ist nur aufgefallen, dass alle zahlen die aus Neunen bestehen und am ende eine 1 haben immer primzahlen zu sein scheinen, demnach wäre das hier auch eine:

Zitat:

99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
99999999999999
1

Wenns so einfach währe

Bis zur 1-Million scheints ja zu Stimmen. Und drüber hinaus? Traust du dir zu, aus 5-6 Zahlen eine allgemein-gültige Regel zu definieren?

_________________
LifeIsToShortToThinkAboutTheShortness

Phantom1 · Beiträge: 390

Hab mein Algo weiter optimiert, diesmal hab ich das Array in gleich große Stücke (64Kilobyte) unterteilt. War ziemlich knifflig und schwieriger als ich dachte, aber es geht erstmal

Auch hier habe ich ein 30er Stempel benutzt mit Bit-Komprimierung.

Hier der 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:
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:

procedure SavePrimes(MaxPrime: Cardinal; const FileName: String = '');
const
  STEMPEL: array[0..7] of Byte = (1, 7, 11, 13, 17, 19, 23, 29);
var
  Primes: array[0..MAXWORD] of Byte;  // 64 KB
  i, j, k, PrimeLen, PrimeBits, Num, Num2, m, mbit: Cardinal;
  f: TextFile;
begin
  if FileName<>'' then begin
    AssignFile(f, FileName);
    ReWrite(f);
    WriteLn(f, '2'+#10#13+'3'+#10#13+'5');
  end;
  PrimeLen:=Length(Primes);
  PrimeBits:=PrimeLen*30;
  for k:=0 to Trunc(MaxPrime/PrimeBits) do begin
    FillChar(Primes, PrimeLen, 0);
    for i:=0 to Trunc(Sqrt((k+1)*PrimeBits)/30) do
      for j:=0 to 7 do
        if not ((i=0) and (j=0)) and ((Primes[i] and (1 shl j)=0) or (k>0)) then begin
          Num:=i*30+STEMPEL[j];
          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
            case mbit of
              1: Primes[m]:=Primes[m] or 1;
              7: Primes[m]:=Primes[m] or 2;
             11: Primes[m]:=Primes[m] or 4;
             13: Primes[m]:=Primes[m] or 8;
             17: Primes[m]:=Primes[m] or 16;
             19: Primes[m]:=Primes[m] or 32;
             23: Primes[m]:=Primes[m] or 64;
             29: Primes[m]:=Primes[m] or 128;
            end;
            Inc(m, i);
            Inc(mbit, STEMPEL[j]);
            if mbit>29 then begin
              Dec(mbit, 30);
              Inc(m);
            end;
          end;
        end;
    if FileName<>'' 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
            WriteLn(f, IntToStr(k*PrimeBits+i*30+STEMPEL[j]));
        end;
  end;
  if FileName<>'' then
    CloseFile(f);
end;

Hier die Ergebnisse:

bei 100 mio testzahlen:
alt: 2478ms (RAM-Verbrauch: 11,9 MB)
neu: 2060ms (RAM-Verbrauch: 64,0 KB)

bei 500 mio testzahlen:
alt: 14598ms (RAM-Verbrauch: 59,6 MB)
neu: 11525ms (RAM-Verbrauch: 64,0 KB)

mfg
Phantom1

alzaimar · Verfasst: Sa 20.08.05 18:43

Bau doch meine Zugriffe mit den Arrays 'mods' und 'p2' ein, anstatt diese übersichtlichen, aber langsamen case of - Anweisungen, dann sparst Du wieder 60%.
Ich habe es auf meinem Lappi getestet, und da ist da Verhältnis bei 500 mio: 17300 (mit CASE) zu 9000 (mit Array). Wieso sollte ein "Case of" eigentlich schneller sein, als ein Zugriff auf ein Array? Schau Dir mal den Assembler an, den Delphi aus einem "Case of" macht.

Dann noch das Trunc(k*PrimeBits/Num) in ein MulDiv (k,PrimeBits, Num), und Du sparst nochmal 1500 ms ein.

Abschliessend habe ich noch die unnötigen Zugriffe auf STEMPEL[J] aus der innersten While Schleife rausgeholt, das brachte mit ein paar Kleinigkeiten nochmal 1100 ms, sodass ich (also, eigentlich ja Du) jetzt bei 6300 ms bin, also fast 3x schneller.

Eigentlich müsstest Du noch die Zugriffe auf das Primes-Array von Primes[m] in einen Zeiger umändern (und den inkrementieren), das dürfte nochmal Einiges bringen, aber das bekomme ich nicht hin. Dein Code ist zwar kompakt, aber die ziemlich lange "If not ((i=0) or ....)" Abfrage wird ja doch oft ausgeführt und ist nicht wirklich optimal.

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:

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);
  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: array[0..MAXWORD] of Byte;  // 64 KB
  s, i30, i, j, y, z,k, PrimeLen, PrimeBits, Num, Num2, m, mbit: Cardinal;
  f: TextFile;
begin
  if FileName<>'' then begin
    AssignFile(f, FileName);
    ReWrite(f);
    WriteLn(f, '2'+#10#13+'3'+#10#13+'5');
  end;
  PrimeLen:=Length(Primes);
  PrimeBits:=PrimeLen*30;
  z := 0;
  for k:=0 to Trunc(MaxPrime/PrimeBits) do begin
    FillChar(Primes, PrimeLen, 0);
    z := k*PrimeLen;
    for i:=0 to Trunc(Sqrt((k+1)*PrimeBits)/30) do begin
      i30 := i*30;
      for j:=0 to 7 do
        if not ((i=0) and (j=0)) and ((Primes[i] and p2[j]=0) or (k>0))  Then Begin
          s := Stempel[j];
          Num := i30 + s;
          if k=0 then
            Num2 := Num * Num
          else
            Num2 := MulDiv (k, PrimeBits, Num) * Num + Num;
          mbit := Num2 mod 30;
          m := (Num2-mbit) div 30 - z;
          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;
      End;

    if FileName<>'' 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
            WriteLn(f, IntToStr(k*PrimeBits+i*30+STEMPEL[j]));
        end;
  end;
  if FileName<>'' then
    CloseFile(f);
end;

Nebenbei steht im ecprime-sourcecode drin, das die das im L1-Cache laufen lassen. Wie geht das denn?

AXMD · Verfasst: Sa 20.08.05 18:59

Bin nicht sooo der Experte, aber ist IntToStr nicht recht langsam? Da gibt's doch bestimmt andere Möglichkeiten? Z.B. den Integer direkt in die Datei schreiben

AXMD

BenBE · Verfasst: Sa 20.08.05 19:02

Soweit ich mich erinnere führt die CPU generell aus dem L1-Cache aus. Was die Leute im ecprimes-Source wahrscheinlich meinenn ist, dass die ihren Source so programmiert haben, dass die mit möglichst wenig Daten auskommen können und die CPU dadurch jegliche benötigten Informationen bereits im L1-Cache stehen hat, also nicht aus L2 oder RAM nachladen brauch.

D.h. auf diesen Source angewendet: Jegliche Zugriffe auf Daten müssten so geartet sein, dass NIE außerhalb eines etwa 16 KB großen Blockes Daten gelesen werden. Schaut für genauere Infos einfach mal auf die Seite von Intel oder AMD. Die haben dort recht gute Informationen zum Optimieren der Programme auf die Prozessoren.

Tipp: Indirekte Adressierungen vermeiden! Also z.B. Pointer auf einen Pointer oder Bit-Operationen die Bitshiftings im Speicher benötigen.
Außerdem sollten möglichst viele Infos gleich in den Registern gehalten werden.

_________________

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.

alzaimar · Verfasst: Sa 20.08.05 19:20

@Benny: Danke für die Info: Ich check den Source von ecprime mal auf deine Aussagen.
@AXMD: Das IntToStr steht ja nur im Output, das ist nicht wirklich entscheidend bei Performancemessungen: Ich messe natürlich immer mit Filename = ''...

Phantom1 · Beiträge: 390

@alzaimar: Ich hatte den Code noch nicht optimiert, ich war grad erst fertig mit der Array-aufteilung, hatte also noch keine Zeit dazu. Die ganzen optimierungen die du aufgezählt hast sind mir selbstverständlich bekannt ;O) Die Sache mit dem Zeiger aufs Primes-Array hab ich früher schonmal probiert, jedoch wurde es etwas langsamer.

@ASMD: wie bereits gesagt wurde, wird IntToStr nur bei der Ausgabe benutzt. Für mich steht im vordergrund aber erstmal nur die Berechnung. Ich werd mich später darum kümmern.

Das was BenBE sagt stimmt, die Daten werden generell aus dem L1-Cache benutzt. Ich glaub dort werden hauptsächlich die Adressen der Array-zugriffe gespeichert, wodurch es beim nächsten Aufruf schneller geht. Soweit ich weiß hat mein Athlon-XP-M einen 128KB (64KBData/64KBInstructionen) L1-Cache und einen 512KB großen L2 Cache, aus dem Grund habe ich eine Große von 64KB gewählt.

Phantom1 · Beiträge: 390

alzaimar hat folgendes geschrieben:

Bau doch meine Zugriffe mit den Arrays 'mods' und 'p2' ein, anstatt diese übersichtlichen, aber langsamen case of - Anweisungen, dann sparst Du wieder 60%.

Habe ich soeben gemacht, diesmal bringts wirklich viel.

alzaimar hat folgendes geschrieben:

Dann noch das Trunc(k*PrimeBits/Num) in ein MulDiv (k,PrimeBits, Num), und Du sparst nochmal 1500 ms ein.

Das kann man so nicht machen, es würde so ein falsches Ergebnis rauskommen.

Hier der aktuelle Code, mit allen Optimierung die was gebracht haben:

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:

procedure SavePrimes2(MaxPrime: Cardinal; const FileName: string = '');
const
  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: array[0..MAXWORD] of Byte;  // 64 KB
  i, j, k, PrimeLen, PrimeBits, Num, Num2, m, mbit, s: Cardinal;
  f: TextFile;
begin
  if FileName<>'' then begin
    AssignFile(f, FileName);
    ReWrite(f);
    WriteLn(f, '2'+#10#13+'3'+#10#13+'5');
  end;
  PrimeLen:=Length(Primes);
  PrimeBits:=PrimeLen*30;
  for k:=0 to Trunc(MaxPrime/PrimeBits) do begin
    FillChar(Primes, PrimeLen, 0);
    for i:=0 to Trunc(Sqrt((k+1)*PrimeBits)/30) do
      for j:=0 to 7 do
        if not ((i=0) and (j=0)) and ((Primes[i] and (1 shl j)=0) or (k>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 FileName<>'' 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
            WriteLn(f, IntToStr(k*PrimeBits+i*30+STEMPEL[j]));
        end;
  end;
  if FileName<>'' then
    CloseFile(f);
end;

Man kann das ganze noch weiter Optimieren, hab heute aber keine Lust mehr dazu ^^

Hier der Vergleich:
bei 100 mio testzahlen:
ohne Optim.: 2060ms
mit Optim.: 724ms

bei 500 mio testzahlen:
ohne Optim.: 11525ms
mit Optim.: 4109ms

mfg
Phantom1

GTA-Place · Verfasst: So 21.08.05 09:00

4 Sekunden für 500 Mio Zahlen. Das ist wirklich schnell!

Ich hab die Funktion mal unter deinem Namen in die DP geschrieben. Ist schon OK, oder?

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

Phantom1 · Beiträge: 390

GTA-Place hat folgendes geschrieben:

4 Sekunden für 500 Mio Zahlen. Das ist wirklich schnell!

Ich hab die Funktion mal unter deinem Namen in die DP geschrieben. Ist schon OK, oder?

Jo kein Problem, allerdings ist diese Funktion schon wieder veraltet :wink:

Hab die Funktion weiter optimiert. Für 500 Mio Zahlen braucht man jetzt nur noch 2,55 sekunden ^^

Hier der 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:
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:

procedure SavePrimes(MaxPrime: Cardinal; const FileName: string = '');
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: array[0..CACHE-1] of Byte;
  PrimesLUT: array of Byte;
  i, j, k, PrimeLen, PrimeBits, Num, Num2, m, mbit, s: Cardinal;
  f: TextFile;
begin
  if FileName<>'' then begin
    AssignFile(f, FileName);
    ReWrite(f);
    WriteLn(f, '2'+#13#10+'3'+#13#10+'5');
  end;

  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;

  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 FileName<>'' 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
            WriteLn(f, IntToStr(k*PrimeBits+i*30+STEMPEL[j]));
        end;
  end;
  if FileName<>'' then
    CloseFile(f);
end;

mfg
Phantom1

GTA-Place · Verfasst: So 21.08.05 11:15

Denn geh ich mal in der DP updaten...

EDIT: Äh... wie misst du? Ich bekomm 25 Sekunden raus.

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

Phantom1 · Beiträge: 390

GTA-Place hat folgendes geschrieben:

Denn geh ich mal in der DP updaten...

EDIT: Äh... wie misst du? Ich bekomm 25 Sekunden raus.

Speicherst du die Zahlen? oder warum dauert es bei dir so lange, mhhh...

Ich habe schnell mal was zusammengebastelt, du findest es im Anhang. Bei mir braucht dieses Programm 2930ms. (Die 2650ms die ich oben gemessen habe, wurde mit RealTime Priority gemessen).

GTA-Place · Verfasst: So 21.08.05 13:48

Die 2,5 Sekunden bekomm ich mit meinem Prog (mit deiner Funktion) nur bei 50.000.000 Zahlen hin.

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

Phantom1 · Beiträge: 390

GTA-Place hat folgendes geschrieben:

Die 2,5 Sekunden bekomm ich mit meinem Prog (mit deiner Funktion) nur bei 50.000.000 Zahlen hin.

Komisch. Wie lange braucht denn das Programm in meinem letzten Posting?

Evtl musst du das Programm an deinen L1 Cache anpassen. Wie groß beträgt dein L1/L2 Cache?

EDIT: Wenn ich 500 Mio zahlen berechne und auf Festplatte speichern lasse, dauert der gesamte vorgang 21,561 sekunden. Die Datei ist anschließend 270MB groß.

mfg
Phantom1

GTA-Place · Verfasst: So 21.08.05 14:51

Ah ja, ich habs mit speichern. Dann bekomm ich etwa das selbe raus.

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

GTA-Place · Verfasst: So 21.08.05 15:09

Ich hab deinen Source mal bisschen formatiert:

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:
107:
108:

procedure SavePrimes(MaxPrime: Cardinal; const FileName: string = '');  
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:            Array[0..CACHE-1] of Byte;
  PrimesLUT:         Array of Byte;
  i, j, k, PrimeLen: Cardinal;
  PrimeBits, Num:    Cardinal;
  Num2, m, mbit, s:  Cardinal;
  f:                 TextFile;
begin
  if not (FileName = '') then
  begin
    AssignFile(f, FileName);
    ReWrite(f);
    WriteLn(f, '2'+#10#13+'3'+#10#13+'5');
  end;

  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
  begin
    for j := 0 to 7 do
    begin
      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];
          m := m + i;
          mbit := mbit + s;
          if mbit > 29 then
          begin
            mbit := mbit - 30;
            Inc(m);
          end;  
        end;  
      end;
    end;
  end;

  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
    begin
      for j := 0 to 7 do
      begin
        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];
            m    := m + i;
            mbit := mbit + s;
            if mbit > 29 then
            begin
              mbit := mbit - 30;
              inc(m);
            end;
          end;
        end;
      end;
    end;

    if not (FileName = '') then
    begin
      for i := 0 to PrimeLen - 1 do
      begin
        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
            WriteLn(f, IntToStr(k * PrimeBits + i * 30 + STEMPEL[j]));
        end;
      end;
    end;
  end;

  if not (FileName = '') then
    CloseFile(f);
end;

Edit: Aktualisiert.

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

Phantom1 · Beiträge: 390

Naja die Formatierung ist Geschmackssache :wink:

Ich finde es so ehrlich gesagt unübersichtlicher. Zudem hab ich oben noch ein paar änderungen vorgenommen, die in deinem "formatiertem" Code noch nicht drin sind.

Momentan benötigt mein Code für 2^32-1 etwas über 24 sekunden. Jetzt können wir langsam auf 64bit-Bereich gehen *g

mfg
Phantom1

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme