Optimierung eines Stück Codes für eine Wette!

[SirThornberry]

so was hier würde ich übrigens als Schiedsrichter nicht durchgehen lassen:

Delphi-Quellcode:

Prim[1] := 2; 
Prim[2] := 3; 
Prim[3] := 5; 
anz_Prim := 3;

Denn sonst kommt der nächste und knotet gleich alle Primzahlen fest ins Programm. Entweder wird alles ermittelt oder alles fest rein geknotet. Oder warum hast du nur die ersten 3 Primzahlen fest rein geknotet und nicht die ersten 4?

@uwe:
folgendes sollte noch schneller sein:

Delphi-Quellcode:

For D := 7 To max_Prim do begin          // 6 ist keine Primzahl, daher ab 7  
  if not Odd(D) then Continue;           // schließe alle geraden Zahlen aus 
  maxTest := Trunc(Sqrt(D));             // prüfe nur bis max. Quadratwurzel des Kandidaten 
  for I := 2 to anz_Prim do begin        // gerade Zahlen hatten wir ausgeschlossen, daher ab 2 
    test := Prim[I]; 
    if test > maxTest then Break; 
    if not Boolean(D mod test) then
      Break; 
  end;
  if (i < anz_Prim) then
    Continue; 
  Inc(anz_Prim); 
  Prim[anz_Prim] := D; 
end;

[Blup]

Nach dem Schleifendurchlauf ist i undefiniert, insbesondere da der Compiler For-Schleifen optimiert (z.B. abwärts zählen bis 0).

Im Prinzip hab ich nichts neues hinzuzufügen, aber da ich mir schon die Mühe gemacht hab:

Delphi-Quellcode:

For D := Prim[anz_Prim] + 1 To max_Prim do 
begin 
  if Odd(D) then
  begin
    Pmax := Trunc(Sqrt(D));

    flg_Prim := True;
    for I := 1 to anz_Prim do
    begin
      P := Prim[I];
      flg_Prim := ((D mod P) <> 0);
      if not flg_Prim then
        Break;
      if P >= PMax then
        Break;
    end;
      

    If flg_Prim then 
    begin 
      Inc(anz_Prim); 
      Prim[anz_Prim] := D; 
      {lst_Ausgabe.Items.Add(IntToStr(D) + ' ist eine Primzahl!'); } 
    end; 
  end;
end;

[sirius]

Zitat von Thornberry:

// gerade Zahlen hatten wir ausgeschlossen, daher ab 2

Dann doch ab 3

Zitat:

if not Boolean(D mod test)

Wenn dann schon "LongBool(D mod test)", ansonsten testest du ja nur das letzte Byte.

[SirThornberry]

Auf was für einem Rechner läuft eigentlich der finale Testlauf? Wenn es einer mit mehreren Kernen ist kann man einiges an Zeit raus holen wenn man mit mehreren Threads arbeitet.

[sirius]

Ein riesen ZEitsprung entsteht, wenn man die Division mit einer Schleifenvariable, anstatt mit dem Inhalt einer lokalen Variable (=bisherige Primzahlen) macht.
Mit der verbesserten Variante von Sir komme ich unter 2 Sekunden.

[R2009]

Hallo Blup,

ich hab deinen Code reinkopiert.
Ergebnis:
Bei Delphi ist der Zeitaufwand für 1000000 nicht mehr messbar, bei VB nach wie vor 22 Sekunden.
Ich hab natürlich jetzt die Lacher auf meiner Seite.
Natürlich hab ich mich geweigert den Code rauszurücken, du hast ja doch schon gewaltig am Algorithmus gedreht.
Aber Hauptsache ich hab die VB Jünger hier im Hause etwas geärgert. Ein Freund von mir wird das Ganze
genauso in VB realisieren, dann sehen wir weiter.
Die Wette hab ich damit noch nicht gewonnen aber du hast (ihr habt) mir sehr geholfen.

Vielen herzlichen dank für eure Mühe!
Grüsse
rainer

[MaBuSE]

[edit]
Mist, hätte doch noch mal vor dem posten refresh drücken sollen,
hab das neben der Arbeit gecoded. Deswegen hat etwas gedauert
Uwe hat ja schon "meine" Lösung geposted.
[/edit]

Zitat von R2009:

Am Algorithmus kann ich nur bedingt etwas ändern.

Die meiste Zeit geht durch unnötige Berechnungen drauf.
Da z.B. 2*3 = 3*2 ist, musst Du nur bis zur abgerundeten Wurzel prüfen.

Delphi-Quellcode:

...
{$A8,B-,C-,D-,E-,F-,G+,H-,I-,J-,K-,L-,M-,N+,O+,P-,Q-,R-,S-,T-,U-,V-,W-,X-,Y-,Z1}
procedure TForm1.Button1Click(Sender: TObject);
const
  max_prim = 1000000;
var
  prim: array of cardinal;
  anz_prim: cardinal;
  d, i, w: cardinal;
  Anfg_Zeit: TDateTime;
begin
  // Arraygröße
  setlength(prim,80000); // reicht bei bis zu 1000000

  // Zeitmessung
  Anfg_Zeit := Now;

  // Berechnung
  Prim[1] := 2;
  Prim[2] := 3;
  Prim[3] := 5;
  anz_Prim := 3;
  d := 7;
  repeat
    w := Trunc(Sqrt(D)); // nur bis zur Wurzel testen, da sonst doppelt getestet wird. 2*3 = 3*2
    i := 2; // div 2 ist unnötig, da inc(d,2)
    while (D mod Prim[I] > 0) and  (Prim[i] < w) and (i < anz_Prim) do inc(i);

    If D mod Prim[I] > 0 then
    begin
      inc(anz_Prim);
      Prim[anz_Prim] := D;
    end;

    inc(D,2);
  until (D >= max_Prim);

  // Zeitmessung
  Caption := TimeToStr(now - anfg_zeit);

  // Ausgabe
  lst_ausgabe.Items.BeginUpdate;
  for i := 1 to anz_prim do
  begin
    lst_Ausgabe.Items.Add(IntToStr(Prim[i]) + ' ist eine Primzahl!');
  end;
  lst_ausgabe.Items.EndUpdate;

  // Zeitmessung
  Caption := TimeToStr(now - anfg_zeit);
end;
...

[R2009]

Hihi,

hab gewonnen. Kollege hat mit VB das Ganze nachgeproggt.
Ich bin bei 10 000 000 bei 2 Sekunden er bei ca 4 (bisschen drüber)
Ein Dutzend Leute haben überprüft, dass das auch ja das Gleiche ist.

Was micht etwas wundert ist dass VB so schnell ist. Bisher (zumindest die Versionen die ich kenne)
war da (zur Laufzeit) immer ein Interpreter beteiligt.
Erzeugt das Teil jetzt wirklich Maschinencode?

Grüsse
Rainer

[uoeb7gp]

Hi, also wenns soschnell wie möglich gehen soll, sieh dier mal die hochoptimierten Fastcode routienen an.

Dann bist je nach Prozessor im msec Bereich!

lg.

[rwachtel]

Zitat von R2009:

[...] Was micht etwas wundert ist dass VB so schnell ist. Bisher (zumindest die Versionen die ich kenne)
war da (zur Laufzeit) immer ein Interpreter beteiligt. [...]

...das ist schon ein paar Jährchen her...

Reden wir denn jetzt eigentlich von VB oder von VB.NET?