AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

sehr schneller Rechner gesucht

Ein Thema von mikeslash · begonnen am 18. Mär 2011 · letzter Beitrag vom 20. Mär 2011
Antwort Antwort
Seite 3 von 4     123 4   
Benutzerbild von isilive
isilive

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

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 17: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 18:11 Uhr)
  Mit Zitat antworten Zitat
mikeslash

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

AW: sehr schneller Rechner gesucht

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

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 18: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
 
#24

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 19: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 19:57 Uhr)
  Mit Zitat antworten Zitat
mikeslash

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

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 19: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 21:45 Uhr)
  Mit Zitat antworten Zitat
mikeslash

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

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 22: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 (19. Mär 2011 um 23:30 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
34.931 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#27

AW: sehr schneller Rechner gesucht

  Alt 20. Mär 2011, 08:27
Delphi-Quellcode:
nn := 100;
Clear[x, y]; // arrays X und Y mit 0 füllen
for 0 := 0 to nn+1 do
  x[i] := 0;
x[1] := 1;
for p2 := 2 to nn do begin
  for cnt := 0 to p+1 do begin
    y[cnt] := x[cnt] + x[cnt-1];
    x[cnt] := y[cnt];
  end;
  admis := 0;
  for p := 2 to nn do begin
    If (p + 1 - cnt) * Log[3] < p * Log[2] then begin
      admis := admis + x[cnt];
      x[cnt] := 0;
    end;
  end;
  t[p2] := admis;
end;
//DeleteCases[t, 0] alle nullen ignorieren oder aus dem Array rauslöschen
Hey, Wolfram hat ein paar nette Seiten
damit war das übersetzen ein Leichtes
http://reference.wolfram.com/mathematica/ref/Table.html


und hier auch nochmal
http://www.matheplanet.com/default3....p?topic=146021
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.431 Beiträge
 
Delphi 10.1 Berlin Starter
 
#28

AW: sehr schneller Rechner gesucht

  Alt 20. Mär 2011, 09:03
Computertätigkeiten des schnöden Berechnens, etwas anspruchsvoller des Abarbeitens von Algorithmen können nie die menschlichen Tätigkeiten des Beweisens ersetzen.

Hinzu kommt, daß solche Rechenorgien sich bestenfalls zum Finden eines oder einzelner Fälle finden lassen, die entweder eine Behauptung untermalen oder aber widerlegen (was immerhin eine Falsifikation und damit (sozusagen?) ein indirekter Beweis wäre). Doch auch das ist hier nicht gegeben: Wenn eine Collatzfolge astronomisch wächst, verrät auch dieses Verhalten leider keinerlei Information darob, daß sie - jenseits aller Berechnebarkeit wegen der Beschränkung der Computertechnik - nicht doch noch danach (wieder) zu einem bekannten, der Vermutung entsprechenden Wert in sich zusammenfiele, so daß hier nicht einmal eine Falsifikation möglich ist.

Die Arithmetik hat als Tummelfeld zwar nur die "kleinste" der unendlichen Mengen (genaugenommen eine mit niedrigster Mächtigkeit, die Abzählbarkeit), nämlich die der natürlichen Zahlen, doch auch das sind unendlich viele Zahlen, die zudem noch beliebig groß werden können. Dieser Schrankenlosigkeit hinsichtlich der Anzahl ("alle") und der Größe die Beschränktheit eines Computers entgegenzusetzen, besser:entgegensetzen zu wollen, ist ein aussichtsloser David-Goliath-Kampf. Sie kranken grundsätzlich daran, daß nur das "unterste" und hinsichtlich (bzw. relativ zu) der Gesamtgröße des Untersuchungsobjektes auch nur unendlich kleine Ende überhaupt erfaßt und überprüft wird.

Computer können damit bestenfalls nur als erste Orientierung bezüglich der Verifikation einer Vermutung im Bereich dienen.

Anscheinend enthält das hier vorgestellte Programm kompliziertere mathematische Ideen, um sich dem Wahrheitsgehalt der Collatz-Vermutung zu nähern. Die Halbierung sowie die Verdreifachung plus 1 findet sich allerdings auch hier wieder.

Ein „sehr schneller“ Rechner ist vor allem ein solcher, der möglichst viele Prozessoren bzw. Prozessorkerne enthält, denn die Taktfrequenzerhöhung fand erst einmal ihre Grenze. Mithin wäre eine Parallelisierung des Algorithmus' naheliegend und ratsam.

Geändert von Delphi-Laie (20. Mär 2011 um 09:29 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von isilive
isilive

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

AW: sehr schneller Rechner gesucht

  Alt 20. Mär 2011, 13:43
Also, das ganze hier ist sehr interessant zu lesen. Aber da ich nicht Andrew Wiles heisse, steige ich hier aus Mein Vorschlag: Vielleicht kennst du jemanden, der dir das ganze auf CUDA schreiben kann. Ich denke man kann den Algorithmus gut parallelisieren (?).
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 (20. Mär 2011 um 17:00 Uhr)
  Mit Zitat antworten Zitat
mkinzler
(Moderator)

Registriert seit: 9. Dez 2005
Ort: Heilbronn
39.447 Beiträge
 
Delphi 10.2 Tokyo Enterprise
 
#30

AW: sehr schneller Rechner gesucht

  Alt 20. Mär 2011, 13:46
Dann benötgt man aber eine aktuelle CUDA-fähige NVidia-Grafikkarte. Besser wäre es dann OpenCL zu verwenden, dann täte es auch eine aktuelel von Ati/AMD
Markus Kinzler
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

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 13:12 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf