sehr schneller Rechner gesucht

[himitsu]

OK, selbst wenn Double keine 4 Byte ist ... Double und Bit-Operationen paßt ebensowenig.

Wenn schon, dann Integer/LongInt.


Also das Integer-Array auf einen Integer und Bit-Operationen runterkürzen,
und dann kann man bestimmt auch die ganzen Fließkomma-Operationen auf einen Int64 beschränken.
Zumindestens sollten sich so bestimmt locker mal über 90% des Codes und damit von der Laufzeit einsparen lassen.

[Assarbad]

Zitat von himitsu:

OK, selbst wenn Double keine 4 Byte ist ... Double und Bit-Operationen paßt ebensowenig.

Wenn schon, dann Integer/LongInt.

Stimmt.

Zitat von himitsu:

Also das Integer-Array auf einen Integer und Bit-Operationen runterkürzen,

Das wüßte ich gern genauer. Was soll das bringen? Die kleinste Einheit die der Prozessor modifizieren kann ist: ein Byte. Was soll es da also bringen (außer Platzeinsparung) das zu tun? Wir reden hier ja nicht von mehreren Megabyte mit einem Array von Einsen und Nullen und einer Beschränkung der verfügbaren RAM-Menge bei der uns das juckt (siehe "Programming Pearls" und mehrere der darin beschriebenen Probleme). Schneller ist es jedenfalls unter normalen Umständen schon deshalb nicht, weil eine 32bit-CPU schneller ist mit einem Befehl eine Null oder Eins an eine Speicherstelle zu schreiben als in mehreren Operationen genau das Bit zu modifizieren was man eben gerade modifizieren wollte (was auch an eine Speicherstelle schreibt aber zusätzlich AND, OR oder NOT braucht, je nach Fall ... von den bedingten Sprüngen nicht zu reden) ...

Wenn du jetzt mit einer revolutionären Methode aufwarten kannst mit der man Bits sehr einfach als Array benutzen kann, ohne Laufzeitverluste, dann interessiert das sicher nicht nur mich

Einfügung: Unbenommen der obigen Aussagen, scheint hier ein Fall gegeben zu sein wo man in der Tat mit Bitmasken arbeiten könnte. Und dann sollte der Laufzeitverlust sich in der Tat umkehren. Sorry, das hatte ich übersehen.

Zitat von himitsu:

und dann kann man bestimmt auch die ganzen Fließkomma-Operationen auf einen Int64 beschränken.
Zumindestens sollten sich so bestimmt locker mal über 90% des Codes und damit von der Laufzeit einsparen lassen.

Daß Gleitkommaoperationen langsamer sind - und nichts anderes sagst du - ist seit einigen Jahren nur noch ein schönes Märchen. Das war in der Tat so, bspw. als FPU und CPU noch in verschiedenen Sockeln steckten usw. - inzwischen aber nicht mehr. Es hängt zwar vom Einzelfall und benutzten Operationen ab, aber eine verallgemeinernde Aussage wie die, daß Gleitkommaoperationen generell langsamer seien, ist nicht haltbar.

[Assarbad]

So, und jetzt nochmal zum Thema selber. Mir sind da einige Unstimmigkeiten aufgefallen:

j,y: variant; Variants sind langsam, weil sie künstlich zusammengefaßte Typen sind. Warum sollte - angesichts der Nutzung dieser beiden Variablen als Integer - das notwendig sein?

Delphi-Quellcode:

k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12,k13,k14,
k15,k16,k17,k18,k19,k20,k21,k22,k23,
k24,k25,k26,k27,k28,k29,k30: integer;
h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11,h12,h13,h14,h15,
h16,h17,h18,h19,h20,h21,h22,h23,h24,
h25,h26,h27,h28,h29: integer;
m1,m2,m3,m4,m5,m6,m7,m8,m9,m10,m11,m12,m13,m14,m15,
m16,m17,m18,m19,m20,m21,m22,m23,m24,
m25,m26,m27,m28: integer;

Der Sinn erschließt sich mir nicht vollständig, aber als Array, statt als Einzelvariablen mit numerischem Anhängsel im Namen, könnte es an Lesbarkeit gewinnen.

"uWert" wird im gesamten Code nur als Konstante verwendet. Es ist schöne Tradition das dann auch so zu deklarieren, womit versehentlichen Modifikationen auch gleich vorgebeugt wäre ...
Gleiches gilt im Übrigen für "Grenze".

Das hier:
floor(m1), ... floor(m28) ... is auch Moppelkotze. Wenn m1..m28 schon Integer sind, warum sie dann implizit zu Gleitkommazahlen machen und dann versuchen den Ganzzahlteil zu ermitteln, den wir ja schon kennen?

Ansonsten schließe ich mich bei diesem Teil den Vorrednern an, daß die Fortschrittsanzeige hier sinnlos ist. Zumal man einen Canvas auch im Speicher halten kann und dorthin schreiben, anstatt - wie du es machst - direkt jeden einzelnen Pixel anzuzeigen (was seeeeehr verlangsamend wirken dürfte).

Ach ja und "Liste" wird nirgends freigegeben.

sn: array[0..100] of integer; Siehe Aussage von Phoenix und himitsu, mach einen 32bit-Integer draus. Nennen wir diesen doch einfach auch sn. Dann können wir schreiben:

Delphi-Quellcode:

      // sn: LongWord; // <--- wichtig
      // Benutzt die Variablen wie im Original, statt Array)
      if ((sn and $00000003) = $00000001) then Inc(k1);
      if ((sn and $00000007) = $00000003) then Inc(k2);
      if ((sn and $0000000F) = $00000007) then Inc(k3);
      if ((sn and $0000001F) = $0000000F) then Inc(k4);

      // für k5 ... k28 auch

      if ((sn and $3FFFFFFF) = $1FFFFFFF) then Inc(k29);
      if ((sn and $7FFFFFFF) = $3FFFFFFF) then Inc(k30);

... das gewinnt schon deutlich an Lesbarkeit

Aber es geht noch besser.

Man sollte natürlich Berechnung und Fortschritt trennen, was ich hier einfach mal über eine Callback-Funktion mache. Desweiteren sind alle diese globalen Variablen nicht nur schlechter Stil sondern auch sinnlos. Und damit Luckie nicht wieder wegen der Speicherung in C:\ meckert, habe ich die Ergebnisse ins aktuelle Verzeichnis verlegt.

Delphi-Quellcode:

uses
  Math;

const
  uWert = 30;

type
  TMWerte = array[1..uWert-2] of Integer;
  TFNCallback = procedure(const j, y: Integer); stdcall;

procedure Berechnung(var m: TMWerte; pfnCallback: TFNCallback = nil);
const
  Grenze = 84141805077;
  // Warum ich das als Konstanten mache und nicht im Code befülle, sollte klar
  // sein. Nein, es geht nicht um die Geschwindigkeit ... ;)
  Bitmask : array[1..uWert] of LongWord = (
    $00000003,
    $00000007,
    $0000000F,
    $0000001F,
    $0000003F,
    $0000007F,
    $000000FF,
    $000001FF,
    $000003FF,
    $000007FF, // 10
    $00000FFF,
    $00001FFF,
    $00003FFF,
    $00007FFF,
    $0000FFFF,
    $0001FFFF,
    $0003FFFF,
    $0007FFFF,
    $000FFFFF,
    $001FFFFF, // 20
    $003FFFFF,
    $007FFFFF,
    $00FFFFFF,
    $01FFFFFF,
    $03FFFFFF,
    $07FFFFFF,
    $0FFFFFFF,
    $1FFFFFFF,
    $3FFFFFFF,
    $7FFFFFFF
  );
  Comparand : array[1..uWert] of LongWord = (
    $00000001,
    $00000003,
    $00000007,
    $0000000F,
    $0000001F,
    $0000003F,
    $0000007F,
    $000000FF,
    $000001FF,
    $000003FF, // 10
    $000007FF,
    $00000FFF,
    $00001FFF,
    $00003FFF,
    $00007FFF,
    $0000FFFF,
    $0001FFFF,
    $0003FFFF,
    $0007FFFF,
    $000FFFFF, // 20
    $001FFFFF,
    $003FFFFF,
    $007FFFFF,
    $00FFFFFF,
    $01FFFFFF,
    $03FFFFFF,
    $07FFFFFF,
    $0FFFFFFF,
    $1FFFFFFF,
    $3FFFFFFF
  );
var
  i : Byte;
  b,c,g,u,x: extended;
  j, y: Integer;
  k : array[1..uWert] of Integer;
  h : array[1..uWert-1] of Integer;
  sn: LongWord; // Bitmaske, 30 Bits genutzt
begin
  // Alles in k ausnullen
  FillChar(k, sizeof(k), 0);
  sn := 0;

  b:=3; u:=0; g:=0; j:=0; y:=0;

  repeat
    c:=b;
    repeat
      if frac((c+1)/2)=0 then
      begin
        c:=(3*c+1)/2; u:=u+1;
      end;
      if frac(c/2)=0 then c:=c/2;
      if u>uWert then break;
    until (c<b) and (frac((c+1)/2)=0);

    if u=uWert then
    begin
      i:=1; c:=b; g:=g+1;

      sn := sn or 1;
      c:=(3*c+1)/2;
      repeat
        if frac(c/2)=0 then
        begin
          sn := sn and (not (1 shl i));
          Inc(i);
          c:=c/2;
        end
        else
        begin
          sn := sn or (1 shl i);
          Inc(i);
          c:=(3*c+1)/2;
        end;
      until i>u;

      for i := 1 to uWert do
      begin
        if ((sn and Bitmask[i]) = Comparand[i]) then Inc(k[i]);
      end;

      x:=(g+1)/int(Grenze/250000);
      if frac(x)=0 then
      begin
        Inc(j);
        if j>500 then
        begin
          j:=0;
          Inc(y);
        end;
        if (Assigned(pfnCallback)) then pfnCallback(j, y);
      end;
    end;
    b:=b+2; u:=0;
  until g>Grenze;

  for i := 1 to uWert - 1 do
  begin
    h[i] := k[i+1] - k[i];
  end;

  for i := 1 to uWert - 2 do
  begin
    m[i] := h[i+1] - h[i];
  end;
end;

procedure MeineCallback(const j, y: Integer); stdcall;
begin
  Form1.Canvas.Pixels[30+j,100+y]:=clblack;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Liste: TStringList;
  m : TMWerte;
begin
  //Berechnung(m, MeineCallback); // mit arschlangsamer Anzeige
  Berechnung(m);

  Liste:=TStringList.Create;
  Liste.Add(Format('%d %d %d %d %d %d %d %d %d %d %d %d ' +
   '%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d',
   [m[1], m[2], m[3], m[4], m[5], m[6], m[7], m[8], m[9], m[10],
   m[11], m[12], m[13], m[14], m[15], m[16], m[17], m[18], m[19], m[20],
   m[21], m[22], m[23], m[24], m[25], m[26], m[27], m[28] ]));

  Liste.SaveToFile('MIKES LISTE.txt');
  Liste.Free();
  ShowMessage('Fertig');
end;

Ja ja, die konstanten Arrays könnten auch außerhalb der Funktion deklariert werden. Ist aber alles Kosmetik.

[ibp]

also wenn ich es richtig verstanden habe, dann könnte man den ganzen Überprüfungsteil sich sparen indem man den folgenden Teil umschreibt....

Delphi-Quellcode:

repeat
  if frac(c/2)=0 then begin sn[i]:=0; i:=i+1; c:=c/2; end
             else begin sn[i]:=1; i:=i+1; c:=(3*c+1)/2; end;
until i>u;

in...

Delphi-Quellcode:

k : array[1..30] of integer;
sn:integer;
//..
// initialisieren alle k[] = 0 
//..   
kpos=1;
sn=0;
repeat
  if frac(c/2)=0 then 
  begin 
    k[i]=k[i]+1;
    c:=c/2; 
  end
  else 
  begin 
    sn:=1;  
    c:=(3*c+1)/2; 
  end;
            
  i:=i+1;                  
until (i>u) and (sn=0);

[Phoenix]

Und jetzt würde mich die Performance interessieren

[igel457]

Und bitte Integer und div und mod verwenden (Verwendung von Fließkommazahlen kann hier außerdem zu Fehlern führen!):

Delphi-Quellcode:

k : array[1..30] of integer;
sn:integer;
//..
// initialisieren alle k[] = 0
//..   
kpos=1;
sn=0;
repeat
  if c mod 2 = 0 then
  begin
    k[i] := k[i] + sn;
    c := c div 2;
  end
  else
  begin
    sn := 1;
    c := (3 * c + 1) div 2;
  end;
            
  i:=i+1;               
until (i>u) and (sn=0);

Jetzt würde mich die Performance interessieren

[Bummi]

statt
if c mod 2 = 0 then würde ich
if (c AND 1) = 0 then verwenden....

[Assarbad]

Zitat von igel457:

Und bitte Integer und div und mod verwenden (Verwendung von Fließkommazahlen kann hier außerdem zu Fehlern führen!)

Könntest du das mal erklären? Ich habe mich nicht bemüht den Code tiefergehend zu verstehen, sondern ihn nur "refactored". Zu der Annahme Gleitkomma-Arithmetik seien generell langsamer hatte ich weiter oben schonmal etwas geschrieben.

Zitat von Bummi:

statt
if c mod 2 = 0 then würde ich
if (c AND 1) = 0 then verwenden....

Braucht dann aber auch ein wenig Erklärung. Wie vielleicht meine Bitmasken oben auch - war aber schon zu müde *gähn*

[mikeslash]

Hallo,
ich muss gestehen, dann ich eure letzten Antworten nur eben gerade überflogen habe. Deshalb kann ich noch nicht darauf eingehen. Aber vielen Dank dafür. Ich habe bis gerade meinen Algorithmus sehr vereinfacht. Mir genügt erstmal ein einziger Wert zur Überprüfung des Sachverhalts. So habe ich alles andere rausgeschmissen und auf die arrays verzichtet. Mein Code sieht jetzt so aus. Mit euren Tipps geht es aber bestimmt noch schneller. Was aber vor allem Zeit frist, ist die Collatz-Iteration selbst in einem so großen Zahlenbereich.

Delphi-Quellcode:

var
  Form1: TForm1;
  
  b,c,g,u: extended;
  k6,k7,k8,h6,h7,m6: extended;  // die können Integer vielleicht überschreiten!
  i,s0,s1,s2,s3,s4,s5,s6,s7,s8: byte;
  Liste: TStringList;

procedure TForm1.Button1Click(Sender: TObject);
begin

  Liste:=TStringList.Create;

  k6:=0; k7:=0; k8:=0; b:=3; u:=0; g:=0;

 
  repeat

    c:=b;
    repeat
      if frac((c+1)/2)=0 then begin c:=(3*c+1)/2; u:=u+1; end;
      if frac(c/2)=0 then c:=c/2;

      if u>30then break;

    until (c<b) and (frac((c+1)/2)=0);



    if u=30 then begin

      i:=1; c:=b; g:=g+1;

      s0:=0; s1:=0; s2:=0; s3:=0; s4:=0; s5:=0; s6:=0; s7:=0; s8:=0;

      c:=(3*c+1)/2;
      repeat
        if frac(c/2)=0 then begin c:=c/2;
                                  if i=1 then s0:=0;
                                  if i=2 then s1:=0;
                                  if i=3 then s2:=0;
                                  if i=4 then s3:=0;
                                  if i=5 then s4:=0;
                                  if i=6 then s5:=0;
                                  if i=7 then s6:=0;
                                  if i=8 then s7:=0;
                                  if i=9 then s8:=0;
                                  i:=i+1;
                            end

                       else begin c:=(3*c+1)/2;
                                  if i=1 then s0:=1;
                                  if i=2 then s1:=1;
                                  if i=3 then s2:=1;
                                  if i=4 then s3:=1;
                                  if i=5 then s4:=1;
                                  if i=6 then s5:=1;
                                  if i=7 then s6:=1;
                                  if i=8 then s7:=1;
                                  if i=9 then s8:=1;
                                  i:=i+1;
                        end;
      until i>u;


      if (s0=1) and (s1=1) and (s2=1) and (s3=1) and (s4=1) and (s5=1) and (s6=0)
       then k6:=k6+1;

      if (s0=1) and (s1=1) and (s2=1) and (s3=1) and (s4=1) and (s5=1) and (s6=1) and (s7=0)
       then k7:=k7+1;

      if (s0=1) and (s1=1) and (s2=1) and (s3=1) and (s4=1) and (s5=1) and (s6=1) and (s7=1) and (s8=0)
       then k8:=k8+1;

     end;


    b:=b+2; u:=0;

  until g>84141805077;


   h6:=k7-k6;
   h7:=k8-k7;
   m6:=h7-h6;

   Liste.Add(Format('%d',[floor(m6)]));
   Liste.SaveToFile('F:\MIKES LISTE.txt');

   showmessage('Fertig');


end;

[igel457]

Zitat von Assarbad:

Zitat von igel457:

Und bitte Integer und div und mod verwenden (Verwendung von Fließkommazahlen kann hier außerdem zu Fehlern führen!)

Könntest du das mal erklären? Ich habe mich nicht bemüht den Code tiefergehend zu verstehen, sondern ihn nur "refactored". Zu der Annahme Gleitkomma-Arithmetik seien generell langsamer hatte ich weiter oben schonmal etwas geschrieben.

Wenn ich das dem Wikipedia-Artikel richtig entnommen habe (http://de.wikipedia.org/wiki/Collatz-Problem) geht es um folgen ganzer Zahlen. Die Abfrage frac(c/2) = 0 überprüft ob der Nachkommateil der Division gleich null ist, die Zahl also gerade. Schleichen sich für den Wert von "c" also irgendwo Fehler ein (da Gleitkommazahlen ja bekanntlich nicht mathematisch korrekt rechnen), so ist "frac(c / 2)" ungleich null, obwohl "c" vielleicht eigentlich gerade sein sollte.

Deshalb: Probleme mit Ganzzahlen gleich mit Ganzzahlarithmetik lösen. "c mod 2" gibt den Teilerrest der Division durch zwei zurück - dieser ist dann null wenn die Zahl gerade ist. "c and 1 = 0" macht das gleiche - stellt also sicher, ob die letzte Stelle im binären Stellenwertsystem (1) nicht gesetzt ist und die Zahl somit gerade. Letztere Optimierung ist aber IMHO unnötig, das sollte der Compiler automatisch machen.