sehr schneller Rechner gesucht

[divBy0]

Bin erst nächstes Wochenende wieder zu Hause, könnte deinen Code dann mal mit einem Intel Core i7-970 (3.2GHz, 6.4GT/s, 12MB) testen.

Allerdings läuft dein Code ja nur auf einem von sechs Kernen.

[mikeslash]

Oh, ich hätte gedacht, dass sich das automatisch auf alle Kerne verteilt. Kann man es denn auch so programmieren, dass alle Kerne genutzt werden?

Gruß, Mike

[Medium]

Pro Thread ein Kern --> Aufteilung auf mehrere parallel arbeitende Threads. Nicht jedes Problem ist allerdings parallelisierbar, und bei nicht jedem ist die Eignung offensichtlich, bzw. muss sie erst hergestellt werden. Ich hab jetzt leider nicht mehr die Wachheit das in diesem Fall zu überblicken . Sobald der Fall gegeben ist, dass Teilergebnisse nicht von der Gesamtheit voriger Ergebnisse abhängen, ist Parallelisierung in der Regel möglich. Automatisch passiert in diese Richtung aber nix.

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

[Phoenix]

Und jetzt würde mich die Performance interessieren

[himitsu]

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

[Delphi-Laie]

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.

[isilive]

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 (?).