sehr schneller Rechner gesucht

[mikeslash]

Hallo,
würde mir jemand den Gefallen tun und mein Programm auf einem sehr schnellen Rechner laufen lassen? Mein acht Jahre alter Celeron hat hier keine Chance. Kann aber bestimmt einige Stunden in Anspruch nehmen. Das Programm sucht und ordnet bestimmte binäre Tupel der Collazt-Iteration und speichert das Ergebnis als "MIKES LISTE" im Verzeichnis C. Der Fortschritt im Algorithmus wird als Pixel in einem 500x500 Quadrat angezeigt. Würde die erste Linie schon 5 Minuten dauern, so läuft der Algorithmus mindestens 42 Stunden. Man kann also schnell erkennen, ob sich ein Weitersuchen überhaupt lohnt. Vielleicht kann mein Algorithmus aber auch beschleunigt werden, bin für jeden Tipp dankbar.

Viele Grüße,
Mike

Delphi-Quellcode:

var
  Form1: TForm1;

  b,c,g,u,x,uWert,Grenze: extended;
  i: integer;
  j,y: variant;
  k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12,k13,k14,k15,k16,k17,k18,k19,k20: integer;
    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;
  Liste: TStringList;
  sn: array[0..100] of integer;



implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
begin


  Liste:=TStringList.Create;

  k1:=0; k2:=0; k3:=0; k4:=0; k5:=0; k6:=0; k7:=0; k8:=0; k9:=0; k10:=0;
  k11:=0; k12:=0; k13:=0; k14:=0; k15:=0; k16:=0; k17:=0; k18:=0; k19:=0; k20:=0;
  k21:=0; k22:=0; k23:=0; k24:=0; k25:=0; k26:=0; k27:=0; k28:=0; k29:=0; k30:=0;


  b:=3; u:=0; g:=0; j:=0; y:=0; Grenze:=84141805077; uWert:=30;


  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:=0; c:=b; g:=g+1;

      sn[i]:=1; i:=i+1;
      c:=(3*c+1)/2;
      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;


      if (sn[0]=1) and (sn[1]=0)
      then k1:=k1+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=0)
      then k2:=k2+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=0)
      then k3:=k3+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=0)
      then k4:=k4+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=0)
      then k5:=k5+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=0)
      then k6:=k6+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=0)
      then k7:=k7+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=0)
      then k8:=k8+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=0)
      then k9:=k9+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=0)
      then k10:=k10+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1) and (sn[11]=0)
      then k11:=k11+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1) and (sn[11]=1) and (sn[12]=0)
      then k12:=k12+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1) and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=0)
      then k13:=k13+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1) and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=0)
      then k14:=k14+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1) and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=0)
      then k15:=k15+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1) and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=0)
      then k16:=k16+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1) and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=0)
      then k17:=k17+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=0)
      then k18:=k18+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=0)
      then k19:=k19+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=0)
      then k20:=k20+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=0)
      then k21:=k21+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=1) and (sn[22]=0)
      then k22:=k22+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=1) and (sn[22]=1)  and (sn[23]=0)
      then k23:=k23+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=1) and (sn[22]=1) and (sn[23]=1) and (sn[24]=0)
      then k24:=k24+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=1) and (sn[22]=1) and (sn[23]=1) and (sn[24]=1)
                   and (sn[25]=0)
      then k25:=k25+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=1) and (sn[22]=1) and (sn[23]=1) and (sn[24]=1)
                   and (sn[25]=1) and (sn[26]=0)
      then k26:=k26+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=1) and (sn[22]=1) and (sn[23]=1) and (sn[24]=1)
                   and (sn[25]=1) and (sn[26]=1) and (sn[27]=0)
      then k27:=k27+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=1) and (sn[22]=1) and (sn[23]=1) and (sn[24]=1)
                   and (sn[25]=1) and (sn[26]=1) and (sn[27]=1) and (sn[28]=0)
      then k28:=k28+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=1) and (sn[22]=1) and (sn[23]=1) and (sn[24]=1)
                   and (sn[25]=1) and (sn[26]=1) and (sn[27]=1) and (sn[28]=1)
                   and (sn[29]=0)
      then k29:=k29+1;

      if (sn[0]=1) and (sn[1]=1) and (sn[2]=1) and (sn[3]=1) and (sn[4]=1)
                   and (sn[5]=1) and (sn[6]=1) and (sn[7]=1) and (sn[8]=1)
                   and (sn[9]=1) and (sn[10]=1)  and (sn[11]=1) and (sn[12]=1)
                   and (sn[13]=1) and (sn[14]=1) and (sn[15]=1) and (sn[16]=1)
                   and (sn[17]=1) and (sn[18]=1) and (sn[19]=1) and (sn[20]=1)
                   and (sn[21]=1) and (sn[22]=1) and (sn[23]=1) and (sn[24]=1)
                   and (sn[25]=1) and (sn[26]=1) and (sn[27]=1) and (sn[28]=1)
                   and (sn[29]=1) and (sn[30]=0)
      then k30:=k30+1;



      x:=(g+1)/int(Grenze/250000);
      if frac(x)=0 then begin
                          j:=j+1;
                          if j>500 then begin j:=0; y:=y+1; end;
                          canvas.pixels[30+j,100+y]:=clblack;
                        end;


     end;



    b:=b+2; u:=0;

  until g>Grenze;


   h1:=k2-k1;
   h2:=k3-k2;
   h3:=k4-k3;
   h4:=k5-k4;
   h5:=k6-k5;
   h6:=k7-k6;
   h7:=k8-k7;
   h8:=k9-k8;
   h9:=k10-k9;
   h10:=k11-k10;
   h11:=k12-k11;
   h12:=k13-k12;
   h13:=k14-k13;
   h14:=k15-k14;
   h15:=k16-k15;
   h16:=k17-k16;
   h17:=k18-k17;
   h18:=k19-k18;
   h19:=k20-k19;
   h20:=k21-k20;
   h21:=k22-k21;
   h22:=k23-k22;
   h23:=k24-k23;
   h24:=k25-k24;
   h25:=k26-k25;
   h26:=k27-k26;
   h27:=k28-k27;
   h28:=k29-k28;
   h29:=k30-k29;

   m1:=h2-h1;
   m2:=h3-h2;
   m3:=h4-h3;
   m4:=h5-h4;
   m5:=h6-h5;
   m6:=h7-h6;
   m7:=h8-h7;
   m8:=h9-h8;
   m9:=h10-h9;
   m10:=h11-h10;
   m11:=h12-h11;
   m12:=h13-h12;
   m13:=h14-h13;
   m14:=h15-h14;
   m15:=h16-h15;
   m16:=h17-h16;
   m17:=h18-h17;
   m18:=h19-h18;
   m19:=h20-h19;
   m20:=h21-h20;
   m21:=h22-h21;
   m22:=h23-h22;
   m23:=h24-h23;
   m24:=h25-h24;
   m25:=h26-h25;
   m26:=h27-h26;
   m27:=h28-h27;
   m28:=h29-h28;

   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',

   [floor(m1), floor(m2), floor(m3), floor(m4), floor(m5), floor(m6), floor(m7), floor(m8), floor(m9), floor(m10),
   floor(m11), floor(m12), floor(m13), floor(m14), floor(m15), floor(m16), floor(m17), floor(m18), floor(m19), floor(m20),
   floor(m21), floor(m22), floor(m23), floor(m24), floor(m25), floor(m26), floor(m27), floor(m28)
   ]));

  Liste.SaveToFile('C:\MIKES LISTE.txt');

  showmessage('Fertig');

end;

[Luckie]

Lass das Zeichen weg und stell den Fortschritt anders da. Und vorallem Speichere die Daten wo anders. Bei mir müsste das Programm mit Admin-Rechten laufen und das werde ich bestimmt nicht tun.

[Phoenix]

Also, auf den ersten Blick sieht es so aus, als würdest Du das Array von integern NUR dazu verwenden, nullen und einsen zu speichern. Und das auch nur in den ersten 30 Feldern des 100-teiligen Arrays.

Ich würde daher empfehlen anstelle des arrays SN einen einzigen DOUBLE zu verwenden. Der kann mit seinen 4 byte = 32 bit genau die gleiche Datenmenge abbilden wie Du sie verwendest.

UNd dann würde ich die ganzen Operationen bitweise machen und auch die ganzen Vergleiche auf Bitmasken umstellen.
Das hat den *riesigen* Vorteil, dass ein Bitvergleich über 32 byte genau in einer Rechenoperation auf der CPU erledigt werden kann. Derzeit machst Du bei jedem Durchlauf 30 fakultät viele Indizierte Zugriffe auf das array (die jedesmal ein paar rechenoperationen verwenden), was mit 30 einzelnen Bitweisen operationen zu machen wäre.

Das spart Dir faktoren an Zeit.

[fkerber]

Von zeichnen sehe ich hier allerdings auch nichts, oder?

[Namenloser]

Double? Du meinst wohl longint. Double ist float.

[Phoenix]

Der Canvas - pixel-teil da unter den 'bit' vergleichen und vor der langen zuweisungsreihe in der mitte versteckt ;-)

[Assarbad]

Zitat:

Zitat von Phoenix (Beitrag 1089549)

Ich würde daher empfehlen anstelle des arrays SN einen einzigen DOUBLE zu verwenden. Der kann mit seinen 4 byte = 32 bit genau die gleiche Datenmenge abbilden wie Du sie verwendest.

Does not compute.

Double ist 64bit breit, Single ist 32bit.

ms-help://embarcadero.rs_xe/vcl/System.Double.html

Zitat:

Defines a double-precision floating-point number.

Double is a double-precision real type that is represented with floating-point notation. The range of the Double type is from 5.0 x 10^-324 through 1.7 x 10^308. The size of a Double value is 8 bytes.

NB: du hast allerdings dahingehend recht, daß ein Double verlustlos beliebige 32bit-Integerwerte darstellen kann (also ohne Rundungsverluste).

[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 :cyclops:. 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. :stupid:


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:

Zitat von himitsu (Beitrag 1089579)

OK, selbst wenn Double keine 4 Byte ist ... Double und Bit-Operationen paßt ebensowenig.

Wenn schon, dann Integer/LongInt. :stupid:

Stimmt.

Zitat:

Zitat von himitsu (Beitrag 1089579)

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:

Zitat von himitsu (Beitrag 1089579)

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:

Delphi-Quellcode:

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:

Delphi-Quellcode:

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.

Delphi-Quellcode:

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 :D

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.

[ibp]

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);

[Phoenix]

Und jetzt würde mich die Performance interessieren ;-)

[igel457]

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 ;-)

[Bummi]

statt

Delphi-Quellcode:

if c mod 2 = 0 then

würde ich

Delphi-Quellcode:

if (c AND 1) = 0 then

verwenden....

[Assarbad]

Zitat:

Zitat von igel457 (Beitrag 1089594)

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.

Zitat:

Zitat von Bummi (Beitrag 1089609)

statt

Delphi-Quellcode:

if c mod 2 = 0 then

würde ich

Delphi-Quellcode:

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*

[mikeslash]

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;

[igel457]

Zitat:

Zitat von Assarbad (Beitrag 1089665)

Zitat:

Zitat von igel457 (Beitrag 1089594)

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

Delphi-Quellcode:

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.

Delphi-Quellcode:

    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

Delphi-Quellcode:

  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 :twisted:

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 :stupid: 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

[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 :shock:
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 :-D Mein Vorschlag: Vielleicht kennst du jemanden, der dir das ganze auf CUDA schreiben kann. Ich denke man kann den Algorithmus gut parallelisieren (?).

[mkinzler]

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

[Medium]

DirectX Compute Shader :love:

[turboPASCAL]

Zitat:

Zitat von Medium (Beitrag 1089845)

DirectX Compute Shader :love:

Nvidia Cuda (wer hat der hat..) und nein, das hat nicht unbedingt mit Graphik zu tun.

[mkinzler]

Zitat:

Zitat von turboPASCAL (Beitrag 1089857)

Zitat:

Zitat von Medium (Beitrag 1089845)

DirectX Compute Shader :love:

Nvidia Cuda (wer hat der hat..) und nein, das hat nicht unbedingt mit Graphik zu tun.

http://www.delphipraxis.net/1089842-post29.html
http://www.delphipraxis.net/1089844-post30.html