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 2 von 4     12 34   
Benutzerbild von himitsu
himitsu

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

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 01:34
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.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014

Geändert von himitsu (19. Mär 2011 um 01:38 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Assarbad
Assarbad

Registriert seit: 8. Okt 2010
Ort: Frankfurt am Main
1.175 Beiträge
 
#12

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 03:43
OK, selbst wenn Double keine 4 Byte ist ... Double und Bit-Operationen paßt ebensowenig.

Wenn schon, dann Integer/LongInt.
Stimmt.

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.

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.
Oliver
"... aber vertrauen Sie uns, die Physik stimmt." (Prof. Harald Lesch)

Geändert von Assarbad (19. Mär 2011 um 04:59 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Assarbad
Assarbad

Registriert seit: 8. Okt 2010
Ort: Frankfurt am Main
1.175 Beiträge
 
#13

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 05:30
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.
Oliver
"... aber vertrauen Sie uns, die Physik stimmt." (Prof. Harald Lesch)

Geändert von Assarbad (19. Mär 2011 um 05:32 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von ibp
ibp

Registriert seit: 31. Mär 2004
Ort: Frankfurt am Main
1.511 Beiträge
 
Delphi 7 Architect
 
#14

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 10:51
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);

Geändert von ibp (19. Mär 2011 um 11:00 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Phoenix
Phoenix
(Moderator)

Registriert seit: 25. Jun 2002
Ort: Hausach
7.516 Beiträge
 
#15

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 10:51
Und jetzt würde mich die Performance interessieren
Sebastian P.R. Gingter
不死鳥 Visit my Blog.
Do not argue with an idiot. They lower you to their level and then try to beat you with experience.
  Mit Zitat antworten Zitat
Benutzerbild von igel457
igel457

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

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 10:54
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
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 Bummi
Bummi

Registriert seit: 15. Jun 2010
Ort: Augsburg Bayern Süddeutschland
3.470 Beiträge
 
Delphi XE3 Enterprise
 
#17

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 12:39
statt
if c mod 2 = 0 then würde ich
if (c AND 1) = 0 then verwenden....
Thomas Wassermann H₂♂
Das Problem steckt meistens zwischen den Ohren
DRY DRY KISS
H₂ (wenn bei meinen Snipplets nichts anderes angegeben ist Lizenz: WTFPL)
  Mit Zitat antworten Zitat
Benutzerbild von Assarbad
Assarbad

Registriert seit: 8. Okt 2010
Ort: Frankfurt am Main
1.175 Beiträge
 
#18

AW: sehr schneller Rechner gesucht

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

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*
Oliver
"... aber vertrauen Sie uns, die Physik stimmt." (Prof. Harald Lesch)
  Mit Zitat antworten Zitat
mikeslash

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

AW: sehr schneller Rechner gesucht

  Alt 19. Mär 2011, 15:40
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;

Geändert von mikeslash (19. Mär 2011 um 15:58 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von igel457
igel457

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

AW: sehr schneller Rechner gesucht

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