AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

sehr schneller Rechner gesucht

Ein Thema von mikeslash · begonnen am 18. Mär 2011 · letzter Beitrag vom 20. Mär 2011
Antwort Antwort
Benutzerbild von igel457
igel457

Registriert seit: 31. Aug 2005
1.622 Beiträge
 
FreePascal / Lazarus
 
#1

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 16:45
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.
Andreas
"Sollen sich auch alle schämen, die gedankenlos sich der Wunder der Wissenschaft und Technik bedienen, und nicht mehr davon geistig erfasst haben als die Kuh von der Botanik der Pflanzen, die sie mit Wohlbehagen frisst." - Albert Einstein
  Mit Zitat antworten Zitat
Benutzerbild von isilive
isilive

Registriert seit: 15. Okt 2008
Ort: Österreich
192 Beiträge
 
Delphi 2009 Professional
 
#2

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 18:31
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.
Stefan
Jedoch kann die referenzbasierte Implementierung des Standard-Objektmodells in Kombination mit den komplexen syntaktischen Dereferenzierungsregeln bei einer objektorientierten API wie ein Stolperstein wirken.

Geändert von isilive (19. Mär 2011 um 19:11 Uhr)
  Mit Zitat antworten Zitat
mikeslash

Registriert seit: 28. Feb 2010
18 Beiträge
 
#3

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 19:23
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.
  Mit Zitat antworten Zitat
Benutzerbild von isilive
isilive

Registriert seit: 15. Okt 2008
Ort: Österreich
192 Beiträge
 
Delphi 2009 Professional
 
#4

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 19:32
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.
Stefan
Jedoch kann die referenzbasierte Implementierung des Standard-Objektmodells in Kombination mit den komplexen syntaktischen Dereferenzierungsregeln bei einer objektorientierten API wie ein Stolperstein wirken.
  Mit Zitat antworten Zitat
Benutzerbild von isilive
isilive

Registriert seit: 15. Okt 2008
Ort: Österreich
192 Beiträge
 
Delphi 2009 Professional
 
#5

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 20:30
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.)
Stefan
Jedoch kann die referenzbasierte Implementierung des Standard-Objektmodells in Kombination mit den komplexen syntaktischen Dereferenzierungsregeln bei einer objektorientierten API wie ein Stolperstein wirken.

Geändert von isilive (19. Mär 2011 um 20:57 Uhr)
  Mit Zitat antworten Zitat
mikeslash

Registriert seit: 28. Feb 2010
18 Beiträge
 
#6

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 20:57
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.

Geändert von mikeslash (19. Mär 2011 um 22:45 Uhr)
  Mit Zitat antworten Zitat
mikeslash

Registriert seit: 28. Feb 2010
18 Beiträge
 
#7

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 23:47
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

Geändert von mikeslash (20. Mär 2011 um 00:30 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:39 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz