Autor |
Beitrag |
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Di 04.12.12 13: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
|
Verfasst: Di 04.12.12 13:31
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!
Für diesen Beitrag haben gedankt: Anika, Horst_H
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 04.12.12 15:00
Hallo,
so scheint es auch bis 100000 ( NativeInt ist bei mir 64-Bittig, deshalb kein Überlauf bei Summe der Quadrate ) zu sein:
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; 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. |
Was auffällig ist: Die Anzahl steigt linear.
Etwa 395 bei 2500.
Gruß Horst
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Di 04.12.12 15:51
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
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Di 04.12.12 15: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.
Fast so schön wie eine Diskussion zum Sortieren, die in "wie optimiere ich Bubblesort durch Assembler" ausartet.
Weitermachen.
(*) 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
Beiträge: 4705
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Di 04.12.12 16: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
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 04.12.12 16: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
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
|
Verfasst: Di 04.12.12 16:56
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
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 04.12.12 17: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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Di 04.12.12 20: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
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
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. |
Ich finde das auch toll. Es müssen nicht extrem schwere Paranüsse oder Adventsrätsel sein , die ich leider nicht lösen kann .
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.
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Zuletzt bearbeitet von Mathematiker am Di 04.12.12 21:32, insgesamt 1-mal bearbeitet
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 04.12.12 21:29
Hallo,
die Stackprobleme kann ich nicht verstehen?
Es sind doch pro Rekursionsschritt nur 24 Byte ( 3*Int64) mehr auf dem Stack
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
Quelltext 1: 2:
| 44719 4000000000 1428828886 00:00.12.634 | </edit>
<Edit2<
Die Rekursionstiefe lässt sich ja vorab berechnen und beträgt
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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Di 04.12.12 22: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:
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
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 04.12.12 23:19
Hallo,
ich nutze gerade Linux 64-Bit und da geht die Rechnerei mit 64 Bit schneller.
Meine verzeigerte Variante ist langsamer geworden
Quelltext 1: 2:
| 4000000000 1428828886 00:00.15.937 |
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); p0 := p1; inc(p1); folgea; folges; folged; 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:
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
|
Verfasst: Mi 05.12.12 11:59
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
Beiträge: 1581
Erhaltene Danke: 279
Delphi 10 Seattle Prof.
|
Verfasst: Mi 05.12.12 17:02
_________________ Gruß, Jens
Zuerst ignorieren sie dich, dann lachen sie über dich, dann bekämpfen sie dich und dann gewinnst du. (Mahatma Gandhi)
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mi 05.12.12 18: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
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mi 05.12.12 22: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.
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.
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); inc(p0); folgea; folges; folged; 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.
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
Für diesen Beitrag haben gedankt: Mathematiker
|
|
|