sehr schneller Rechner gesucht

[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.

[isilive]

Ich denke auch, dass man unbedingt Ganzzahltypen verwenden sollte!

Weiters wäre odd(x) eine schöne Funktion um auf ungerade zu testen. Vielleicht ist sie auch schneller.

Delphi-Quellcode:

      if odd(trunc(c)) then
        begin c:=(3*c+1)/2; u:=u+1; end
        else
          c:=c/2;

Ist das Absicht, dass nur nur ganz wenige Fälle untersuchst. Nämlich wenn es genau 30mal ungerade war. In den allermeisten Fällen ist "u" grösser oder kleiner als 30.
    if u=30 then begin...
In jedem dieser Fälle erhöhst du den Zähler g um eins. Und die Schleife läuft bis
  until g>84141805077; Das sind rund 84 Milliarden.
Auf meinem PhenomII mit 2,5Ghz erhöhrt sich g in einer Minute um 300.
Bis g diesen Wert erreicht, dauert es 217 Mio. Minuten - das sind 513 Jahre.

Du wirst dir wohl einen Superrechner mieten müssen

Ist das alles wirklich so gewollt, oder sind da noch inhaltliche Fehler im Programmablauf?

Weiters denke ich, dass man das Programm um Zehnerpotenzen schneller machen kann durch
- den Einsatz von Ganzzahltypen
- evtl. den Einsatz von Bitmasken (Stichwort AND, OR, XOR)
- den Einsatz von ODD(). Man könnte hier auch eine Assemblerfunktion einbauen, die möglichst schnell ist, falls ODD() nicht eh schon so schnell ist.

Codeoptimierung lohnt sich. Ich hab mal einen Bruteforcer geschrieben, der durch einfache Massnahmen um den Faktor 1000 schneller wurde.

Edit: Durch Umstellung auf Ganzzahltypen schafft mein Rechner jetzt 60.000 pro Minute. Die Gesamtrechenzeit vermindert sich auf 2,5 Jahre Man kann sicher viel weiter optimieren, aber erst möchten wir wissen ob der Programmablauf wirklich so korrekt ist. Was soll dein Programm überhaupt machen? Schreib doch mal Pseudocode hierher, dann können wir das besser verstehen und optimieren.

[mikeslash]

Hallo,
ja, es ist gewollt nur u=30 zu untersuchen, also Zahlen für die die Collatz-Iteration nach 30 ungeraden Schritten eine kleinere als die Ausgangszahl liefert. Die Collatz-Iteration bildet ein dynamisches System, und dieses Chaos macht einen Beweis so schwierig, weil es nicht zu fassen ist. Ich arbeite an einem Algorithmus (beruht auf Generierung und Sortierung spezieller Matrizen), der dieses Chaos zähmt, und bräuchte u=30 dringend zur numerischen Überprüfung. Natürlich wären auch größere u-Werte interessant, aber 30 ist leider der kleinste Wert der von Interesse ist.

[isilive]

Delphi-Quellcode:

    if u=30 then begin
      i:=1; c:=count; 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) div 2;
      repeat
        if not odd(c) then
                      begin
                        c:=c div 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;
                      end
                    else begin
                        c:=(3*c+1) div 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;
                        end;
      inc(i);
      until i > u;

Nachdem u an dieser Stelle 30 ist - wird die Schleife 30x durchlaufen. Du wertest aber nur die ersten 9 mal aus.
Weiters wäre es hier besser ein Array zu benutzen:

Delphi-Quellcode:

var:       
      s: array [1..8] of byte;
            
    if u=30 then begin
      c:=count;
      i:=1; 
      inc(g);
      c:= (3*c +1) div 2;

      repeat
        if odd(c) then
            begin
              c:=(3*c+1) div 2
              s[i] := 1;
            end
          else
            begin 
              c:=c div 2;
              s[i] := 0;
            end
            
      inc(i);
      until i > 8;
      
      if s[0]=1 and s[1]=1 and s[2]=1 and s[3]=1 and s[4]=1 and s[5]=1 then ...

Ein Array of Bool wäre natürlich noch eleganter, aber so sollte es fürs erste funktionieren.

[isilive]

Delphi-Quellcode:

var
  Form1: TForm1;
  Liste: TStringList;

  count,c,g,u: int64;
  k6,k7,k8:int64;
  h6,h7,m6: int64; // die können Integer vielleicht überschreiten!
  i:byte;
  s0,s1,s2,s3,s4,s5,s6,s7,s8: byte;
  FRun : Bool;

implementation
{$R *.DFM}

procedure TForm1.BStartClick(Sender: TObject);
var s: array [1..8] of byte;
begin
  FRun := True;
  count:=3;
  u:=0; g:=0;
  k6:=0; k7:=0; k8:=0;   // variablen für auswertung

  repeat        //1
    c := count;

      repeat       //2
        if odd(c) then
          begin c:=(3*c+1) div 2; inc(u); end
          else
            c:=c div 2;

        if u > 30 then break;
      until (c < count) and (odd(c) );    //2

    if u=30 then begin
      c:=count;
      i:=1;
      inc(g);   //zählt wie oft dieser fall eintritt

      c:= (3*c +1) div 2;

      repeat
        if odd(c) then
            begin
              c:=(3*c+1) div 2;
              s[i] := 1;          //wir merken uns, dass die iteration[i] ungerade ist
            end
          else
            begin
              c:=c div 2;
              s[i] := 0;
            end;

      inc(i);
      until i > 8;

      i:=1;
      while s[i]=1 do inc(i);   //liefert den index von der ersten 0
      if i=6 then inc(k6);
      if i=7 then inc(k7);
      if i=8 then inc(k8);

     end;

    inc(count,2);
    u:=0;

    if (count AND $FFFE) = 0 then
      begin
        application.ProcessMessages;
        if not frun then exit;
        label1.Caption := inttostr(count);
        label2.Caption := 'g:' + inttostr(g);
        label3.Caption := 'k6:' + inttostr(k6);
        label4.Caption := 'k7:' + inttostr(k7);
        label5.Caption := 'k8:' + inttostr(k8);
      end;

  until g>84141805077;         //1

   h6:=k7-k6;    h7:=k8-k7;    m6:=h7-h6;
   Liste:=TStringList.Create;
   Liste.Add('k6: '+inttostr(k6));
   Liste.Add('k7: '+inttostr(k7));
   Liste.Add('k8: '+inttostr(k8));
   Liste.Add('m6: '+inttostr(m6));
   Liste.SaveToFile('MIKES LISTE.txt');
   Liste.Free;
   Showmessage('Fertig');
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
  FRun := false;
end;

Die weiteren kleinen Optimierungen wirken sich aus: 150.000 pro Minute (für 'g') bei 2,5Ghz - single threaded. Laufzeit bis 84Mrd: 12 Monate. Wie bist du eigentlich auf diese 84Mrd. Zahl gekommen? Ist diese Zahl fix?
Wenn wir g auf 1 bis 10 Mrd. reduzieren können, kommen wir in einen Bereich der für einen normalen PC realistisch wird! Geht das?

(Andererseits wäre eine Variante den Code Multithreaded laufen zu lassen, wenn möglich - da könnte man 4-8x schneller werden. Oder man portiert das ganze auf CUDA und lässt es eine Geforce rechnen. Ich kann mir vorstellen, dass man da noch 100x schneller wird.)

[mikeslash]

Das ist die Grenze der sogenannten Stoppzeit, danach wiederholt sich alles modulomäßig. Bis 2^48 gibt es genau 84141805077 ungerade Zahlen für die die Collatz-Iteration nach 30 ungeraden Schritten eine kleinere Zahl liefert. Die 48 ergibt sich aus ceil(u*ln3/ln2).

Hier gibts einen kleinen Überblick.

http://oeis.org/A100982
Mit dieser liste kann man den Algorithmus für kleinere u testen. Für u=20 ist g=5936673 und m6=45729.
Vielleicht kann der angegebene Mathematica Code hilfreich sein.

http://www.jstor.org/pss/2044308

Vielleicht wäre es möglich formelmäßig bestimmte ungerade Zahlen b auszuschließen.

[mikeslash]

Mit diesem Mathematica Code kann man die 84 Mrd. releavanten Zahlen finden. Man spart sich so den ersten Collatz-Abfrageteil. Er stammt von dem ersten Link. Dieser Mr. Noe hat damit alle Zahlen bis u=500 gezählt, der Zähl-Algorithmus muss also wahnsinnig schnell sein. Ich verstehe ihn aber nicht richtig.

Delphi-Quellcode:

ACHTUNG MATHEMATICA
nn=100; 
Clear[x, y]; 
Do[x[i]=0, {i, 0, nn+1}];
x[1]=1;
t=Table[Do[y[cnt]=x[cnt]+x[cnt-1], {cnt, p+1}]; 
Do[x[cnt]=y[cnt], {cnt, p+1}]; 
admis=0; 
Do[If[(p+1-cnt)*Log[3]<p*Log[2], admis=admis+x[cnt];
x[cnt]=0], {cnt, p+1}]; 
admis, {p, 2, nn}]; 
DeleteCases[t, 0]

Unter diesem Link ist noch ein Stoppzeit-Algorithmus in Mathematica.
http://oeis.org/A177789