Pythagoras-Zahlen

Mathematiker · Verfasst: Di 04.12.12 12:00

Und es geht noch schneller.
Beginnt man die 2.Schleife bei a+1; a=b ergibt nie ein pythagoreisches Tripel, und ändert diese z.B. in eine repeat-until-Schleife, dann kann man b immer um 2 erhöhen. a und b sollen ja teilerfremd sein.
Aus dieser Schleife steigt man mit dem Th69-Vorschlag aus.

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Weiterhin reicht es reicht mM, nur ggt(a,b) zu berechnen und sich die beiden anderen zu sparen (auch wenn sie schnell berechnet werden).

Ich behaupte: Wenn ggt(a,b)=1 und a^2 + b^2 = c^2, dann auch ggt(a,c)=ggt(b,c)=1. Beweis: Wenn zB ggt(a,c)=d größer 1 wäre, dann wäre b^2 = c^2 - a^2 = (c-a)*(c+a) durch d^2 teilbar, also b durch d, also ggt(a,b) >= d > 1. Widerspruch! Oder sehen die Mathespezialisten einen Fehler in der Argumentation? Auch jeden Fall gibt es im Anika-Bereich kein Gegenbeispiel!

Horst_H · Verfasst: Di 04.12.12 14:00

Hallo,

so scheint es auch bis 100000 ( NativeInt ist bei mir 64-Bittig, deshalb kein Überlauf bei Summe der Quadrate ) zu sein:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:

{$IFDEF FPC}
  {$MODE Delphi}
{$else}
  {$Apptype Console}
{$ENDIF}
uses
  sysutils;
const
  max = 100000;  
var
  T1,T0: TDateTime;
  Wur  : double;
  a,b,c,aMax,
  cnt1 : NativeInt; 
  
function ggt(zahl1,zahl2:NativeInt):NativeInt;
  var 
    rest:integer;
  begin
    repeat
      rest:=zahl1 mod zahl2;
      zahl1:=zahl2;
      zahl2:=rest;
    until rest=0;
    Result:=zahl1;
  end;
begin  
  T0 := now;
 cnt1 := 0;// Unter 3 gibt es keins
 for a:= 3 to max do
   begin
   aMax := trunc(sqrt(sqr(max)-sqr(a))); 
   for b:=a+1 to aMax do
     begin
     Wur := sqrt(sqr(a) + sqr(b));
     c := trunc(Wur);
     if c = Wur then
       begin
       IF (ggt(a,b)<>1) then
         continue;        
       inc(cnt1);
       IF (ggt(c,a)<>1) OR (ggt(c,b)<>1) then
         writeln(Format('%d %d %d', [a, b, c]));
       end;
     end;
   end;
  T1 := now;   
  writeln(' Anzahl: ',cnt1);
  writeln(FormatDateTime('HH:NN.SS.ZZZ',T1-T0));
end.
{Ausgabe
Anzahl: 15919
00:01.54.717
}

Was auffällig ist: Die Anzahl steigt linear.
Etwa 395 bei 2500.

Gruß Horst

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Die Linearität scheint asymptotisch gegeben zu sein mit Anzahl = ln(1+sqrt(2))2/Pi^2*max + O(sqrt(max)), gefunden über Wiki in diesem Artikel. Die Formel des Authors enthält einen zusätzlichen Faktor 2, da er sich nicht auf a < b beschränkt. Sonderlich gut ist sie für Deine Werte max=2500 und 100000 allerdings nicht: Deine Anzahlen sind 395 und 15919, nach der Formel 446 bzw. 17860.

Gausi · Verfasst: Di 04.12.12 14:59

/OT Dieser Thread ist toll. Eine recht einfache Frage, ein paar einfache Lösungsansätze, und dann kommen ein paar Nerds(*) an und kapern den Thread. :lol:

Fast so schön wie eine Diskussion zum Sortieren, die in "wie optimiere ich Bubblesort durch Assembler" ausartet.

Weitermachen. :zustimm:

(*) Ist nicht negativ gemeint - spätestens seit The Big Bang Theory sind die ja voll gesellschaftsfähig. ;-)

_________________
We are, we were and will not be.

Ralf Jansen · Verfasst: Di 04.12.12 15:16

Zitat:

und dann kommen ein paar Nerds(*) an und kapern den Thread.

Nerd ist ok aber bitte politisch korrekt 'NerdInnen' mit Binnenmajuskel um alle hier Beteiligten anzusprechen

Wobei der nerdige Teil eher an denen vorbei ging :gruebel:

Horst_H · Verfasst: Di 04.12.12 15:24

Hallo,

ich habe mal Zahlen aus Seite 4 aus der pdf Kopiert.
Anzahl phytagoräischer Tripel mit a,b < n ( Hier im topic war nach a,b,c < n gefragt )

Ich weiß nicht, wie man da nicht etwas asymptotische Lineares sehen kann?
Bei 1 Millionen ist der rel. Unterschied zu 1 Milliarden 7e-5

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

         n       ̃P(n) ( Anzahl phytagoräischer Tripel mit a,b < n
        10         2
        50        16
       100        36
       500       180
      1000       358
      5000      1780
     10000      3576
     50000     17856
    100000     35722
    500000    178600
   1000000    357200
   5000000   1786016
  10000000   3572022
  50000000  17860382
 100000000  35720710
 200000000  71441356
 300000000 107162112
 400000000 142882968
 500000000 178603536
 600000000 214324350
 700000000 250045106
 800000000 285765804
 900000000 321486520
1000000000 357207278

Gruß Horst

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Ja das sieht linear aus, aber Du must Dich entscheiden, ob Du Deinem Programm oder deren Zahlen traust. Unter der Voraussetzung, daß die Anzahlen mit dem Faktor 2 zu bearbeiten sind, hast Du für max=100000 den Wert 2*15919=31838, das Papier die Werte (gezählt?) 35722, theoretisch 35 721. Für eine Fehler O(sqrt(n)) sehen die Zahlen im Papier mM viel zu gut aus!

Edit: Sehe gerade beim nochmaligen Durchschauen des Papiers, daß die Situationen nicht komplett identisch sind: Wir haben a < b <= max und c <= max; die haben die Einschränkung c <= max nicht, d.h wir würden in dem Bildchen nicht das Quadrat sondern nur den Viertelkreis, und deshalb kleinere Zahlen haben.

Horst_H · Verfasst: Di 04.12.12 16:50

Hallo,

Dein Edit habe ich doch angemerkt:

Zitat:

Anzahl phytagoräischer Tripel mit a,b < n ( Hier im topic war nach a,b,c < n gefragt )

Mich wundert eher, wie sie es in endlicher Zeit geschafft haben, diese Zahlen 1e9 zu erzeugen zu zählen.
Aber www.arndt-bruenner.d...ts/pythagotripel.htm hat ja mehrere Wege dorthin, wie man am Beispiel für c=85 sieht.
Es wird nur c variiert und keine zwei Schleifen ineinander geschachtelt, was quadratische Lauftzeit hat.

Gruß Horst

Mathematiker · Verfasst: Di 04.12.12 19:15

Hallo,
die Anzahl pythagoreischer Tripel a < b < Grenze kann ausgehend von dem Basistripel 3-4-5 über bestimmte Zahlenfolgen gefunden werden. Die drei Folgen

markieren

Quelltext

1:
2:
3:

Folge A  a2 = 2·(c1-b1)+a1 ; b2 = 2·(c1+a1)-b1 ; c2 = 2·(a1-b1)+3·c1
Folge S  a2 = 2·(c1+a1)+b1 ; b2 = 2·(c1+b1)+a1 ; c2 = 2·(a1+b1)+3·c1
Folge D  a2 = 2·(c1-a1)+b1 ; b2 = 2·(c1+b1)-a1 ; c2 = 2·(b1-a1)+3·c1

müssen sich gegenseitig rekursiv aufrufen.

Mit meinem Text

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:

procedure TForm1.Button1Click(Sender: TObject);
var a,b,c,a2,b2,c2,anzahl,grenze:int64;

procedure folges(a,b,c:int64); forward;
procedure folged(a,b,c:int64); forward;

procedure folgea(a,b,c:int64);
begin
    a2:=2*(c-b)+a;
    b2:=2*(c+a)-b;
    c2:=2*(a-b)+3*c;
    a:=a2;
    b:=b2;
    c:=c2;
    if b<=grenze then
    begin
      inc(anzahl);
      folgea(a,b,c);
      folges(a,b,c);
      folged(a,b,c);
    end;
end;
procedure folges(a,b,c:int64);
begin
    a2:=2*(c+a)+b;
    b2:=2*(c+b)+a;
    c2:=2*(a+b)+3*c;
    a:=a2;
    b:=b2;
    c:=c2;
    if b<=grenze then
    begin
      inc(anzahl);
      folgea(a,b,c);
      folges(a,b,c);
      folged(a,b,c);
    end;
end;
procedure folged(a,b,c:int64);
begin
    a2:=2*(c-a)+b;
    b2:=2*(c+b)-a;
    c2:=2*(b-a)+3*c;
    a:=a2;
    b:=b2;
    c:=c2;
    if b<=grenze then
    begin
      inc(anzahl);
      folgea(a,b,c);
      folges(a,b,c);
      folged(a,b,c);
    end;
end;
begin
     grenze:=10;
   repeat
     anzahl:=1;
     a:=3; b:=4; c:=5;
     folgea(a,b,c);
     a:=3; b:=4; c:=5;
     folges(a,b,c);
     a:=3; b:=4; c:=5;
     folged(a,b,c);
     listbox1.items.add(format('%d'#9'%d',[grenze,anzahl]));
     if grenze>=1e8 then grenze:=grenze+100000000
                    else grenze:=grenze*10;
     application.processmessages;
   until (grenze>1e9);
end;

kann die Anzahl damit relativ schnell berechnet werden. Für einen Vergleich mit der Tabelle müssen die Werte verdoppelt werden, da hier nur a < b berechnet wird.
Den exakten mathematischen Beweis, dass damit alle Tripel gefunden werden, kenne ich leider nicht.
Ich gehe davon aus, das Ihr noch eine Beschleunigung der Routine erreicht. Ärgerlich ist auch, dass ich bei 1,8 Milliarden einen Stack-Überlauf bekomme.

Zusätzliche Ergebniss:
1,2 Milliarden ... 428648736 Tripel a,b < n
1,4 Milliarden ... 500090034
1,6 Milliarden ... 571531802
1,8 Milliarden ... Stacküberlauf

Gausi hat folgendes geschrieben :

/OT Dieser Thread ist toll. Eine recht einfache Frage, ein paar einfache Lösungsansätze, und dann kommen ein paar Nerds(*) an und kapern den Thread. :lol:

Ich finde das auch toll. Es müssen nicht extrem schwere Paranüsse oder Adventsrätsel sein :wink:

, die ich leider nicht lösen kann :oops:

.
Die scheinbar einfachen Fragen sind diejenigen, die faszinieren und viele Möglichkeiten geben, weitergehende Untersuchungen anzustellen. Das ist Mathematik! Und deshalb liebe ich sie so. Ich bin eben ein Nerd!

Beste Grüße
Mathematiker

Nachtrag: Nach Vergrößerung des Stacks bekomme ich
1,8 Milliarden ... 642973124
2,0 Milliarden ... 714414498
2,5 Milliarden ... 893018212
3,0 Milliarden ... 1071622030
3,5 Milliarden ... 1250225390
4,0 Milliarden ... 1428828886
5,0 Milliarden ... 1786036162
6,0 Milliarden ... 2143243604 , mein Computer zeigt deutlich Geschwindigkeitsprobleme
7,0 Milliarden ... 2500450678
8,0 Milliarden ... 2857658176
9,0 Milliarden ... 3214865160
Mal sehen, wie weit ich es treiben kann. :lol:

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Horst_H · Verfasst: Di 04.12.12 20:29

Hallo,

die Stackprobleme kann ich nicht verstehen?
Es sind doch pro Rekursionsschritt nur 24 Byte ( 3*Int64) mehr auf dem Stack

markieren

Quelltext

1:
2:
3:
4:
5:
6:

maximale
Rekursionstiefe      Bis           Anzahl phyth Tripel
      2234          10000000         3572022
      ... //                               Bis = 100-fach -> sqrt(100) = 10 fach Rekursionstiefe
     22359        1000000000       357207278
     44719        4000000000      1428828886

Bei 4e9 maximal 1,073 Mb
<Edit>
Bis 4e9 braucht es bei mir nur 12,6 Sekunden.
Man könnte aber gut 3 CPU benutzen in der Rekursion

markieren

Quelltext

1:
2:

 44719  4000000000      1428828886
00:00.12.634

</edit>

<Edit2<
Die Rekursionstiefe lässt sich ja vorab berechnen und beträgt

markieren

Delphi-Quelltext

1:	MaxRekTiefe = sqrt(MAXGrenze div 2)

in folgeX steht ja a = 2* ,b= 2* c=2* )
<Edit2>

Die Geschwindigkeitsprobleme beruhen ja auf der vollständige Neuberechnung, da man die vorherige Rechnung nicht ausnutzen kann.
Oder kann man das doch?
Könnte man die Zahlen die bei Rekursionabbruch auftreten eventuell in 3 Listen für Folge a,s,d speichern und ab dort dann mit neuer Grenze weitermachen?

Gruß Horst
//Übrigens kann man hier schlecht einloggen, wenn man statt &password=.... &passwoard=. "post"et um an eine sid zu kommen. Haare rauf.

Mathematiker · Verfasst: Di 04.12.12 21:41

Hallo Horst_H,

Horst_H hat folgendes geschrieben :

die Stackprobleme kann ich nicht verstehen?

Ich auch nicht, aber bei meiner überarbeiteten Version kommt der Überlauf schon bei 1 Milliarde.

Horst_H hat folgendes geschrieben :

Bis 4e9 braucht es bei mir nur 12,6 Sekunden.

Und das verstehe ich schon gar nicht. Bis 1e9 benötigt mein Computer über 45 Sekunden, trotz der schnelleren Variante:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:

procedure TForm1.Button1Click(Sender: TObject);
var a,b,c,anzahl,grenze:int64;

procedure folges(a,b,c:int64); forward;
procedure folged(a,b,c:int64); forward;

procedure folgea(a,b,c:int64);
var a2,b2,c2:int64;
begin
    b2:=2*(c+a)-b;
    if b2<=grenze then
    begin
      a2:=2*(c-b)+a;
      c2:=2*(a-b)+3*c;
      inc(anzahl);
      folgea(a2,b2,c2);
      folges(a2,b2,c2);
      folged(a2,b2,c2);
    end;
end;
procedure folges(a,b,c:int64);
var a2,b2,c2:int64;
begin
    b2:=2*(c+b)+a;
    if b2<=grenze then
    begin
      a2:=2*(c+a)+b;
      c2:=2*(a+b)+3*c;
      inc(anzahl);
      folgea(a2,b2,c2);
      folges(a2,b2,c2);
      folged(a2,b2,c2);
    end;
end;
procedure folged(a,b,c:int64);
var a2,b2,c2:int64;
begin
    b2:=2*(c+b)-a;
    if b2<=grenze then
    begin
      a2:=2*(c-a)+b;
      c2:=2*(b-a)+3*c;
      inc(anzahl);
      folgea(a2,b2,c2);
      folges(a2,b2,c2);
      folged(a2,b2,c2);
    end;
end;
var zeit:integer;
begin
     zeit:=gettickcount;
     grenze:=1000000000;
     anzahl:=1;
     a:=3; b:=4; c:=5;
     folgea(a,b,c);
     a:=3; b:=4; c:=5;
     folges(a,b,c);
     a:=3; b:=4; c:=5;
     folged(a,b,c);
     listbox1.items.add(format('%d'#9'%d',[grenze,2*anzahl]));
     label1.caption:=inttostr(gettickcount-zeit)+' ms';
end;

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Horst_H · Verfasst: Di 04.12.12 22:19

Hallo,

ich nutze gerade Linux 64-Bit und da geht die Rechnerei mit 64 Bit schneller.
Meine verzeigerte Variante ist langsamer geworden :-(

markieren

Quelltext

1:
2:

4000000000      1428828886
00:00.15.937

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:

{$IFDEF FPC}
  {$MODE Delphi}
  {$OPTIMIZATION ON}
  {$OPTIMIZATION Regvar}
  {$OPTIMIZATION Peephole}
  {$OPTIMIZATION cse}
  {$OPTIMIZATION asmcse}
{$else}
  {$Apptype Console}
{$ENDIF}
uses
  sysutils;
const
  max = 200000;
var
  T1,T0: TDateTime;
type
   tTripel =  record
                a,b,c : Int64;
              end;
   ptTripel = ^tTripel;           
const
  MaxGrenze = 4*1000*1000*1000;
  Maxtiefe =  round(sqrt(MAXGrenze div 2))+1;
var
  MeinStack : array[0..Maxtiefe+1] of tTripel;
  p0,p1 : ptTripel;
  anzahl,grenze:int64;

procedure folgea; forward;
procedure folges; forward;
procedure folged; forward;

procedure check;
begin
  inc(anzahl);
  // eins tiefer
  p0 := p1; inc(p1);    
  folgea;
  folges;
  folged;
  //wieder eins hoeher
  p1 := p0; dec(p0);
end;

procedure folgea;
begin
    with p0^ do
      begin
      p1^.a :=2*(c-b)+a;
      p1^.b :=2*(c+a)-b;
      p1^.c :=2*(a-b)+3*c;
      end;
    if p1^.b<= grenze then
     check;
end;
procedure folges;
begin
  with p0^ do
    begin
    p1^.a :=2*(c+a)+b;
    p1^.b :=2*(c+b)+a;
    p1^.c :=2*(a+b)+3*c;
    end;
    if p1^.b<= grenze then
     check;
end;

procedure folged;
begin
    with p0^ do
      begin
      p1^.a :=2*(c-a)+b;
      p1^.b :=2*(c+b)-a;
      p1^.c :=2*(b-a)+3*c;
      end;
    if p1^.b<= grenze then
     check;
end;

procedure CountPhyth;
begin
   grenze:= MaxGrenze;
   repeat
     anzahl:=1;
     p0 := @MeinStack[0];
     with p0^ do
       begin
       a:=3; b:=4; c:=5;
       end;
     p1 := p0;
     inc(p1);
      
     folgea;
     folges;
     folged;
     
     writeln(format('%d'#9'%d',[grenze,2*anzahl]));
     if grenze>=1e8 then grenze:=grenze+100000000
                    else grenze:=grenze*10;
   until (grenze>MaxGrenze);
end;
begin
  T0 := now;
  CountPhyth;
  T1 := now;
  writeln(FormatDateTime('HH:NN.SS.ZZZ',T1-T0));
end.
n       P(n)
        10         2
        50        16
       100        36
       500       180
      1000       358
      5000      1780
     10000      3576
     50000     17856
    100000     35722
    500000    178600
   1000000    357200
   5000000   1786016
  10000000   3572022
  50000000  17860382
 100000000  35720710
 500000000 178603536
1000000000 357207278

Diese Compilerschalter sind wohl unwirksam:
Beispielhaft der Auszug des Assemblers von folgea:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:

P$PROGRAM_FOLGEA:
.Lc4:
# Temps allocated between rsp+0 and rsp+0
# [47] begin
  subq  $8,%rsp  // Wozu das? dass muss einen besonderen Grund haben, vielleicht eine Adreese, die bei Absturz aufgerufen wird
.Lc6:
# [48] with p0^ do
  movq  U_P$PROGRAM_P0,%rax  // Zeiger p0 ist in rax und bleibt auch da
# [50] p1^.a :=2*(c-b)+a;
  movq  U_P$PROGRAM_P1,%rsi  // Zeiger p1 ist jetzt in rsi
  movq  16(%rax),%rdx
  movq  8(%rax),%rcx
  subq  %rcx,%rdx
  shlq  $1,%rdx
  movq  (%rax),%rcx
  addq  %rcx,%rdx
  movq  %rdx,(%rsi)
# [51] p1^.b :=2*(c+a)-b;
  movq  U_P$PROGRAM_P1,%rsi // Der Zeiger war schon in RSI ?????????
  movq  16(%rax),%rdx
  movq  (%rax),%rcx
  addq  %rcx,%rdx
  shlq  $1,%rdx
  movq  8(%rax),%rcx
  subq  %rcx,%rdx
  movq  %rdx,8(%rsi)
# [52] p1^.c :=2*(a-b)+3*c;
  movq  U_P$PROGRAM_P1,%rsi // Der Zeiger war schon in RSI ?????????
  movq  (%rax),%rdx
  movq  8(%rax),%rcx
  subq  %rcx,%rdx
  shlq  $1,%rdx
  movq  16(%rax),%rax
  imulq  $3,%rax
  addq  %rax,%rdx
  movq  %rdx,16(%rsi)
# [54] if p1^.b> grenze then
  movq  U_P$PROGRAM_P1,%rax   //???? rsi hat immer noch die richtige Adresse 
  movq  8(%rax),%rax
  cmpq  U_P$PROGRAM_GRENZE,%rax
  jg  .Lj9
# [56] check;
  call  P$PROGRAM_CHECK
.Lj9:
# [57] end;
  addq  $8,%rsp  
  ret

Gruß Horst

Anika · Beiträge: 30 Erhaltene Danke: 2 Windows 7 Delphi 7

Guten Tag.
Von den letzten Sachen verstehe ich nichts mehr.
Ich habe jetzt nur noch eine Berechnung des größten gemeinsamen Teilers und höre auf, wenn c zu groß wird.
Das Programm ist jetzt super schnell. Mein Lehrer wird staunen.
Nochmals vielen dank.

Anika

Nersgatt · Verfasst: Mi 05.12.12 16:02

Anika hat folgendes geschrieben :

Das Programm ist jetzt super schnell. Mein Lehrer wird staunen.

Noch mehr staunen wird er, wenn Du auch noch erklären kannst, warum Deine Lösung vielleicht schneller ist, als die Deiner Klassenkameraden. Das ist meiner Meinung noch wichtiger, als eine schnelle Lösung zu haben.

_________________
Gruß, Jens
Zuerst ignorieren sie dich, dann lachen sie über dich, dann bekämpfen sie dich und dann gewinnst du. (Mahatma Gandhi)

Mathematiker · Verfasst: Mi 05.12.12 17:56

Hallo,
ich habe versucht für höhere Grenzen die Anzahl der Tripel zu berechnen. Zumindest für 10 Milliarden erhielt ich 3572072820.
Mein Versuch, bis 100 Milliarden zu bekommen, schlug fehl.
Bei meinem Programm müsste ich den Stack größer machen, als es mein PC+Delphi 5 zulässt. Mit dem Programm von Horst_H geht es auch nicht, da die Datenmenge zu groß wird.

Irgendwie muss eine neue Idee her.

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Horst_H · Verfasst: Mi 05.12.12 21:33

Hallo,

das versteh ich ja nun gar nicht.
Die Maximale Tiefe = sqrt(Maxgrenze div 2)+1 , bei 1e11 sind das nur 223608*24Byte = 5'366'592 Byte.
Das ist doch ein Klacks.Theretisch dauert es bei mir 345 Sekunden, müßte also gleich fertig sein.
Mein Programm hat insgesamt 12 MB reserviert, der Opera-Browser suhlt sich in über 100 Mb.
Die Laufzeit habe ich linear aus 3,47 Sekunden für 1e9 geschätzt und 345,7 Sekunden ist nur knapp daneben.

markieren

Quelltext

1:
2:
3:
4:
5:

Maxtiefe :   223608
Stackgroesze 5366592
100000000000    35720725882
 10000000000     3572072820 // Zum Vergleich 1e9 eingefügt
00:05.45.730

Ich habe den Code minimal modifiziert, indem statt zweier Zeiger als globale Variblen, die scheinbar nicht freiwillig im Register gehalten werden, nun nur einen p0 nutze, welchen ich innerhalb von folge? durch zwei lokale und damit Registervariablen ersetze.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

procedure check;
begin
  inc(anzahl);
  // eins tiefer
  inc(p0);
  folgea;
  folges;
  folged;
  //wieder eins hoeher
  dec(p0);
end;

procedure folgea;
var
  p,p1 :ptTripel;
begin
  p1 := p0;
  p:= p1;
  inc(p);
  with p1^ do
    begin
    p^.a :=2*(c-b)+a;
    p^.b :=2*(c+a)-b;
    p^.c :=2*(a-b)+3*c;
    end;
  if p^.b<= grenze then
   check;
end;

Auf dem Stack ist natürlich noch immer viel Verkehr, denn alle Rücksprungadressen und geretteten Register werden ja auch bis zu Maxtiefe auf den Stack zwischen gelagert.

Bis 1e12 also unter einer Stunde.Man kann aber einen Faktor 3 rausholen durch Nutzung dreier CPU-kerne und dreier Stacks.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

     anzahl:=1;
     p00 := @MeinStack0[0];
     with p00^ do
       begin
       a:=3; b:=4; c:=5;
       end;
     p01 := @MeinStack1[0];
     with p01^ do
       begin
       a:=3; b:=4; c:=5;
       end;
     p02 := @MeinStack2[0];
     with p02^ do
       begin
       a:=3; b:=4; c:=5;
       end;
StarteTread0 mit folgea;
StarteTread1 mit folges;
StarteTread2 mit folged;

Die ersten 7 Stellen der Anzahl der phyth. Tripel von 1e10 und 1e11 stimmen überein, das sehe ich nun wirklich keinen Erkenntnisgewinn, den Zahlenbereich immer höher zu schrauben.

Gruß Horst

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme