Autor |
Beitrag |
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mi 04.07.12 20:21
Hallo,
eine interessante mathematische Fragestellung ist der 196-Algorithmus:
Gegeben ist eine zwei- oder mehrstellige natürliche Zahl n.
Zu dieser Zahl wird die natürliche Zahl addiert, welche dadurch entsteht, dass die Ziffernfolge von n umgekehrt wird. Diese Addition wird mit der Summe immer wiederholt, bis eine Palindrom-Zahl entsteht, z.B. n = 5280 mit den Gliedern 6105, 11121, 23232.
Die entstehende Zahl kann teilweise sehr groß werden, z.B. für 89 ergibt sich 8813200023188.
Die kleinsten Zahlen, für welche nicht bekannt ist, ob der Algorithmus irgendwann eine Palindrom-Zahl liefert, sind: 196, 887, 1675, 7436, 13783, …
Bis heute weiß niemand, ob im Dezimalsystem immer ein Palindrom entsteht. Im Dualsystem ist es sicher, dass nicht jede Zahl schließlich zu einem Palindrom führt. 10110 wird dort niemals palindromisch.
Mein kleines Programm sucht nach der Eingabe der Startzahl das Palindrom.
Das Problem ist nun, dass z.B. für n = 196 schnell die Schwierigkeit auftritt, die Zahl umzukehren und außerdem effizient im Speicher zu halten, da die Ziffernzahl scheinbar über alle Grenzen wächst.
Mir ist klar, dass mit einem einfachen Delphi-Programm das Palindrom der 196 nicht gefunden werden kann, da 2005 Wade van Landingham die Suche nach 284 Millionen Iterationen abbrechen musste, da das Folgenglied mehrere Millionen Ziffern hatte.
Meine Frage ist nun, ob jemand eine gute Idee hat, wenigstens bis zu 100000 Ziffern Länge in vertretbarer Zeit zu kommen.
Mein Algorithmus ist dafür ungeeignet. Ich verwandle die Zahl in einen String, drehe diesen Zeichen für Zeichen und transformiere diesen zurück, d.h. doppelte Speicherbelastung (Zahl und String) und langwierige String-Operationen.
Beste Grüße
Mathematiker
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Mi 04.07.12 20:34
Hey, wie viele Probleme willst du hier eigentlich noch vorstellen? Wir brauchen ja bald eine Mathe-Sparte (nicht dass das schlecht wäre)
Ich hab da eine Idee - eigentlich braucht man ja nur Addition und Reverse, das braucht kein FGInt.
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mi 04.07.12 21:17
Hallo Martok,
Martok hat folgendes geschrieben : | Ich hab da eine Idee - eigentlich braucht man ja nur Addition und Reverse, das braucht kein FGInt. |
Das bringt mich auf die Idee, String und FGInt fallen zu lassen und es einmal mit einem array of byte für die Ziffern zu versuchen. Die Addition dürfte dann relativ schnell gehen, natürlich mit dem Übertrag.
Ich werde es ausprobieren.
Martok hat folgendes geschrieben : | Hey, wie viele Probleme willst du hier eigentlich noch vorstellen? Wir brauchen ja bald eine Mathe-Sparte (nicht dass das schlecht wäre) |
Ich weiß, dass das hier ein Delphi(!)-Forum und kein Mathe-Forum ist. Leider gibt es ein Mathe-Forum, dass sich mit der programmtechnischen Umsetzung von Matheproblemen (die ich verstehe) beschäftigt, leider nicht. Ich werde mit etwas zurückhalten.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Mi 04.07.12 21:24
Mathematiker hat folgendes geschrieben : | Ich weiß, dass das hier ein Delphi(!)-Forum und kein Mathe-Forum ist. Leider gibt es ein Mathe-Forum, dass sich mit der programmtechnischen Umsetzung von Matheproblemen (die ich verstehe) beschäftigt, leider nicht. Ich werde mit etwas zurückhalten. |
Bloß nicht, ich finde das interessant
Solange uns das nicht die nächsten 100 Jahre Weihnachtsrätsel "verbrennt"...
Was hältst du davon? Ich hab gleich mal die GUI eingespart, die ersten 100k Iterationen (irgendwas um 43k Stellen, das scrollt so schnell vorbei ) dauern etwas weniger als 60 Sekunden.
Einloggen, um Attachments anzusehen!
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
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 04.07.12 21:53
Martok hat folgendes geschrieben : | Was hältst du davon? Ich hab gleich mal die GUI eingespart, die ersten 100k Iterationen (irgendwas um 43k Stellen, das scrollt so schnell vorbei ) dauern etwas weniger als 60 Sekunden. |
Die Geschwindigkeit ist geradezu unglaublich. So habe ich mir das vorgestellt. Allerdings werde ich etwas brauchen, um Deinen Text zu verstehen.
Ich schäme mich fast, meine zweite Variante zu veröffentlichen, bei der ich auch Arrays nutze. Es ist viel langsamer als Dein Programm.
Beste Grüße
Mathematiker
Nachtrag: Ich habe mir ersteinmal FastMM4 besorgt, kannte ich natürlich nicht.
Beim Übersetzen Deines Textes fand mein Delphi
DivMod(Sum, NUMBER_BASE, Carry, Dig);
nicht. Kann das sein, dass in den aktuellen Delphi-Versionen die math-unit diesen Befehl enthält? Bei meinem steinzeitlichen Delphi5 gibt's denn nicht.
Nachtrag 2: Eine verbesserte Variante siehe weiter unten.
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Zuletzt bearbeitet von Mathematiker am Do 05.07.12 14:00, insgesamt 2-mal bearbeitet
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Mi 04.07.12 22:38
Ich behaupte mal, as einzige was bei dir ernsthaft bremst ist die GUI-Aktualisierung über Application.ProcessMessages. Wie du siehst, ist mir sogar die Windows-Console zu langsam um das jeden Durchgang zu machen, deswegen das runterteilen auf jeden 100sten Durchlauf
Mathematiker hat folgendes geschrieben : | Nachtrag: Ich habe mir ersteinmal FastMM4 besorgt, kannte ich natürlich nicht. |
In neueren Delphis ist der sogar fest eingebaut. Bringt einiges, wenn man oft realloziieren muss (was SetLength ja tut).
Mathematiker hat folgendes geschrieben : | Beim Übersetzen Deines Textes fand mein Delphi
DivMod(Sum, NUMBER_BASE, Carry, Dig);
nicht. |
Ich bin der Meinung die gibts schon länger, aber ich bin mir nicht sicher ob vielleicht in einer anderen Unit. Das Ding macht eigentlich nur Div und Mod in einem Durchgang und ist dabei angeblich schneller (ich kann mich an Messungen erinnern, die das relativiert haben), also:
Delphi-Quelltext 1: 2:
| Carry:= Sum div NUMBER_BASE; Dig:= Sum mod NUMBER_BASE; |
EDIT:
ich lass das mal aus Spaß laufen:
Quelltext 1:
| 1826000 it 756082 dig 20260.0 s |
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 05.07.12 10:10
Hallo,
hier wird doch nur addiert, da kann Carry nur 0 oder 1 sein.
Dadurch fällt auch die Variable Dig weg.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| for p:= 0 to high(Summand) do begin Sum:= Carry + Number[p] + Summand[p]; Carry := 0; IF SUM >= NUMBER_BASE then begin dec(sum,NUMBER_BASE); Carry := 1; end; Number[p]:= Sum; end; |
Das macht einiges aus, ich habe mal die Zahl vor den Zahlenangeban und Zeiten ausgegeben
Startzahl ist 196 und wie man sieht: Die Zahlen ähneln sich
Original
Quelltext 1: 2: 3: 4: 5:
| 60112339269111851140389301806586681291351507449752782263142146284398312681631144 80513403906695460975689940797209307853656534423943491142030348495051500816735422 60147073619478325530666484993268957414968737533136622157990802952584506637311513
241389 it 100000 dig 269.473066 s |
Fälschung, erstatz von divMod
Quelltext 1: 2: 3: 4: 5:
| 60112339269111851140389301806586681291351507449752782263142146284398312681631144 80513403906695460975689940797209307853656534423943491142030348495051500816735422 60147073619478325530666484993268957414968737533136622157990802952584506637311513
241389 it 100000 dig 167.871914 s |
Es bringt sicher etwas.
Verbirgt sich hinter 241389/100000 eine neue mathematische Konstante
Ich habe dummerweis 887 getestet, ach herrje, das ist doch 196+691 und braucht 241389-1 Itertionen für 100000 Stellen, vergeudete Abwärme...
Das setlength kann mann sicher reduzieren, durch indem man sich selbst die belegten Längen merkt und direkt 1 MB oder so belegt.
Ob sich das reversieren des Feldes lohnt wäre noch interessant. wenn meist schon nach drei Vergleichen feststeht es ist kein Palindrom könnte man mit einem Feld für die Zahl/Summe und und einem zusätzlichem halb so langem arbeiten.
Oberes Feld Zahl , unteres Feld Kopie der unteren Hälfte
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| Zahl/Sum 123456 Kopie 123 ich summiere dann in die Zahl Zahl[1]=Zahl[1]+Zahl[6] Zahl[2]=Zahl[2]+Zahl[5] Zahl[3]=Zahl[3]+Zahl[4] jetzt bei der Hälfte Zahl[4]=Zahl[4]+Kopie[3] Zahl[5]=Zahl[5]+Kopie[2] Zahl[6]=Zahl[6]+Kopie[1] |
Man sieht die Nummerierung läuft einfach weiter.
Bei ungerader Zahllänge addiert man ja die mittlere Zahl auf sich selbst, dürfte also ohne Knoten im Hirn funktionieren.
Gruß Horst
Edit:
Ich habe mal die maximalen Vergleiche bis zur Erkennung eines Unterschiedes und bei welcher Iteration sie auftraten gestoppt: Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:
| Startzahl: 196 Iteration maximale Anzahl der Vergleiche auf Palindrom 1 1 6 2 13 3 16 4 25 5 70 8 105 12 1237 13 1430 14 3461 16 3940 17 9777 29 429911 31 = 483101 it 200000 dig 1.00391500000000E+003 s |
Das Notebook ist doch wesentlich langsamer.
Ich hatte gehofft, der Ersatz der Addition und Kontrolle auf Carry durch den Einsatz einer Konstanten SumCarFeld beschleunigen zu können, hätte mehr gebracht.
Vielleicht liegt es an Freepascal und dessen Umgang mit dynaischen Feldern.
Ich habe auf dem Notebook nur Linux also habe ich nur Time aus sysutils genutzt, das hat eine Auflösung von 1 ms, das reicht mir allemal.
Sodele, schnell mal NumberAdd auf Pointerarithmetik umgestellt und die Befehle merkwürdig angeordnet( inc(pb1) read modify write möglichst zeitlich weit bis zum nächsten Zugriff )
Das spart etwa 50 %
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: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171:
| program p196; {$IFDEF FPC} {$MODE DELPHI} {$Optimization ON} {$Optimization RegVar} {$Optimization PEEPHOLE} {$Optimization CSE} {$Optimization ASMCSE} {$Endif}
uses SysUtils;
const NUMBER_BASE = 10; type TDigit = Byte; TSumCar = record s,c : byte; end; TSumCarFeld = array[0..19] of TsumCar; TNumber = array of TDigit; const SumCarFeld : TSumCarFeld =((s:0;c:0),(s:1;c:0),(s:2;c:0),(s:3;c:0),(s:4;c:0), (s:5;c:0),(s:6;c:0),(s:7;c:0),(s:8;c:0),(s:9;c:0), (s:0;c:1),(s:1;c:1),(s:2;c:1),(s:3;c:1),(s:4;c:1), (s:5;c:1),(s:6;c:1),(s:7;c:1),(s:8;c:1),(s:9;c:1)); var MaxIndex : integer; Cycle: Cardinal; procedure NumberFromString(var Number: TNumber; Str: string); var i: integer; begin SetLength(Number, Length(Str)); for i:= 0 to Length(Str) - 1 do Number[i]:= Ord(Str[Length(Str) - i]) - Ord('0'); end;
function NumberToString(var Number: TNumber): string; var i: integer; begin SetLength(Result, Length(Number)); for i:= 0 to High(Number) do Result[Length(Result) - i]:= Chr(Ord('0') + Number[i]); end;
procedure NumberAdd(var Number, Summand: TNumber); var pb1,pB2 : pByte; p: integer; Carry: integer; begin Carry:= 0; pb1 := @Number[0]; pb2 := @Summand[0]; for p:= high(Summand) downto 0 do begin With SumCarFeld[Carry + pb1^ + pb2^] do begin inc(pb2); pb1^ := s; inc(pb1); Carry := c; end; end; IF Carry = 1 then begin p := Length(Summand)+1; setlength(Summand, p); SetLength(Number, p); Number[p-1] :=1; end; end;
procedure NumberReverse(var Reversed, Number: TNumber); var i: integer; begin SetLength(Reversed, Length(Number)); for i:= 0 to high(Number) do Reversed[high(Reversed) - i]:= Number[i]; end;
function NumberCompare(var A, B: TNumber): boolean; begin Result:= (high(A) = high(B)) and CompareMem(@A[0], @B[0], Length(A)); end;
function NumberCompareB(var A: TNumber): boolean; var i,j: integer; begin i := Low(A); j := High(A); repeat Result:= A[i]=A[j]; inc(i); dec(j); until Not(Result) OR (J<I); IF MaxIndex <i then begin MaxIndex := i; writeln(cycle:10,i:4) end; end;
var Work, Rev: TNumber;
Time1, Time2 : TDateTime; s: string; begin repeat Write('Startzahl: '); ReadLn(s); if s='' then break; NumberFromString(Work, s); Cycle:= 0; Time1 := time; NumberReverse(Rev, Work); repeat NumberAdd(Work, Rev); NumberReverse(Rev, Work); inc(Cycle); if Cycle AND cardinal(-1) = 0 then begin Time2 := time; WriteLn(Cycle:10,' it',Length(Work):10,' dig',(Time2-Time1)*86400.0:14:1,' s'); end; until NumberCompareB(REv) OR (Length(Work)>99999); Time2 := time; WriteLn('='); WriteLn(NumberToString(Work)); WriteLn(Cycle:10,' it',Length(Work):10,' dig',(Time2-Time1)*86400.0,' s');
WriteLn; WriteLn; WriteLn; until false; end. |
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Do 05.07.12 13:33
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: Do 05.07.12 13:59
Gammatester hat folgendes geschrieben : | Was bei p196b sehr bremst, ist das völlig überflüssige Zusammenbasteln der Anzeige, auch dann wenn gar nichts angezeigt werden soll. |
Gerade, als ich meine neue Variante senden wollte, kam Deine Nachricht. Genau das(!) bremst ungemein.
Außerdem habe ich auch div und mod "rausgeworfen". Da die Summe zweier Ziffern nicht größer als 19 wird, genügt die Subtraktion mit 10 und das Inkrementieren der nächsten Ziffer.
Auf meinem Rechner brauche ich nun für 100000 Ziffern Länge nur noch 207 Sekunden.
Beste Grüße
Mathematiker
Nachtrag: Statt e[i]:=e[i]-10 nun dec(e[i],10) bringt noch einmal 4 Sekunden. Nicht viel, aber ein Anfang.
^Horst_H: Pointerarithmetik muss ich erst einmal verstehen.
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Do 05.07.12 16:00
Ich hab gestern auch noch etwas gebastelt und auch nochmal gut 10% rausgeholt, aber grade, als ich das hochladen wollte, das gesehen.
100k Iterationen in 5-10 Sekunden, irgendwas machen wir prinzipiell falsch.
Das Compare ist nicht das teuere: MemCmp bricht bei Ungleicheheit sowieso ab, d.h. nur ein Palindrom wird überhaupt in die 2. Hälfte kommen. Und dass da bis 413mio Iterationen keins kommt wissen wir schon Und da die Reverse eh vorhanden ist, kann man auch gleich das nehmen: mit FastMM vergleicht der in Machine Word Schritten.
Horst_H: ist eine Tabelle da echt schneller als Add/Cmp/Sub? Guck an.
Wenn wir eh Pointer nehmen, kann auch das dynamische Array raus.
Ich häng mal den Stand von gestern Abend an; mittlerweile ganz ohne Carry, und nur noch Inc/Dec/Cmp in einer Schleife.
Ca 51s für 100k Iterationen.
Einloggen, um Attachments anzusehen!
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
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: Do 05.07.12 17:03
Martok hat folgendes geschrieben : | Ich häng mal den Stand von gestern Abend an; mittlerweile ganz ohne Carry, und nur noch Inc/Dec/Cmp in einer Schleife.Ca 51s für 100k Iterationen. |
Sehr schön, das ist das Schnellste bisher.
Martok hat folgendes geschrieben : | 100k Iterationen in 5-10 Sekunden, irgendwas machen wir prinzipiell falsch. |
Du hast recht, aber was ist prinzipiell falsch. Scheinbar gibt es eine völlig andere Grundidee zur Bestimmung der Folgenglieder. Aber welche? Irgendwie rätselhaft.
Da ich von C# keinerlei Ahnung habe, meine Frage: Würde Dein Programm mit C# eigentlich deutlich schneller laufen?
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: Do 05.07.12 17:38
Hallo,
@Martok:
Die Interseite lässt die Hoffnung schwinden oder sind es die 27 Grad im Zimmer
Eine kleine Anmerkung. Dein Programm berechnet 100000 Durchgänge und ich habe oben 100000 Stellen gerechnet, also 241xxx Durchgänge.
Delphi-Quelltext 1: 2: 3: 4:
| if Cycle >= 100000 then break; statt until NumberCompareB(REv)or (Length(Work)>99999); |
Bitte erst die Zahl ausgeben und dann die Zeiten, ich habe sie nicht mehr im Fenster.
Eine Kompilierung mit Freepascal 2.6.0 kam auf 22 Sekunden, meine Version auf 16 Sekunden, obwohl CompareMem etwas schneller wäre, aber es ist mehr eine Findungsphese, wie man das implementieren könnte
Ich bastel an der Version ohne ReverseFeld und einem Kopiefeld von halber Größe, wie oben beschrieben.
Vielleicht kann man zwei BCD_Ziffern in einem Byte verarbeiten, Ein SumCarFeld hätte auch nur 199 Einträge, aber dann muss man sehr oft die obere Hälfte um 4 Bit schieben.
@Mathematiker: bin immer noch schneller, aber weit weit weg vom Optimum,
Diese p196 Laufzeiten sondern einen mehr erstaunen.
Die Laufzeit wächst ja theoretisch quadratisch mit der Ziffernzahl.
Ich brauch 95 Sekunden für 100000 Stellen = 241??? Durchläufe, Hochgerechnet sind das 606 Sekunden also 10 min 6 Sekunden.
Aber wir kennen den Rechner der Internetseite nicht.
51 Sekunden sind schon sehr beeindruckend.
Zitat: | oder's name and Location 0 - 603,567 Iterations
Vaughn Suite - Trinidad 0:51 |
Gruß Horst
EDIT:
Laufzeit: 592 Sekunden sind 9min52 Sekunden
Quelltext 1: 2: 3:
| ....086914228293595882210473480636969512153155697087
603567 it 250000 dig 5.92248000000005E+002 s |
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 05.07.12 18:04
Horst_H hat folgendes geschrieben : | @Mathematiker: bin immer noch schneller, aber weit weit weg vom Optimum, |
Tut mir leid. Du hast recht, Dein Programm ist im Moment hier das schnellste.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
FinnO
Beiträge: 1331
Erhaltene Danke: 123
Mac OSX, Arch
TypeScript (Webstorm), Kotlin, Clojure (IDEA), Golang (VSCode)
|
Verfasst: Do 05.07.12 18:09
Moin,
mal so nebenbei - am Ende des Tages, was hat man da erreicht?
LG
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 05.07.12 19:04
FinnO hat folgendes geschrieben : | mal so nebenbei - am Ende des Tages, was hat man da erreicht? |
"Der Mathematiker studiert die reine Mathematik nicht, weil sie nützlich ist; er studiert sie, weil er sich an ihr erfreut, und er erfreut sich an ihr, weil sie schön ist." Henri Poincaré
"Mathematik allein befriedigt den Geist durch ihre außerordentliche Gewissheit." Johannes Kepler
"Die Mathematik ist eine Art Spielzeug, welches die Natur uns zuwarf zum Troste und zur Unterhaltung in der Finsternis." Jean-Baptist le Rond d'Alembert
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Do 05.07.12 19:43
FinnO hat folgendes geschrieben : | Moin,
mal so nebenbei - am Ende des Tages, was hat man da erreicht?
LG |
Kann da nur für mich sprechen: Zufriedenheit, Befriedigung, ja sogar ein gewisses Genuß- bis Glücksgefühl: Wenn das Ergebnis eigener Mühen, das Compilat, endlich klappt und genau das tut, was man möchte. Meine Wenigkeit z.B. programmiert nicht per se gern, sondern ergebnisorientiert. Insofern ist Programmierung für mich nur Mittel zu Zweck, und die Programmierung sogar eine zeit- und konzentrationsraubende Lästigkeit auf dem Wege zum Ziel. Insofern erfreue ich mich sehr an den hier vorgestellten Problemen und weiß den Computer als Problemlösungshilfe durchaus zu schätzen (neuerdings wird er sogar als Beweishilfsmittel eingesetzt, aber das mögen viele Mathematiker aus gutem Grunde nicht).
Für diesen Beitrag haben gedankt: FinnO
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 05.07.12 20:04
Hallo,
das Gehirn bleibt nur frisch, wenn es ab und was neues zu tuen bekommt.Dafür sind solche sinnfreien Sachen doch ideal.
Gruß Horst
@Mathematiker:
erst wenn es schneller als 51 Sekunden ist
Aus diesem Rechner natürlich:
Zitat: | The following is a brief comparison of the fastest applications. The test machine is a 2.8GHz Pentium IV (Hyper-threading enabled) with an 800MHz FSB, over-clocked to 2.95GHz, with (2) - 512Mb, 400MHz (PC3200) DDR SDRAM modules (1GB total), 40GB hard drive, running Windows XP pro. |
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Do 05.07.12 20:45
Hyperthreading ist auch noch sowas - ich hab keinen Schimmer, wo wir hier parallelisieren sollten.
Wollen wir uns als Geschwindigkeitstest auf 20k Stellen einigen? Dann muss man nicht immer überlegen, welches Programm grade was ausgibt und es ist wenig genug, dass ich das auch in den Läufen mit GPProfiler machen kann
Ja, die Laufzeit sollte quadratisch sein. Laut MathWorld ist O(k^2) für k Iterationen die optimale Implementation.
Code gibts ab jetzt auf Github, wer dort ist kann ja forken
Horst_H hat folgendes geschrieben : | Bitte erst die Zahl ausgeben und dann die Zeiten, ich habe sie nicht mehr im Fenster. |
Habs grad geändert, die ersten und letzten 25 Stellen scheinen da gerne verwendet zu werden.
Horst_H hat folgendes geschrieben : | Vielleicht kann man zwei BCD_Ziffern in einem Byte verarbeiten, Ein SumCarFeld hätte auch nur 199 Einträge, aber dann muss man sehr oft die obere Hälfte um 4 Bit schieben. |
Siehe Code, ich hab die Carries mal komplett rausgeworfen. Ist geringfügig schneller, aber bringt nicht allzu viel (ungefähr 1 Sekunde auf 100k Iterationen).
Ich werde mal die Schleife in Asm schreiben, der Delphi-Compiler gefällt mir da nicht so ganz.
Quelltext 1: 2: 3:
| = 241389 it 100000 dig 293.801473 s 1316113735615475349297100 ... 5799080295258450663731151 |
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 05.07.12 21:24
Hallo,
ich bin gerade bei 100k Stellen in 52 Sekunden, statt 95 ist schon was
Natürlich läßt sich das parallelisieren.
Eine CPU das 1. Viertel + 4. , zweite 2. mit 3. Viertel
An den Schnittpunkten Viertel 1 auf 2 und Viertel 3 auf 4 Carry einpflegen, selbst pi hat lange Zeiten maximal 6-fach "9" hintereinander.Oh, gerade Fertig:
Quelltext 1:
| 603567 it 250000 dig 3.23028000000001E+002 s |
Merkwürdig:
bei 100 k vorher 95/ jetzt 52 Sekunden und bei 250k 592/323 Sekunden das Verhältnis ist identisch.
Eine kleine Anzahl an Digits reicht also.
NumberRevers habe ich gestrichen, findet jetzt hier statt.
Ein Pointer von End zum Anfang, der andere umgekehrt.
In der Mitte wird das Feld gewechselt
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 NumberAdd_1Feld(var Number: TNumber); var pb1,pB2 : pByte; p: integer; Carry: integer; begin pb2 := @Number[LengthNum-1]; pb1 := @Number[0]; Move(Number[0],Rev[0],LengthRev); Carry:= 0;
for p:= LengthRev-1 downto 0 do begin With SumCarFeld[Carry + pb1^ + pb2^] do begin dec(pb2); pb1^ := s; inc(pb1); Carry := c; end; end;
IF ODD(LengthNum) then begin With SumCarFeld[Carry + pb1^ + pb1^] do begin pb1^ := s; inc(pb1); Carry := c; end; end;
pb2 := @rev[LengthRev-1]; for p:= LengthRev-1 downto 0 do begin With SumCarFeld[Carry + pb1^ + pb2^] do begin dec(pb2); pb1^ := s;
inc(pb1); Carry := c; end; end; IF Carry = 1 then begin inc(LengthNum); SetLength(Number, LengthNum); Number[LengthNum-1] :=1; IF NOT(ODD(LengthNum)) then begin inc(LengthRev); SetLength(Rev, LengthRev); end; end; end; |
Nur noch ein Faktor 7 bis 10.
Jetzt probiere ich mal statische Felder.
Gruß Horst
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: Do 05.07.12 22:14
Hallo,
es freut mich, dass ich einen "kleinen Wettbewerb" bewirkt habe.
An die Zeiten von Horst_H komme ich mit meinen einfachen Programmierfähigkeiten nicht heran. Es ist mir aber gelungen, mein Programm weiter zu beschleunigen. Beim einem Austausch der Button1Click-Methode mit
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:
| procedure TForm1.Button1Click(Sender: TObject); const zmax:integer=999; var k:string; i,anz,laenge:integer; gefunden:boolean; z,e:array of byte; Time1, Time2, Freq: Int64; begin if abbruch=false then begin abbruch:=true; exit end; button1.caption:='Abbruch'; label3.caption:=''; abbruch:=false; memo1.clear; application.processmessages;
zmax:=strtoint(edit2.text); if zmax<100 then zmax:=100;
setlength(z,zmax+2); setlength(e,zmax+2); for i:=0 to zmax do begin z[i]:=0; e[i]:=0 end; k:=edit1.text; if k='' then k:='196'; laenge:=length(k); for i:=laenge downto 1 do z[laenge-i]:=ord(k[i])-48; anz:=0;
QueryPerformanceFrequency(Freq); QueryPerformanceCounter(Time1);
repeat inc(anz); if checkbox1.checked then begin k:=''; if laenge>50 then begin for i:=0 to 25 do k:=chr(z[i]+48)+k; k:=' ... '+k; for i:=laenge-26 to laenge-1 do k:=chr(z[i]+48)+k; end else for i:=0 to laenge-1 do k:=chr(z[i]+48)+k; memo1.lines.add(inttostr(anz)+#9+k+' ('+inttostr(laenge)+')'); end;
for i:=0 to laenge-1 do e[i]:=z[i]+z[laenge-1-i]; for i:=0 to laenge-1 do begin if e[i]>9 then begin inc(e[i+1]); dec(e[i],10); end; end; if e[laenge]>0 then inc(laenge);
gefunden:=true; i:=0; repeat if e[i]<>e[laenge-1-i] then gefunden:=false; inc(i); until (not gefunden) or (i>laenge div 2);
if gefunden then begin memo1.lines.add('Palindrom gefunden im Schritt '+inttostr(anz)); k:=''; for i:=0 to laenge-1 do k:=chr(e[i]+48)+k; memo1.lines.add(k); end else z:=copy(e,0,laenge);
if anz mod 1000 = 0 then begin label4.caption:=inttostr(laenge); QueryPerformanceCounter(Time2); label6.caption:=inttostr(anz)+' Zyklen | '+floattostrf((Time2-Time1)/freq,ffgeneral,10,6)+' s'; application.processmessages; end; until abbruch or gefunden or (laenge>zmax);
label4.caption:=inttostr(laenge); QueryPerformanceCounter(Time2); label6.caption:=inttostr(anz)+' Zyklen | '+floattostrf((Time2-Time1)/freq,ffgeneral,10,6)+' s'; if abbruch or (laenge>zmax) then begin memo1.lines.add('Folgenglied im Schritt '+inttostr(anz)); memo1.lines.add('Länge '+inttostr(laenge)); k:=''; for i:=0 to 25 do k:=chr(z[i]+48)+k; k:=' ... '+k; for i:=laenge-26 to laenge-1 do k:=chr(z[i]+48)+k; memo1.lines.add(k); end; button1.caption:='Berechnung'; abbruch:=true; setlength(z,0); setlength(e,0); end; |
ist die Hauptänderung das Kopieren der Summe in die Zahl: z:=copy(e,0,laenge);
Dies bringt (für mich) erstaunlich viel. Mein Rechner braucht für 100k Ziffernlänge, also 241xxx Iterationen, nur noch 184 Sekunden. Natürlich nicht zu vergleichen mit den 52 Sekunden von Horst_H.
Ein bisschen bin ich trotzdem stolz.
@Horst_H
Ganz so sinnlos ist die Suche nach dem 196er-Palindrom nicht. Sollte sich herausstellen, dass es dies nicht gibt (was natürlich eine Rechnung nicht beweisen kann), sind die Zahlentheoretiker gefragt, die dann nach der(!) Ursache für das merkwürdige Verhalten der 196 suchen müssen. Im Ergebnis gibt es dann viele Abhandlungen mit vielen neuen Sätzen und Beweisen, manchmal sogar eine ganz neue Theorie. Findest Du ein Palindrom, ersparst Du den Theoretikern eine Menge Arbeit.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
|