|
Re: Unbegrenzt viele Nachkommastellen
Wo wir doch am Anfang bei Wurzeln waren...
Ich hab hier was:
Delphi-Quellcode:
procedure NSqrt(R: IInteger; Decimals: int64; var Root: IInteger); overload;
var r1: IInteger; i: int64; s: string; begin NSet(r1, 10); if Decimals <= maxint then begin NPow(r1, decimals); NMul(r1, r1); end else begin i := 0; repeat; NPow(r1, maxint); dec(Decimals, maxint); inc(i); until i = decimals div maxint; if decimals = 1 then NMul(r1, 10) else NPow(r1, decimals); end; NMul(r1, R); NSqrt(Root, r1); end; |
Re: Unbegrenzt viele Nachkommastellen
Super, allerings gäbe es einige Verbesserungen:
1.) Decimals als Int64 ist utopisch groß, schon bei Decimals: Cardinal dürftest du die Speichergrenzen fast aller Rechner sprengen :) 2.) Alle Interfaces -> IInteger sollten entweder als const oder var übergeben werden, in deinem Falle ist R: IInteger wenig sinnvoll. 3.) Man kann NMul(R1, R1) benutzen, sauberer wäre aber NSqr(R1). Zum Glück überprüft NMul(R1, R1) ob beide Parameter identisch ist und nutzt intern sowieso NSqr(R1), es gibt also keinen Unterschied. Wäre dies NICHT so dann würde NSqr(R1) ca. 1.5 mal schneller sein als NMul(R1, R1). 4.) die Parameterreihenfolge sollte angepasst werden ans DEC, d.h. zuerst Ausgabeparameter dann readonly Eingabeparameter Es sähe dann so aus:
Delphi-Quellcode:
Man muß sich nun vorstellen was es bedeutet wenn Digits/Decimals > MaxInt wäre.
procedure NRoot(var R: IInteger; const A: IInteger; Root,Digits: Integer; Base: TBase = 10); overload;
// R = A^(1/Root) * Base^Digits resourcestring sNRoot1 = 'NRoot(), invalid paramater Root, must be >= 2'; sNRoot2 = 'NRoot(), invalid paramater Digits, must be >= 0'; var T: IInteger; begin if Root < 2 then NRaise(@sNRoot1); if Digits < 0 then NRaise(@sNRoot2); NPow(T, Base, Digits); NPow(T, Root); NMul(T, A); // A ist verbaut worden, nun können wir sicher R überschreiben NRoot(R, T, Root); // somit müssen R und A nicht distinct sein, ein Aufruf wie end; // NRoot(R, R, 2, 1000) wäre legal. (Bullet proof) Im besten Falle würde man 2^0.5 * 2^2^2^31 rechnen ! Alleine schon 2^2^31 = 2^MaxInt benötigte also 2 Gigabytes an Speicher. D.h. wenn Digits/Decimals größer MaxInt wird benötigt man weit weit mehr als Terabytes Rechner. Mal abgesehen von der nötigen Rechenzeit. Es macht also keinen Sinn Digits/Decimals größer als Integer zu deklarieren. Allerdings macht es dagegen Sinn die Zahlenbasis "Base", die Wurzel Root selber und den Wert A von dem man die Wurzel berechnen will zu übergeben. Mit obigen Code würde man zB. mit NRoot(R, NInt(15), 2, 1000, 8); die 2'te Wurzel aus 15 zu 1000 Oktalen Nachkommastellen berechnen. Also 15^(1/2) * 8^1000. Mit NRoot(R, NTwo, 2, 1000, 10); demzufolge 1000 Nachkommastellen von Quadratwurzel aus 2, und NRoot(R, NTwo, 3, 1000, 10); die 3'te Wurzel aus 2 mit 1000 Nachkommastellen. Man wird bei Wurzeln > 2 feststellen das der Quadratwurzel Algorithmus um Längen schneller ist als zu höherwertigen Wurzelbasen. Gruß Hagen |
Re: Unbegrenzt viele Nachkommastellen
Da die Implementierung von NSqrt() im Vergleich zu NRoot() im DEC so enorme performance Unterschiede aufweist, sollte folgender Code wesentlich schneller sein als obiger Code.
Delphi-Quellcode:
Gruß Hagen
procedure NRoot(var R: IInteger; const A: IInteger; Root,Digits: Integer; Base: TBase = 10); overload;
// R = A^(1/Root) * Base^Digits resourcestring sNRoot1 = 'NRoot(), invalid paramater Root, must be >= 2'; sNRoot2 = 'NRoot(), invalid paramater Digits, must be >= 0'; var T: IInteger; begin if Root < 2 then NRaise(@sNRoot1); if Digits < 0 then NRaise(@sNRoot2); NPow(T, Base, Digits); NPow(T, Root); NMul(R, T, A); // R = T * A while not Odd(Root) do begin NSqrt(R); Root := Root shr 1; end; if Root > 1 then NRoot(R, Root); end; |
Re: Unbegrenzt viele Nachkommastellen
Hi NegaH!
Also, ich weis ja nicht ob das absicht is aber ich kann das bpl - Package nicht installieren. Zuerst kommt folgender Fehler (Der eigentlich bei Installiertem DEC zu erwarten ist): Zitat:
Zitat:
Thx, c113plpbr Noch was: Du wolltest doch kritik o.ä. hier hast du was ... |
Re: Unbegrenzt viele Nachkommastellen
Hagen hatte hier nur die Packages für D5 und D6, nicht aber für D7 veröffentlicht (wenn ich nichts übersehen habe). Die kannst Du dann natürlich nicht verwenden, da sie schon teilweise fertig compiliert sind.
Nachtrag: Ich nehme alles zurück, das D7 Package ist natürlich hier dabei, also ist es was anderes. |
Re: Unbegrenzt viele Nachkommastellen
Hi Mario!
Schau nochmal genau hin: im 7. Beitrag auf der 3. Seite is nen Anhang ... Für Delphi 7 (D7). Nichts für ungut ... |
Re: Unbegrenzt viele Nachkommastellen
Zitat:
|
Re: Unbegrenzt viele Nachkommastellen
Nichts wird installiert. Ihr entpackt die ZIP's mit Ordnern. Dann öffnet ihr direkt z.B. das Test Projekt. In den Compileroptionen mit Packages compilieren abhacken, und im Editfeld sollte nur DECmath stehen. Im Searchpath des Projectes sollte "..\" stehen. Fertig, es sollte dann alles glatt laufen. Rein theoretisch kann man sogar die *.DCU Files alle löschen, wenn man mit Laufzeitpackage DECMath compiliert. Um dann aber die EXE starten zu können muß entweder DECMath.bpl ins selbe Verzeichniss wie die EXE kopiert werden, oder aber Pfad zu DECMath.bpl gelegt werden, oder DECMath.bpl wird ins System kopiert. Ich persönlich bevorzuge den Weg die Packages immer zur EXE zu kopieren.
Gruß hagen |
Re: Unbegrenzt viele Nachkommastellen
Ach eines noch. Im DECMath Package sind andere Versionen der Units aus dem DEC Package enthalten. Es kann also je nach Compiler-Suchpfaden zu kleineren Problemen kommen. Am besten ist es temporär einfach den Ordner in dem sich DEC Part I Version 3.0 befindet umzubenennen. Dadurch findet der Delphi Compiler diese Sourcen nicht mehr und wird auch nicht mehr versuchen sie neu zu compilieren. Stattdessen wird er, so wie vorgesehen, ausgehend vom Projekt den Unterordner durchsuchen, und dort die von mir mitgelieferten DCU's finden. Dieses "Problem" hat man immer schon mit Borland Produkten gehabt. Sein Borland Pascal 4 bis Version 7, dann BPW1 und 1.5, weiter mit Delphi 16 bis Delphi 7 und wahrscheinlich auch im Delphi 8, bei allen Versionen ist das einstellen der Suchpfade fürs Projekt, bis hin zur Speicherung dieser Pfade in den Projektoptionen, schon immer schlecht gelösst.
Also: 1.) Die ZIP's mit Pfaden entpacken 2.) den Ordner der DEC Part I Installation x:\DEC\Source umbenennen in x:\DEC_\Source 3.) Test Projekt in x:\DEC_D?\Test\ öffnen 4.) in den Compileroptinen ohne Packages compilieren einstellen 5.) F9 wenn man DECMath.bpl nutzen möchte und die DCU's löschen will, dann 4.) DECMath.bpl nach x:\DEC_D?\Test\DECMath.bpl kopieren 5.) in den Compielroptionen mit Packages compilieren einstellen, DECMath im Editfeld eingeben 6.) F9 Gruß Hagen |
Re: Unbegrenzt viele Nachkommastellen
@negaH: Du hast im Quelltext der nint_1 geschrieben, es könne wömiglich schneller gehen(die Pi-Berechnung). Aber wie? :)
|
Re: Unbegrenzt viele Nachkommastellen
Hi
Mehrere Optimierungsmöglichkeiten fallen mir da ein. 1.) es gibt bessere Typen des verwendeten Chudnovsky Algorithmus, sprich höherdimensionale Formeln. Statt 15 Stellen auf einmal zu berechnen können diese Chudnovsky Formeln z.B. 31 Stellen auf einmal berechnen. Allerdings sind diese Formeln viel komplizierter als die von mir benutzte 2.) die benutzte Formel basiert in weiten Teilen auf dem sogenannten "Binary Splitting". Man kann sich das so vorstellen das das Ziel eine Zahl X mit Y Stellen ist. Nun zerlegt man diese Y Stellen in zwei Teile einen Linken und Rechten Teil. Man versucht nun eine Formel zu finden die den Linken und Rechten Teil separat berechnen kann und dann nur noch den Linken und Rechten Teil miteinander multipliziert. Somit haben wir zwei kleine Berechnungen mit halb so großen Zahlen und deren Resultate werden multipliziert. Man kann nun Rekursiv wiederum den Linken und Rechten Teil teilen, usw. usw. Somit reduziert man die Zahlengrößen in den Berechnungen immer weiter. Wichtig ist es dabei das die beiden Zahlen der Linken und Rechten Seite der Berechnung möglichst gleichgroß sind. Denn dadurch wird der maximale Durchsatz, eg. Geschwindigkeit der Berechnungen erzielt. Es ist nämlich so das man zwei gleichgroße Zahlen am schnellsten Multiplizieren kann, d.h. zB. zwei Zahlen bei denen die eine Zahl 2 mal so lange wie die andere ist, wird immer langsammer pro Bit sein als wenn die beiden Zahlen etwa gleichgroß sind. Nun, exakt hier könnte man ebenfalls ansetzen, denn die von mir benutze Formel zur Pi Berechnung erzeugt NICHT immer gute Rechte + Linke Zahlen. Ziel der Optimierung ist es also die Berechnungen besser auszugleichen. 3.) Der von mir benutzte Binary Splitting Algorithmus ist ein Algo der auf Universalität codiert wurde. Im Falle der Pi Berechnung schleppt dieser Algo. z.B. eine Variable zusätzlich sinnlos mit. Das kostet Zeit. Ziel der Optimierung wäre es also einen eigenen Binary Splitting Algo. zu coden der besser auf die Anforderungen der Pi Formel angepasst ist. Unten habe ich mal den derzeitigen Bin. Splitting Algo. gepostet. 4.) Die Bin. Splitting Callback der Pi Berechnung berechnet viele succzessive Variablen. Im Grunde sind diese voneinander abhängig in ihren Zahlenwerten. Aber! meine Callback berechnet diese Werte immer absolut. Ziel der Optimierung wäre es nun diese Zahlenwerte ebenfalls inkrementell zu erzeugen, sprich die vielen kleinen Multiplikationen durch schnellere inkrementelle Additionen zu ersetzen. Dies ist durchaus möglich, man muß nur die besten Formeln dafür finden. 5.) meine Math. Library nutzt ganz verschiedene Multiplikations-verfahren abhänig von den Zahlengrößen. Für die längst-andauerenen Berechnungen = größten Zahlen wird der asymptotisch schnellste Algorithmus der heutzutage bekannt ist verwendet. Es ist die Modulare Fermat Fast Fourier Transformation von Schönhage und Strassen. Wichtig bei solchen FFT-Multiplikationen ist das Wörtchen "asympthotisch", denn es bedeutet das die Performance-Kurve im Verhältnis zu den Zahlengrößen eben NICHT linear sondern sprunghaft ist. D.h. die FFT berechnet immer in weiten Schranken unterschiedlich große Zahlen mit gleicher Geschwindigkeit. Erst wenn bestimmte Zahlkengrößen überschrittten werden steigt der Zeitaufwand der FFT sprunghaft an. Sozusagen entsteht eine Treppenfunktion in der Performance beim Ansteigen der Zahlengrößen. Nun, Ziel der Optimierung wäre es die Formeln so umzustellen das sie bei der Multiplizierung eben diese Treppenfunktion=asymptotisches Verhalten der FFT berücksichtigt. Kurz gesgt: es ist für die meisten FFT's am besten wenn die Zahlengröße in Bits ein Vielfaches von 2 ist. 6.) An vielen Stellen mit sehr wichtigen math. Funktionen habe ich in Assembler optimiert. Dabei wurden auch die neueren SSE2 Features der CPU's berücksichtigt. Beim SSE2 kann man sagen das dies ein mindestens 2 mal höhere Performance erzeugt. Allerdings es gibt noch genügend Source-Stückchen die noch nicht mit solchem SSE2 Code programmiert sind. Besodners die Funktionen für die FFT hätten das noch Potential. Ziel der Optimierung wäre es also diese wichtigen Sources in SSE2 Assembler zu coden. 7.) ein weiteres Beispiel für eine solche Optimierung ist der verwendete Division Algortihmus. Auch dieser basiert auf dem "Divide and Conquer" Verfahren. Der benutzte Algorithums ist der zur Zeit schnellste bekannte, die "Fast Recursive Karatsuba Division" von Burnikel & Ziegler. Auch dieser Algo. zerlegt das Gesamtproblem der Division in viel immer kleiner werdende Divisionen + Multiplikationen. Die kleinest Einheit von Divisions-Algo. ist aber eine normale Assemblercodierte Division nach Donald E. Knuth. Dieser Code ist aber in i486 Code programmiert. Ziel der Optimierung wäre es diesen Algo. auf SSE2 zu portieren. Dadurch düfte die Division im gesammten ca. 2 mal schneller werden. In einigen Performance-Vergleichen zu anderen Pi-Berechnugs-Programmen zeigte es sich das gerade meine Division um den Faktor 2 bis 3 langsammer ist als die der Konkurrenten. Dies liegt hauptsächlich daran das dieses Programme eine komplett andere Division von großen Zahlen benutzten. Die meisten nutzen eine Reziprokale Division die auf einer Newton Iteration basiert. Normalerweise ist dieser Algo. ineffizienter als der von mir benutzte, mit einer einzigsten Ausnahme. Eben der Divsion von sehr sehr großen Zahlen die die besonderen Eigenschaften besitzen wie sie bei der Pi-Formel von Natur aus entstehen. Somit wäre ein zweite Ziel der Oprimierung diese Reziprokale Division zu codieren. 8.) mein Speichermanagement für die IInteger ist darauf ausgelegt möglichst uuniversell flexibel zu sein. Dies äußerst sich auch darin das im Zahlenbereich bis zu ca. 500.000 Dezimalstellen von Pi mein jetziger Code eben schon ca. 2 mal schneller ist als die anderen Programme. D.h. mein Speichermanagement ist enorm effizient für kleinere Zahlen für kryptographische Algortihmen. Will man aber sehr große Zahlen berechnen, wie eben Pi, so ist es sinnvoller eine komplett andere Strategie im Speichermanagement zu verfolgen. Statt die viele kleinen Speicherzugriffe zu optimieren wird es bei großen Zahlen wichtig den Speicher möglichst linear wiederzuverwenden. Ziel der Optimierung wäre es also alle FFT Operationen innerhalb eines einmalig sehr groß allozierten Speicherbereiches inplaced durchzuführen. Dies bedingt aber eine komplette Neuprogrammierung der internen Zahlendarstellungen und Speicherzugriffe. 9.) der von mir benutzte Binary Splitting Algorithmus enthält eine partielle Formel-Optimierung. D.h. er optimiert bis zu einer Tiefe von 4, bestimmmte Multiplikationen weg. Theoretisch könnte man diese Optimierungstiefe aber viel stärker ausbauen. Dazu müssten alle Zwischenresulate der Callback bekannt sein. Nun könnte man das Bin. Splitting so optimieren das es mit der geringsten Anzahl an nötigen Multiplikationen arbeitet. Allein dies dürfte das Vrfahren mindestens 2 bis 3 mal beschleunigen. Allerdings steigt der Speicherverbrauch enorm an. Alles in allem würde ich schätzen das alle obigen Optimierungen meine Pi Berechnungen ca. 3 bis 5 mal schneller machen könnten. Damit wäre diese in der Performance ca. 2 mal schneller als das schnellste Pi Programm das es zur Zeit für PC's gibt. Allerdings, jede der obigen Optimierungen ist wesentlich komplizierter als es die jetzigen Algorithmen eh schon sind. D.h. es ist nicht so einfach wie es sich anhört. Alle bisherigen Algos. sind von mir schon bis zur max. Leistungsgrenze hin optimiert worden. Gruß Hagen Hier mal der Binary Spliting Code von mir:
Delphi-Quellcode:
type
TIIntegerSplitData = packed record P,Q,A,B: IInteger; end; TIIntegerBinarySplittingCallback = procedure(N: Cardinal; var P: TIIntegerSplitData); register; function NBinarySplitting(var P,Q: IInteger; Count: Integer; Callback: TIIntegerBinarySplittingCallback; ImplicitShift: Boolean = True): Cardinal; type TSplitParam = packed record P,Q,A,B: IInteger; Callback: TIIntegerBinarySplittingCallback; CallerEBP: Cardinal; CalcP: Boolean; end; function BinarySplitting(n1,n2: Cardinal; var R: TSplitParam): Cardinal; procedure Split_C(n: Cardinal; var R: TSplitParam); asm PUSH [EDX].TSplitParam.CallerEBP CALL [EDX].TSplitParam.CallBack POP EAX end; function Split_1(n: Cardinal; var R: TSplitParam): Cardinal; begin Split_C(n, R); if R.P <> nil then if R.A <> nil then NMul(R.A, R.P) else R.A := R.P; if R.Q <> nil then Result := NShr(R.Q) else Result := 0; end; function Split_2(n: Cardinal; var R: TSplitParam): Cardinal; var L: TSplitParam; rQs,lQs: Cardinal; begin rQs := 0; lQs := 0; L.Callback := R.Callback; L.CallerEBP := R.CallerEBP; L.CalcP := True; Split_C(n +0, L); Split_C(n +1, R); // L.A := (L.A * R.B * R.Q * L.P) shl rQs; // R.P = R.P * L.P; // R.Q = R.Q * L.Q; // R.B = R.B * L.B; // R.A = R.A * L.B * R.P + L.A; if R.Q <> nil then begin rQs := NShr(R.Q); if L.A <> nil then NMul(L.A, R.Q) else NSet(L.A, R.Q); end else if L.A = nil then NSet(L.A, 1); if L.Q <> nil then begin lQs := NShr(L.Q); if R.Q <> nil then NMul(R.Q, L.Q) else NSwp(R.Q, L.Q); end; if L.B <> nil then if R.A <> nil then NMul(R.A, L.B) else R.A := L.B; if R.B <> nil then begin NMul(L.A, R.B); if L.B <> nil then NMul(R.B, L.B); end else NSwp(R.B, L.B); if L.P <> nil then begin NMul(L.A, L.P); if R.P <> nil then NMul(R.P, L.P) else NSwp(R.P, L.P); end; if R.P <> nil then if R.A <> nil then NMul(R.A, R.P) else R.A := R.P; if rQs > 0 then NShl(L.A, rQs); if R.A = nil then begin NSwp(R.A, L.A); NInc(R.A); end else NAdd(R.A, L.A); Result := rQs + lQs; end; function Split_3(n: Cardinal; var R: TSplitParam): Cardinal; var L,M: TSplitParam; rQs,lQs,mQs: Cardinal; begin lQs := 0; mQs := 0; rQs := 0; L.Callback := R.Callback; L.CallerEBP := R.CallerEBP; M.Callback := R.Callback; M.CallerEBP := R.CallerEBP; Split_C(n +0, L); Split_C(n +1, M); Split_C(n +2, R); if L.Q <> nil then lQs := NShr(L.Q); if M.Q <> nil then mQs := NShr(M.Q); if R.Q <> nil then rQs := NShr(R.Q); // P := [R.P * [M.P * L.P]] // Q := [R.Q * M.Q] * L.Q // B := [R.B * M.B] * L.B // R.A := ([R.B * M.B] * [R.Q * M.Q] * L.A * L.P) shl (rQs + mQs) + // (([M.P * L.P] * R.B * R.Q * M.A) shl rQs) * L.B + // [R.P * M.P * L.P] * M.B * R.A // R.P := P // R.Q := Q // R.B := B if L.P <> nil then if M.P <> nil then NMul(M.P, L.P) else M.P := L.P; if M.P <> nil then if R.P <> nil then NMul(R.P, M.P) else R.P := M.P; if M.A = nil then NSet(M.A, 1); if M.P <> nil then NMul(M.A, M.P); if R.B <> nil then NMul(M.A, R.B); if R.Q <> nil then NMul(M.A, R.Q); if rQs > 0 then NShl(M.A, rQs); if R.A = nil then NSet(R.A, 1); if R.P <> nil then NMul(R.A, R.P); if M.B <> nil then NMul(R.A, M.B); NAdd(R.A, M.A); if L.B <> nil then NMul(R.A, L.B); if M.Q <> nil then if R.Q <> nil then NMul(R.Q, M.Q) else R.Q := M.Q; if M.B <> nil then if R.B <> nil then NMul(R.B, M.B) else R.B := M.B; if L.A = nil then NSet(L.A, 1); if L.P <> nil then NMul(L.A, L.P); if R.B <> nil then NMul(L.A, R.B); if R.Q <> nil then NMul(L.A, R.Q); Inc(rQs, mQs); if rQs > 0 then NShl(L.A, rQs); NAdd(R.A, L.A); if L.Q <> nil then if R.Q <> nil then NMul(R.Q, L.Q) else R.Q := L.Q; if L.B <> nil then if R.B <> nil then NMul(R.B, L.B) else R.B := L.B; Result := lQs + rQs; end; function Split_4(n: Cardinal; var R: TSplitParam): Cardinal; var L,M,K: TSplitParam; rQs,mQs,kQs,lQs: Cardinal; begin lQs := 0; mQs := 0; kQs := 0; rQs := 0; L.Callback := R.Callback; L.CallerEBP := R.CallerEBP; M.Callback := R.Callback; M.CallerEBP := R.CallerEBP; K.Callback := R.Callback; K.CallerEBP := R.CallerEBP; Split_C(n +0, L); Split_C(n +1, M); Split_C(n +2, K); Split_C(n +3, R); if L.Q <> nil then lQs := NShr(L.Q); if M.Q <> nil then mQs := NShr(M.Q); if K.Q <> nil then kQs := NShr(K.Q); if R.Q <> nil then rQs := NShr(R.Q); if L.P <> nil then if M.P <> nil then NMul(M.P, L.P) else M.P := L.P; if M.P <> nil then if K.P <> nil then NMul(K.P, M.P) else K.P := M.P; if K.P <> nil then if R.P <> nil then NMul(R.P, K.P) else R.P := K.P; if M.A = nil then NSet(M.A, 1); if M.P <> nil then NMul(M.A, M.P); if L.B <> nil then NMul(M.A, L.B); if R.Q <> nil then if K.Q <> nil then NMul(K.Q, R.Q) else K.Q := R.Q; if K.Q <> nil then NMul(M.A, K.Q); if M.Q <> nil then NMul(K.Q, M.Q); if L.A = nil then NSet(L.A, 1); if L.P <> nil then NMul(L.A, L.P); if K.Q <> nil then NMul(L.A, K.Q); if M.B <> nil then NMul(L.A, M.B); if mQs > 0 then NShl(L.A, mQs); NAdd(L.A, M.A); if R.B <> nil then if K.B <> nil then NMul(K.B, R.B) else K.B := R.B; if K.B <> nil then NMul(L.A, K.B); Inc(kQs, rQs); if kQs > 0 then NShl(L.A, kQs); if K.A = nil then NSet(K.A, 1); if K.P <> nil then NMul(K.A, K.P); if R.Q <> nil then NMul(K.A, R.Q); if R.B <> nil then NMul(K.A, R.B); if rQs > 0 then NShl(K.A, rQs); if R.A = nil then NSet(R.A, 1); if R.P <> nil then NMul(R.A, R.P); if K.B <> nil then NMul(R.A, K.B); NAdd(R.A, K.A); if M.B <> nil then if L.B <> nil then NMul(L.B, M.B) else L.B := M.B; if L.B <> nil then NMul(R.A, L.B); NAdd(R.A, L.A); NSwp(R.Q, L.Q); if K.Q <> nil then if R.Q <> nil then NMul(R.Q, K.Q) else NSwp(R.Q, K.Q); NSwp(R.B, L.B); if K.B <> nil then if R.B <> nil then NMul(R.B, K.B) else NSwp(R.B, K.B); Result := lQs + kQs + mQs; end; function Split_D(n1, n2: Cardinal; var R: TSplitParam): Cardinal; var L: TSplitParam; nM,lQs,rQs: Cardinal; begin nM := (n1 + n2) shr 1; L.Callback := R.Callback; L.CallerEBP := R.CallerEBP; L.CalcP := True; lQs := BinarySplitting(n1, nM, L); rQs := BinarySplitting(nM, n2, R); // R.A := (R.A * L.B * L.P) + (L.A * R.B * R.Q) shl rQs // R.P := R.P * L.P // R.Q := R.Q * L.Q // R.B := R.B * L.B if R.B <> nil then begin if R.Q <> nil then begin if L.A <> nil then begin NMul(L.A, R.B); NMul(L.A, R.Q); if rQs > 0 then NShl(L.A, rQs); end else begin NMul(L.A, R.B, R.Q); if rQs > 0 then NShl(L.A, rQs); end; end else L.A := R.B; end else if R.Q <> nil then if L.A <> nil then begin NMul(L.A, R.Q); if rQs > 0 then NShl(L.A, rQs); end else if rQs > 0 then NShl(L.A, R.Q, rQs) else L.A := R.Q; if L.B <> nil then begin if R.A <> nil then begin NMul(R.A, L.B); if L.P <> nil then NMul(R.A, L.P); end else if L.P <> nil then NMul(R.A, L.B, L.P); end else if L.P <> nil then if R.A <> nil then NMul(R.A, L.P) else NSet(R.A, L.P); if R.A = nil then begin NSwp(R.A, L.A); NInc(R.A); end else if L.A <> nil then NAdd(R.A, L.A) else NInc(R.A); if R.CalcP then if L.P <> nil then if R.P <> nil then NMul(R.P, L.P) else NSwp(R.P, L.P); if L.Q <> nil then if R.Q <> nil then NMul(R.Q, L.Q) else NSwp(R.Q, L.B); if L.B <> nil then if R.B <> nil then NMul(R.B, L.B) else NSwp(R.B, L.B); Result := lQs + rQs; end; resourcestring sNBinarySplitting = 'NBinarySplitting(), internal error index = 0'; begin case n2 - n1 of 0: begin NRaise(@sNBinarySplitting); Result := 0; end; 1: Result := Split_1(n1, R); 2: Result := Split_2(n1, R); 3: Result := Split_3(n1, R); 4: Result := Split_4(n1, R); else begin Result := Split_D(n1, n2, R); end; end; end; // apply a custom binary splitting computation for linear convergent series // // p[0]...p[n] a[n] // S = P / Q = sum(n=0..Count -1) ----------- ---- // q[0]...q[n] b[n] // // TI97-7.ps, Fast multiprecision evaluation of series of rational numbers // Bruno Haible & Thomas Papanikolaou // for each coefficient p[n], q[n], a[n], b[n] are callback(N, P, Q, A, B) called. // The custom callback procedure can access as nested procedure to the owner stack. // If the IIntegers P,Q,A,B of the callback are unchanged = not assigned = NIL then // there assumed to a value of +1. That reduce memory, interfaces and speedup. // Means we can implicate that the callback is called by Callback(n, 1, 1, 1, 1); resourcestring sNBinarySplitting = 'NBinarySplitting(), Count must be >= 0 and Callback <> nil'; var D: TSplitParam; begin if (Count < 0) or not Assigned(Callback) then NRaise(@sNBinarySplitting); if Count = 0 then begin NSet(P, 0); NSet(Q, 1); Result := 0; end else begin asm MOV EAX,[EBP] MOV D.CallerEBP,EAX end; D.Callback := Callback; D.CalcP := False; Result := BinarySplitting(0, Count, D); if D.B <> nil then if D.Q <> nil then NMul(D.Q, D.B) else NSwp(D.Q, D.B); if ImplicitShift then begin NShl(D.Q, Result); Result := 0; end; NSwp(P, D.A); NSwp(Q, D.Q); end; end; |
Re: Unbegrenzt viele Nachkommastellen
@negaH:
Ich hab den Binary-Splitting mal "entmüllt" und auf die NPi-Berechnungen angewandt. Der Fast-Chudnovsky wurde bei 500.000 Nachkommastellen tatsächlich 16 ms schneller. :wink: Du hast doch auch gepostet, es gäbe "Höherdimensionale" Varianten des Chudnovsky-Algos. Was haben wir dabei unter "Höherdimensional" zu verstehen, und vor allem, wie funktioniert er? BtW: Komm, gib nur die Formeln an, ich will auch mal denken! Und: wie berechnet man die Euler-Zahl e? |
Re: Unbegrenzt viele Nachkommastellen
Liste der Anhänge anzeigen (Anzahl: 1)
Zitat:
Aber du könntest mir mal deine Umsetzung mailen. Zitat:
1.) man benötigt Rationale Zahlen oder eben Fließkommaarithmetik, dies bringt aber eine gewisse "Unsicherheit" in der Genauigkeit mit sich. D.h. die Dimension in der der Programmiere/Mathematiker seinen Algo. überdenken muß wird höher. 2.) die Formel ansich arbeitet in höherer Dimension, aber dazu solltest du die einschlägigen WEB Seiten/PostScripts studieren. Ich bin einer der Mathematik am liebsten macht wenn ein Problem auch nur mit Halbwissen zu lösen ist. D.h. auch ich verstehe nicht jede Formel zu 100% in all ihren Abgründen, trotzdem kann ich sie programmieren. Nun diese 31 Stellen Chundnovsky Formel ist so ein Monster. Zitat:
Zitat:
Delphi-Quellcode:
Umgeschrieben bedeutet das für dich
procedure NExp(var A: IInteger; U,V: Integer);
// A = A * e^(U / V) A = A * e^(1/1) = A * e^1 = A * e. Du setzt A z.B. auf A = 10^500000 und rufst danach NExp(A) auf, schon hast du A = e * 10^500000, also die 500000 Dezimalstellen von e. Gruß Hagen |
Re: Unbegrenzt viele Nachkommastellen
Hi negaH!
Das einzige an "entmüllung" ist, alle if-Dinger mir x.B als Bedingung zu löschen. Ist also nicht wirklich kompliziert :wink: |
Re: Unbegrenzt viele Nachkommastellen
hi negaH
also dein IInteger fasziniert mich ! :-D hättest du nicht lust eine ordentliche lib zum machen so ähnlich wie gmp aber halt für delphi mit ner kleinen beschreibung aller enthaltenen funktionen ? weil leider gib es keine vernünftige BigInt lib für delphi :cry: und deine NInts.pas/dcu ist das beste was ich derzeit finden kann :-D hab zwar auch eine gmp-dll aus der ich die gmp-funktionen importe aber das ist keine saubere lösung so ein package für delphi wäre echt ne spitzen sache ! :thumb: mfg Dano |
Re: Unbegrenzt viele Nachkommastellen
Danke und ähm
Zitat:
Nee, was du möchtest ist eine OpenSource Bibliothek weil es keine freien Sourcen auf diesem Sektor für Delphi gibt. Und tatsächlich meine IInteger sind keine Freeware, da haste Recht. Ich glaube du unterschätzt den Aufwand erheblicheine solche Lib zu coden (ist ja nicht nur die Programmierung). Ich habe ca. 3 Jahre dran gebastelt, ca. 75% ist in Assembler selbst der SSE2 Befehlssatz wird unterstützt. Aber viel wichtiger sind die Algorithmen, und da kann ich sehr stolz behaupten das selbst die GMP Experten Teams nicht so effiziente Algos. enthalten wie in meiner Lib. Also, bitte warum sollte ich jetzt nun das Bedürfniss haben diese 3 Jahre Spaß mit der Hölle, nochmal zu wiederholen ? Gruß Hagen |
Re: Unbegrenzt viele Nachkommastellen
Zitat:
|
Re: Unbegrenzt viele Nachkommastellen
sorry, wenn dich meine ausführlichen Antworten stören, dann las ichs einfach, tschüß.
Gruß hagen |
Re: Unbegrenzt viele Nachkommastellen
:shock: ich glaube nailor hat das eher scherzhaft bzw. "frotzelig" gemeint...
Komm bloß nicht auf die Idee, nicht mehr so grandios zu antworten! Ich verstehe zwar nicht wirklich immer alles, wenn es so ins Detail geht, aber ich lese sowas immer mit sehr großem Interesse! (Gerade was mathematische Klamotten angeht). Also: Keep cool, and keep on! :) |
Re: Unbegrenzt viele Nachkommastellen
@Hagen ich kann auch nur sagen immer weiter, deine mehr als ausführlichen antworten machen es erst richtig interessant sich hier ein bißchen durchzulesen, vor allem weil mich der mathematische bereich auch sehr interessiert aber man den mit 11. klasse schulbildung noch nich wirklich blickt :roll: :mrgreen:
also immer weiter so, hör bloß nich auf :thumb: :mrgreen: |
Re: Unbegrenzt viele Nachkommastellen
sorry.... das mit dem ordentlich war nicht so gemeint daß deine NInts nicht ordentlich ist....
aber sinus und cosinus... ist ja extra(NInt_1.dcu)... ich dachte da mehr an ein 'all in one'... das ich nur eine lib/package includen muß und alles da ist... den aufwand kenn ich.... deshalb frag ich ja ob du so lieb bist eine lib online zu stellen...natürlich mit deine copyrights... weil so versuchen jeden tag 100 noobs wie ich selber sowas zu machen (rechnen mit endlos langen zahlen)... und das will nicht so recht klappen... und da sowas bei delphi irgendwie ein großes schwarzes loch ist(nichtmal borland bietet sowas als zusatz an) und in c/c++ gibts mehrere libs, wäre es schön gewesen wenn es geklappt hätte... das was du netterweiße zum download gegeben hast ist leider igendwie nur in mehreren stücken... besser wer ein include und ne anleitung für leute wie mich die nicht so erfahren sind in delphie... so nach dem motto "DECMath in uses eintragen, dann habt ihr IInteger, und ihr könnt damit das, das, das machen" opencource muß es ja nicht unbedingt sein, ich würde es sowieso nicht verstehn^^.... hauptsache es funktionier... und wenn es jemand comerziel nutzen will... muß er es natürlich bezahlen, und wenn du selber schon sagst das selbst gmp nich so gut ist wie dein IInteger, wäre das eigentlich eine marktlücke für dich :-D genauso wie dein DEC naja... mfg Dano P.S: nailor, das war nicht nett |
Re: Unbegrenzt viele Nachkommastellen
Das war in keinster Weise böse oder verunglimpfend gemeint. Aber du hast echt sehr viel geschrieben und dann damit geendet, dass du vorraussichtlich in nächster Zukunft nichts neues mehr zu dem Thema programmieren wirst, obwohl du anscheinend noch voll im Thema drin bist und mit so einem Post den besten Grundstein zu einer Weiterentwicklung gelegt hast.
Falls das jetzt von dir und/oder auch anderen als Angriff oder so gewertet wurde, will ich betonen dass das nicht meine Intention war und mich für die Aufregung entschuldigen, die ich verursacht habe. Und jetzt: Viel Spass beim weiterposten! :dp: |
Re: Unbegrenzt viele Nachkommastellen
hi Hagen
ich habe mal bissel gebastelt^^ und brauche zufallszahlen die funktion NRnd liefert aber immer zahlen die ähnlich sind :( man kann der funktion noch ein TRandom übergeben.... aber was ist das und wie benutze ich das? oder wie kann ich am besten echt gute zufallszahlen bei IInteger erstellen? mfg Dano |
Re: Unbegrenzt viele Nachkommastellen
Zitat:
Meinst du das nach dem Start der Anwendung immer wieder mit den gleichen Zahlen begonnen wird ? Oder meinst du das die Zahlen alle im gleichen Wertebereich liegen, zB. eben immer 512 Bits -> 2^512 <= x < 2^513 liegen ? Über den Parameter vom Typ TRandom kannst du deinen eigenen Zufallsgenerator übergeben. Sei es ein komplett anderer Zufallsgenerator oder nur eine eigene Instanz, sprich eigene Kopie mit eigenen Initialisierungsparamatern. Aber normalerweise sollte der RNG vom DEC, ein LFSR mit maximaler Periode von 2^2048, vollkommen ausreichend und sicher sein. Wird einer Funktion die eine TRandom-Instance benötigt stattdessen NIL übergeben so wird diese Funktion intern den RND aus der Unit RNG.pas benutzen. Wie bei jedem Pseudozufalls-Generator gibt es immer zwei Dinge zu beachten: 1.) die Periode und Komplexität bestimmt die kryptographische Sicherheit des Algos. TRandm_LFSR im DEC ist ein sehr sicherer LFSR da er intern mit mindestens 128 Bit Registerbreite arbeitet. 2.) jeder PRNG muß initialisiert werden und diese Initialisierung bestimmt dann welche Zufallsbits erzeugt werden. D.h. das Seed-Register des RNGs bestimmt was für Bits -> IInteger-Zahlen, erzeugt werden. Wird also dieses Seedregister immer auf den gleichen Wert initialisiert so MÜSSEN durch diesen RNG die selben Zahlen erzeugt werden. Um immer unterschiedliche Zahlen zu erzeugen muß man dieses Seed Register also beim Start der Anwendung mit anderen Werten füllen, wie beim Delphi Random() mit Randomioze() möglich. Nun, aber diese Initialisierung ist der kryptograühisch kritischste Moment. Werden schlechte Werte dafür benutzt, sprich sind diese reproduzierbare Werte, so ist der komplette Output dieses Generators als unsicher einzustufen !! Andererseits ist es für mathematische/statistische Berechnungen absolut wichtig das ein RNG immer wieder reproduzierbare Zufallswerte erzeugt. Demzufolge darf eine beliebige Random-Bibliothek niemals einen Zufallsgenerator mit igendwelchen Werten initialisieren, dies muß immer Aufgabe des Programmierers und Nutzers dieser Library durchführen. Also DU ;) Gruß Hagen |
Re: Unbegrenzt viele Nachkommastellen
hi Hagen,
jup, mit ähnlich meinte ich das die zahlen immer zwischen einer 2er potenz sind also bei NRnd(Zahl,16); sind sie immer zwischen 32 000 und 65 000.... die zufallszahlen haben nichts mit verschlüsselung zu tun, sind nur für mathematische versuche ;) habe aber einen weg gefunden :) ich lösche einfach das erste bit in der IInteger mit NCut dann kommen ganz gute ergebnisse^^ hier mal ein beispiel: ein memo und ein button auf form1 und los gehts^^
Delphi-Quellcode:
und wenn ich das richtig verstanden habe brauche ich NRnd kein TRandom übergeben weil er dann automatisch das TRandom aus der RNG.Pas benutzt und das reicht für gute zufallszahlen?
procedure TForm1.Button1Click(Sender: TObject);
var Zahl,ZahlMin,ZahlMax: IInteger; Count,Bits: Integer; begin Bits:=16; NSet(ZahlMax,NNull); NRnd(ZahlMin,Bits); for Count:=1 to 100 do begin NRnd(Zahl,Bits); NCut(Zahl,Bits-1); if NCmp(Zahl,ZahlMax)= 1 then NSet(ZahlMax,Zahl) else if NCmp(Zahl,ZahlMin)= -1 then NSet(ZahlMin,Zahl); Memo1.Lines.Add(NStr(Zahl,10)); end; Memo1.Lines.Add('------------------------'); Memo1.Lines.Add('Kleinste: '+NStr(ZahlMin,10)); Memo1.Lines.Add('Größte: '+NStr(ZahlMax,10)); end; mfg Dano PS: dein IInteger ist echt klasse :) |
Re: Unbegrenzt viele Nachkommastellen
Delphi-Quellcode:
Bits gibt dabei die Größe=Wertebereich des IInteger's in A an der erzeugt werden soll.
NRnd(var A: IInteger; Bits: Integer = 0; Sign: Boolean = False; Random: TRandom = nil); overload;
Also bei NRnd(A, 64); wird A im Bereich von 2^63 <= A < 2^64 sein, ergo A hat garantiert eine Größe von 64 Bits. Dieses Verhalten ist bei der Anwendung von großen Zahlen, sei es für Kryptographie, Mathematik ect. pp. am häufigsten erwünscht. Meistens muß man eben Zufallszahlen erzeugen (zb. Primzahlen) die exakt X Bits groß sind. Wird Sign == TRUE gesetzt so wird auch das Vorzeichen per Zufall erzeugt, ansonsten bleibt es wie es ist. Du kannst aber auch Bits == 0 übergeben. Dann wird intern Bits per Zufall im Bereich von 1 bis 2048 liegen, d.h. die Function NRnd() erzeugt dann Zufallszahlen im Bereich von 0 <= A < 2^2048 Statt NCut() hättest du dann NBit(A, NHigh(A), False); nehmen können, dies dürfte schneller sein. Wie du am nachfolgendem Source von NRnd() erkennen kannst kann Bits < 0 sein. Zb. mit NRnd(A, -64); würdest du Zahlen im Bereich von 0 <= A < 2^64 erzeugen. Also im Grunde das was du suchtest. Ok, der negative Bits Parameter ist ziemlich versteckt allerdings benötigt man solche Zufallszahlen fast niemals. Zumindestens ich brauchte diese Funktionalität nur ein einzigstes mal bisher. Dein NCut() Aufruf wirkt mathematisch wie ein NMod(A, 2^16), sprich Modulare Division. Falls du Zb. Zahlen im Bereich von 100.000 <= A < 1.000.000 erzeugen wolltest dann sähe dies so aus
Delphi-Quellcode:
Gruß Hagen
NRnd(A, -32);
NMod(A, 1000000 - 100000); NAdd(A, 100000);
Delphi-Quellcode:
procedure NRnd(var A: IInteger; Bits: Integer = 0; Sign: Boolean = False; Random: TRandom = nil);
var I: Integer; begin with NAllocNew(A)^ do begin if Random = nil then Random := RND; if Bits = 0 then Bits := Random.Int(256 * 8); if Bits = 0 then begin FCount := 0; FNeg := False; end else begin if Bits < 0 then begin Bits := -Bits; I := (Bits + 31) shr 5; if Cardinal(I) > FSize then NSetCount(A, I, cfNoFill) else FCount := I; Random.Buffer(FNum^, I * 4); Dec(I); Bits := FNum[I] and ($FFFFFFFF shr (32 - Bits and 31)); FNum[I] := Bits; if Bits = 0 then NNormalize(A); end else repeat I := (Bits + 31) shr 5 +1; if Cardinal(I) > FSize then NSetCount(A, I, cfNoFill) else FCount := I; Random.Buffer(FNum^, I * 4); if FNum[I] = 0 then NNormalize(A); I := NSize(A) - Bits; if I > 0 then NShr(A, I); until I >= 0; if Sign then FNeg := Random.Int(2) = 1; end; end; end; |
Re: Unbegrenzt viele Nachkommastellen
Liste der Anhänge anzeigen (Anzahl: 4)
Zitat:
Die statistischen Eigenschaften der LFSR's = Linear Feadback Shift Register sind bei weitem besser als die der LCG's. Wenn man Zb. eine Monochrome Bitmap per Random() Pixelweise füllt so kann man je nach Seed und Bitmap Dimension eindeutig grafische Muster erkennen, sprich Wiederholungen. Nimmt man dagegen einen LFSR so sieht man immer ein Bild das Weises Rauschen darstellt, also keine Wiederholungen. Es macht ja keinen Sinn eigene TRandom_XXX Klassen im DEC zu integrieren wenn diese nicht wesentlich besser sind als Delphis Random() Funktion. Zudem ist der 128 Bit LFSR ziemlich schnell,auf einem alten PII 266MHz Rechner erzeugt dieser LFSR Zufall mit 40Mb/sec. Ich habe dir aber mal meine alten zusätzlichen TRandom_XXX Klassen rangehangen. Diese basieren NICHT auf IInteger sondern auf TBigNum, meiner vorherigen Klassenbasierten Large Integers. Enthalten sind ein LCG = TRandom_LCG = Linear Congruential Generator der aber im Gegensatz zum Delphi Random() LCG mit viel viel größeren Perioden arbeiten kann. Statt also nur 2^32-1 Bit Periode kannste den mit 2^2048 oder viel viel größerer Periode laufen lassen. Dann der TRandom_MSG = "Micali Schnorr" Generator, dieser basiert auf dem RSA Verfahren und ist ein kryptographisch sicherer RNG wenn man die beiden Primzahlen >= 512 Bit wählt. Bei Primzhalne mit 512 Bit wäre demnach die Periode 2^1024 -1 Bits, und falls man die benutzten Primzahlen und Seeds nicht kennt ist er nicht knackbar -> sprich vorhersehbar. Dann der TRandom_BBS = "Blum Blum Shub" Generator. Das ist der Quadratische Restegenerator und der zur Zeit mathematisch beweiseneermaßen einzigst sichere Zufallsgenerator. Dann der TRandom_ISAAC = der nach dem ISAAC Verfahren arbeitet. So ganz traue ich diesem nicht, allerdings gibt es viele vergleichbare Impelementierungenin anderen Programmiersprachen, und er wird sehr oft verwendet. Um also zu diesen anderen Libraries kompatibel zu sein. Natürlich müsstest du die TBigNums durch IInteger ersetzen, das habe ich bisher nicht gemacht. Gruß Hagen PS: und danke für's Kompliment ;) |
Re: Unbegrenzt viele Nachkommastellen
Hi Hagen
danke,danke,danke :) ich hab jetzt ne lösung mit der ich gut zurecht komme ;) also danke ich dir für deine hilfe :) nun hätte ich noch eine andere frage function NRoot(var A,R: IInteger; const B: IInteger; E: Integer): Boolean; overload; // 1.) was ist R? wenn das der Rest sein soll, dann stimmt irgend etwas nicht.... weil er dann bei manchen ergebnissen unfug macht :( mfg Dano |
Re: Unbegrenzt viele Nachkommastellen
Ja, es sollte der Reminader = Rest sein.
Kannst du mir ein oder besser mehrere Beispiele geben wo er Unfug macht ? Das sollte er nämlich nicht und ich zittere schon bei dem Gedanken der Fehlersuche !
Delphi-Quellcode:
function NRoot(var A,R: IInteger; const B: IInteger; E: Integer): Boolean; overload;
A = B^(1/E) R = B - A^E ergo: B = A^E + R Gruß hagen |
Re: Unbegrenzt viele Nachkommastellen
hi Hagen :)
sorry das die antwort so lange warten ließ, aber das RL fordert meine ganze zeit also: ich habe mal fix ein demoprogramm gemacht wo einmal mit function NRoot(var A,R: IInteger; const B: IInteger; E: Integer): Boolean; overload; die wurzel + rest gebildet wird und dann eine gegenrechnung zur prüfung das ist alles was mit "1." im memo erscheint und dann einmal mit function NRoot(var A: IInteger; const B: IInteger; E: Integer): Boolean; overload; wo ich den rest selber bilde indem ich die wurzel wieder potenziere und von ausgangswert subtrahiere und eine gegenrechnung zur prüfung mache das ist "2." im memo
Delphi-Quellcode:
also button und memo ist klar.... also brauchst nur den button-event + die format-const kopieren
unit Unit1;
interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls; type TForm1 = class(TForm) Button1: TButton; Memo1: TMemo; procedure Button1Click(Sender: TObject); private { Private-Deklarationen } public { Public-Deklarationen } end; var Form1: TForm1; implementation {$R *.dfm} uses NInts; // unsere eigene formatkonstante.... const NStrFormatTT: TStrFormat = ( Base: 16; Plus: ''; Minus: '-'; Zero: ''; Comma: ','; DigitsPerBlock: 0; BlockSep: ' '; BlockPadding: ' '; DigitsPerLine: 0; LineSep: #13#10; LinePadding: ' '; DigitsChars: '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/'; FormatChars: ' /\-+;:#~"()[]?_<>!§$%&{}'''#13#10#9; LeftAlign: False; Offset: 0; Precision: 0; ); procedure TForm1.Button1Click(Sender: TObject); var IIWurzel1,IIRest1: IInteger; IIWurzel2,IIRest2: IInteger; IIData,IINewData: IInteger; Bits,Count: Integer; begin Bits:=$ff; //Länge in bits NRnd(IIData,Bits); //Zahl Generieren //schleife um 255 mal die wurzel zu ziehen for Count:=1 to $FF do begin Memo1.Lines.Add(''); Memo1.Lines.Add(''); Memo1.Lines.Add(IntToStr(Count)+'-('+IntToHex(Count,2)+')te Wurzel ---------'); Memo1.Lines.Add('0. Zahl : '+NStr(IIData,NStrFormatTT)); Memo1.Lines.Add(''); // 1. die wurzel ziehen und das ergebnis + rest anzeigen NRoot(IIWurzel1,IIRest1,IIData,Count); Memo1.Lines.Add('1. Ergebnis : '+NStr(IIWurzel1,NStrFormatTT)); Memo1.Lines.Add('1. Rest : '+NStr(IIRest1,NStrFormatTT)); //gegenrechnen..... potenz bilden + rest addieren und anzeigen NPow(IINewData,IIWurzel1,Count); NAdd(IINewData,IIRest1); Memo1.Lines.Add('1. Prüfung : '+NStr(IINewData,NStrFormatTT)); // der 2. lange/andere weg // die wurzel ziehen und das ergebnis + rest anzeigen NRoot(IIWurzel2,IIData,Count); NPow(IINewData,IIWurzel2,Count); NSub(IIRest2,IIData,IINewData); Memo1.Lines.Add(''); Memo1.Lines.Add('2. Ergebnis : '+NStr(IIWurzel2,NStrFormatTT)); Memo1.Lines.Add('2. Rest : '+NStr(IIRest2,NStrFormatTT)); //gegenrechnen..... potenz bilden und rest addieren und anzeigen NPow(IINewData,IIWurzel2,Count); NAdd(IINewData,IIRest2); Memo1.Lines.Add('2. Prüfung : '+NStr(IINewData,NStrFormatTT)); end; end; end. Zitat:
ich hoffe das dir das hilft mfg Dano ps: im memo habe ich Courier als font.... das machts übersichtlicher |
Re: Unbegrenzt viele Nachkommastellen
hi Hagen
hab mal ein paar fragen ;)
Delphi-Quellcode:
beides ist eine restberechnung
// division with remainder, Q = A div B & R = A rem B
procedure NDivRem(var Q,R: IInteger; const A,B: IInteger); overload; // division with modular remainder, Q = A div B, R = A mod B procedure NDivMod(var Q,R: IInteger; const A,B: IInteger); overload; wo ist nun der genaue unterschied zwischen MOD und REM ?
Delphi-Quellcode:
was ist MOD2K?
// modular squaring, A = A^2 mod 2^k, A = B^2 mod 2^k
procedure NSqrMod2k(var A: IInteger; const B: IInteger; K: Cardinal); overload; wie muß man sich das vorstellen? ich hoffe du kannst ein bischen licht in mein dunkel mit dem ganzen "modularen" bringen^^ und was ist "montgomery domain" ??? mfg Dano ;) |
Re: Unbegrenzt viele Nachkommastellen
Zitat:
Zitat:
-> A = A^2 mod 2^k Vorstellen kannst du es dir so: -> x = 1234^2 mod 2^16 == 1234^2 mod $10000; Solche Operationen sind enorm schnelle Divisionen auf Binärrechnern, logisch da eine Division zu 2^k = ein Exponent zu Basis 2, eben nichts anders wie eine UND Verknüpfung mit 2^k -1 darstellen. Nach A^2 wird also das Resultat auf k Bits abgeschnitten, da man ja mit einer Binärzahl modular dividiert die aus k-1 ein Einsen besteht. Zb. A mod 2^1024 == A and (2^k-1) == A and 0b111111111.111111. Der Divisor besteht also als Binärzahl aus k-1 Einsen. Technisch gesehen bedeutet dies aber nur das man jeden Dividenden einfach auch k Bits in der Größe anbschneidet. Intern im DECMath wird zu jedem IInteger die Größe der verwendeten 32 Bit Werte verwaltet. D.h. die IInteger bestehen aus einem Linearen Speicherbereich der die Zahl enthält und einem Zähler wieviele Cardinal == 32Bit Werte man benötigt um diese große Zahl zu speichern. Eine MOD 2^k Operation wird also im Grunde immer nur diesen Zähler verkleinern und maximal den höchsten 32 Bit Wert im Speicher AND verknüpfen. Der Performancetechnisch Aufwand der MOD 2^k Operationen beschränkt sich demnach immer nur auf eine 32Bit breite AND Operation, auf bei Zahlen und einem k von vielen tausenden Bits. Will man Zb. 1 Million Nachkommastellen von Pi berechnen, benötigt davon aber nur die letzten 8 Hexadezimalen Ziffern, dann kann man das so machen das nach jeder Operation mit MOD 2^32 -> k = 32, modular verkürzt. Du kannst dir nun vorstellen das es ein gewaltiger Unterschied in der Performance ist ob man nur mit 32 Bit großen Werten oder mit 125.000 Bit großen Zahlen rechnet. Man berechnet also nur Teilziffern der gesuchten Zahl und kann so effizient und sehr schnell seine Ergebnisse mit zB. Testdaten aus dem Internet vergleichen. Man erhöht nun k, ausgehend von 32 so das nach jeder richtigen Teilberechnung die nächste Berechnung mit k * 2 durchführt. So kann man sehr effizient Überprüfungen durchführen. In NCombi.pas findest du viele solcher Verfahren die intern modulare Divisionen mit 2^k durchführen können. Zb. möchtest du 2*3*5*7*13.....65537 mod 2^32 berechnen, also das Primorial = Produkt aller Primzahlen zwischen 0 bis 65538 modulo 2^32, also nur die letzten 32 Bits = 8 Hexadezimalen Ziffern. Du benutzt dazu NPrimorial(A, 0, 65538, NInt("HEX:100000000")); d.h. der Modulare Divisor ist 2^32. Intern ruft nun NPrimorial nach jedem Rechenschritt NMod(x, 2^32) auf, und NMod() wiederum kann überprüfen ob der Divisor eine echte Potenz von 2 ist, d.h. NMod() berechnet wenn möglich das k == 32. Falls das zutrifft wird nicht mehr mit einer langsammen Standarddivision gerechnet sondern eben einfach mit Beschneidung des Resultates auf k == 32 Bits. Solche Feinheiten werden erst dann relevant wenn man Zb. bestehende Algorithmen in/aus anderen Libraries nach/von DECMath umsetzt, und sich dann bei Berechnungen mit mod 2^k Zahlen wundert warum DECmath um so vieles schneller als andere Libraries ist. Dies liegt eben daran das DECMath intern so weit dies effizient möglich ist bei vielen Operationen das schnellste Verfahren zur Lösung der Aufgabe ermittelt. Gerade die häufigsten Operationen wie die modulare Exponentation, modulare Multiplikation, modulare Quadrierung usw. profitieren dann davon wenn man mit mod 2^k berechnet. Zitat:
Für eine genaue Beschreibung solltest du besser im Internet danach suchen. Interessant an den meisten Montgomery Tricks ist aber der Fakt das diese Tricks zu einer Zeit entdeckt wurden als man mit Langzahlen wie sie heute durch Computer möglich gemacht werden, damals noch garnicht gab. D.h. Montgomery hat viele Tricks gefunden die zu seiner Zeit keinerlei reale Bedeutungen hatten. Erst viel viel später besann man sich auf diese schon bekannten Tricks zurück um damit verschiedenen Computerberechnungen zu beschleunigen. Fazit: Montgomery hat Wissen entdeckt nur weil es entdeckbar war, und nicht weil man es zur Lösung eines konkreten Zieles nötig war ;) Oder anders ausgedrückt: man entdeckt irgendwas und erfindet erst danach eine konkrete Anwendung dafür. Gruß Hagen |
Re: Unbegrenzt viele Nachkommastellen
Zu den Montgomery Funktionen zählen NMont(), NRedc() und NPowMod(). Die Montgomery Domain wird normalerweise in NPowMod() automatisch ausgewählt falls das zu einem Geschwindigkeitsvorteil auf dem jeweiligen Rechnertyp führt. D.h. in den meisten Fällen ist die interne Anwendung des Montgomery TRicks für dich als Anwender vollständig transparent, du bekommst davon nichts weiter mit. Es gibt aber sehr häufig die Notwendigkeit noch mehr spezielle Algorithmen mit DECMath zu entwickeln, die eben sehr viele modulare Divisionen zum gleichen Divisor durchführen. Da aber beim Montgomery Trick die Umwandlung der Zahlen in und aus der Montgomerydomain sehr rechenaufwändig sind, ist es vorteilhafter vor und nach solchen Spezialberchnungen nur einmalig diese Konvertierungen durchzuführen. Nun, dazu wurden eben die Funktionen NMont() und NRedc() verfügbar gemacht. Eine Anwendung dieses Falles sind die Funktionen zur Berechnng in Elliptischen Kurven in der Unit NGFps.pas.
Ich hätte diese Funktionen auch nur intern verwenden und deklarieren können, aber warum solche Funktionalität verstecken wenn man sie später eventuell gebrauchen kann ? Fazit: diese Funktionen sind sehr sehr spezieller Natur, können aber wenn man weis wie und wo die Laufzeit ganz bestimmter Algorithmen stark positiv beeinflussen. Sie sind also nur Support-Funktionen. Gruß Hagen |
Re: Unbegrenzt viele Nachkommastellen
Hi Dano,
ich habe mich mal des NRoot() Problemes angenommen. Du hast natürlich Recht gehabt, NRoot() berechnet unter bestimmten Umständen den Rest falsch. Hier mal der korregierte Source für NRoot() aus meiner Lib.
Delphi-Quellcode:
Gruß hagen
function NRoot(var A,R: IInteger; const B: IInteger; E: Integer): Boolean;
// A = B^(1/E), R = B - B^(1/E)^E, returns R == 0 if B is a perfect power of E // NRoot(1MBit, 3) = 31.6 seconds // TBigNum.NRoot(1MBit, 3) = 44.9 seconds // @A, @R can be nil, if both are nil we can check for PerfectPower // todo: apply a recursive karatsuba newton method, equal to NSqrt() resourcestring sNRoot = 'NRoot(), B must be > 0 and E > 0'; var X,Y,T: IInteger; I: Integer; begin Result := True; if E <= 0 then NRaise(@sNRoot); I := NSgn(B, True); if I <= 0 then NRaise(@sNRoot); if (E = 1) or (I = 1) then begin if @A <> nil then NSet(A, B); if @R <> nil then NSet(R, 0); end else if E = 2 then Result := NSqrt(A, R, B) else begin NBit(Y, (NSize(B) + E -1) div E, True); Dec(E); repeat NSet(X, Y); NPow(T, Y, E); NMul(Y, T, E); NAdd(T, Y); // now here -> T = Y^E * (E +1) NMul(Y, X); NAdd(Y, B); NDivRem(Y, T, Y, T); I := NCmp(Y, X); until I >= 0; // HR, BugFIX!, we have to recompute on some circumstances the remainder // Thanks to Dano to pointing me out this. if I <> 0 then begin NPow(T, X, E +1); NSub(T, B, T); end; Result := NSgn(T) = 0; if @A <> nil then NSwp(A, X); if @R <> nil then NSwp(R, T); end; end; |
Re: Unbegrenzt viele Nachkommastellen
hi Hagen
erstmal danke für deine sehr ausführliche erklärung von Mod/Mod2k/Montgomery :) ich werde mir noch ein paar quellen im internet suchen um das zu vertiefen, aber im großen und ganzen habe ich das erstmal verstanden :) dann danke für den bugfix von NRoot.... nun muß ich mir nur was einfallen lassen wie ich das am besten einbaue... wenn ich es in eine extra unit stecke und die dann bei uses importiere, nimmt er doch immer wieder die alte NRoot aus NInts.dcu :( ich habe mich jetzt ein wehnig mit Interfaces beschäftigt... die sind eigentlich eine feine sache durch das referenzcounting. nur bei IInteger komme ich auf keinen grünen zweig. normalerweise müßte das interface mit einer klasse verbunden sein, aber so richtig fündig bin ich nicht geworden. oder kann man interfaces auch ohne klasse verwenden? da sie aber nur methoden haben dürfen kann ich mir das nicht vorstellen :?: was mich nun verzweifeln läßt ist das ich als variable nur ein interface deklariere und keine klasse oder struct. also wie verwaltet das interface dann seine daten wenn es keine felder hat? leider sind die deutschen quellen im internet nicht sehr ergibig wie das interface intern so richtig arbeitet :( muß ich doch mal auf dem englichen sector suchen :gruebel: mfg Dano |
Re: Unbegrenzt viele Nachkommastellen
Hi Dano,
das sind sehr gute Fragen. Es ist richtig das IInteger KEINE Objecte sind aber denoch Interfaces. Es sind preallozierte Records bzw. genauer gesagt stinknormale Interfaces ;) Der Irrglaube heutzutage ist eben das Interfaces aus Objecten bestehen müssen, falsch: die Objecte sind eine "umständlicher" Überbau auf die Interfaces. D.h. die einfachste Interface Implementierung sind Records. Bisher kenne ich aber immer noch keine andere Delphi Source die dieses Tricks,wie bei IInteger, benutzen oder kennen. Es gibt nun mehrere Gründe warum IInteger so arbeitet: 1.) das Interface von DECMath ist komplett prozedural -> sprich es macht keinerlei Sinn die IInteger als Objecte zu bauen, das procedurale Interface mit overloaded Fuctions ist wesentlich effizienter und ausbaubarer. 2.) der nötige Programcode-"Überbau" damit IInterface mit TObject funktioniert reduziert die Performance bei sehr häufigen Aufrufen der Interfaces, ohne dabei Vorteile zu bringen (siehe 1.) Nutzt man Records hat man das alles selber unter Kontrolle und kann es hoch optimieren. 3.) die Speicherbereiche der Interfaces als Records sind "prealloziert". D.h. es ist nun ein leichtes über einen eigenen "Memory Manager" -> NMath.NPool -> die Speicherbereiche von freigegbenen Interfaces zwischenzuspeichern und später wiederzuverwenden. D.h. indirekt stellen die Interfacemethoden von IInteger, im speziellen die Allokatorfunktion und die Methode ._Release; die Schnittstelle zum internen Speichermanager NPool dar. Denn exakt zum autom. Aufruf von ._Release + ._RefCount = 0 wird der Interface Record als freier Record im Pool des DEC Speichermanagers eingeordnet. Das hat zB. zur Folge das bei der Berechnung von Pi zu 1 Million Dezimalstellen normalerweise ca. 250.000 mal ein Speicherbereich als Record-Interface vom Borland Speichermanager erzeugt werden müsste. Der Speicherpool NPool reduziert aber diese 250.000 Aufrufe auf ca. 1.000 tatsächlich Speicheranforderungen an den Borland MM. Im Falle Elliptischer Curven Berechnungen habe ich dabei eine Performancsteigerungvon ca. 10% erreicht. D.h. die IInteger Interfacemethoden stellen die Grndlage dafür dar, das man deren Speicherbereiche durch einen eigenen und optimierteren Speichermanager verwalten kann. 4.) das der Speichermanager im DECMath nun fast unabhängig vom Borland MM ist kann dieser auch speziell für Multi-Threaded Berechnungen optimiert werden. -> heist: NPool arbeitet Thread bezogen, jeder Thread installiert seinen eigenen NPool -> ergo bei IInteger-Allokationen verschiedener Thread kommen diese sich nur minimal in die Quere -> ergo kein Locking per RTLCriticalSection's wird benötigt -> ergo viel mehr Performance 5.) da der NPool als stark frequentierte Schnittstelle arbeitet, kann er dazu benutzt werden um ein Polling auf GUI Ebene durchzuführen. D.h. NPool ist auch verantwortlich das Computations-Management zu steuern, sprich über Benutzerinstallierbare Callback Interfaces kann der Programmierer periodisch Application.ProcessMesages aufrufen, oder in der Callback übder Abort eine Berechnung abbrechen, oder den zeitlichen- berchnungsmäßigen Fortschritt anzeigen. Für all diese Operationen muß der Programmierer aber NICHT in seinem mathematischem Code rumwurschteln. Man kennt das ja: man baut komplizierte Funktionen und muß darin das GUI mit Progressbars, Buttonabfragen usw. einbauen. Man muß also zeri komplette getrennte Sachen vermischen und verliert den Überblick. Nun, NPool implementiert also ein asynchrones, intervall-zeitgesteuertes Polling während der mathematischen Berechnungen. 6.) da nur die internen Funktionen im DECMath einen IInteger allozieren können, spricht man auch von Auto-allokatoren. D.h. du als Benutzer kümmerst dich NIE um die Allozierung, Zuweisung, Kopierung bei Veränderungen von IInteger Interfaces. Somit snd IInteger wie zB. LongStrings der RTL, Datenspeicher mit Autoallokation, Garbage Collections und Copy on Write Demand Feature. Du kannst als zB. auch
Delphi-Quellcode:
Schaue mal hier in die Code Library rein, da müsste es einen weitergehenden Beitrag zu meinem Interface-Trick -> "forged Interface" zu finden sein.
var
A,B,C: IInteger; begin // 1.) <- A,B,C werden automatisch mit NIL initialisiert NSet(A, 1); // 2.) <- A wurde intern automatisch alloziert und mit 1 gefüllt B := A; C := B; // 3.) <- Zuweisung von Variablen bedeutet das A,B,C auf das gleiche Object zeigen, wie bei Strings NInc(B); // 4.) <- Veränderungen an B im Inhalt führen zum "Copy on Write Demand" Feature, // B bekommt ein neue Interfacekopie alloziert, mit Inhalt '1' C := B; // 5.) <- Interface A,C wird im refCounting um 1 dekremetiert, // und C zeigt auf B, B Interface +1 im RefCounter // 6.) <- über unsichtbare try finally Blöcke sind ALLE Interface Variablen im Delphi geschützt. // hier also try finally, mit _Release(InterfaceArray[0..2]->@A) // der Compiler legt also die Variablen A,B,C so im Speicher ab das sie in einem Array[0..2] of IInteger liegen // somit kann er schnellere, Looporientierte Funktionen zum Freigeben dieser Interfaces benutzen. end; Gruß Hagen PS: ein IInteger wie A := nil wird mathematisch als 0 betrachtet, so gesehen gibt es KEINEN logischen Zusammenhang zwischen einen allozierten IInteger Interface und einem NIL Interface. Mathematisch sind BEIDES Zahlen, die eine <> 0 die andere == 0. Dies vereinfacht die Denkweise wie man IInteger benutzen kann, sie sind fast ordinale Datentypen wie Integer, Comp, Real, Double etc. Am besten vergleichbar mit LongStrings. Historisch gesehen sind IInteger die 3. Generation, nach zwei versuchen mit Objecten die wesentlich unhandlicher waren. |
Re: Unbegrenzt viele Nachkommastellen
Hier mal die Linkszu weitergehenden Erklärungen:
 http://www.delphipraxis.net/internal...ct.php?t=14605http://www.delphipraxis.net/internal...ect.php?t=7357Gruß hagen |
Re: Unbegrenzt viele Nachkommastellen
Hi Hagen :)
die beiden links sind gold wert :) nach ein paar gemütlichen stunden mit dem debugger (*ironie*^^) habe ich erstmal die ganze genialität der sache regestriert^^ alles habe ich noch nicht raus....aber kommt noch ;) ich versuch es mal zusammenzufassen: (ich hoffe du korrigierst mich falls ich irgendwas falsch interpretiere^^) im grunde nutzen wir nur ein verhalten vom compiler das er bei Interfaces zeigt.... Interfaces wie sie hier benutzt werden sind im prinziep nur zeiger auf eine VMT wobei uns der compiler ein haufen arbeit abnimmt.... im grunde kann man sie wie objekte/klassen verwenden.... 1. locale interface variable
Delphi-Quellcode:
hier wird MyIInteger auf dem stack angelegt und mit nil initialisiert
var MyIInteger: IInteger
das besondere hierbei ist das sie mit nil intialiesiert wird was bei anderen localen var (z.B. Pointer, Integer) nicht der fall wäre, die haben irgendwelche werte die vorher auf dem stack lagen.... (das so erzeugte MyIInteger würde ich mir in gewisser weise als Pointer vorstellen) 2. funktions/procedur - aufrufe die so ein Interface als parameter haben
Delphi-Quellcode:
die funktionen testet ob MyIInteger nil ist
NSet(MyIInteger,1);
Delphi-Quellcode:
wenn sie nil ist dann wird eine funktion aufgerufen die dem interface eine VMT zuweist und speicher reserviert.... dazu komme ich gleich noch ;)
if @MyIInteger <> nil then......
wenn sie nicht nil ist hat sie eine VMT und ist damit bereits initialisiert und kann verwendet werden.... 3. zuweisungen
Delphi-Quellcode:
hier ruft der compiler automatisch IntfCopy auf
MyIInteger1:= MyIInteger2
Delphi-Quellcode:
dadurch wird bei Dest der refcounter um 1 erhöht und MyIInteger1 auf die VMT von MyIInteger2 geändert
procedure _IntfCopy(var Dest: IInterface; const Source: IInterface);
und bei MyIInteger1 wird der refcounter um 1 verringert... fals er 0 wird, wird die VMT und der speicher von MyIInteger1 frei gegeben beide interface zeigen jetzt auf die selbe VMT..... dabei wird kein neuer speicher reserviert... halt wie bei Pointern 4. wenn der gültigkeitsbereich endet also wenn das ende der funktion erreicht ist wird vom compiler automatisch IntfClear aufgerufen
Delphi-Quellcode:
dabei wird der refcounter von MyIInteger um eins verringert
function _IntfClear(var Dest: IInterface): Pointer;
wird er 0, wird die VMT und der speicher von MyIInteger frei gegeben auch bei
Delphi-Quellcode:
wird der refcount um 1 für die variable verringert
MyIInteger:= nil;
5. die VMT (Virtual Methode Tabel) jedes interface hat eine VMT
Delphi-Quellcode:
diese 3 methoden müßen von klassen die ein interface nutzen implementiert werden, das macht man am einfachsten in dem man TInterfacedObject als vorfahre der klasse mit einbindet
type
IInterface = interface ['{00000000-0000-0000-C000-000000000046}'] function QueryInterface(const IID: TGUID; out Obj): HResult; stdcall; function _AddRef: Integer; stdcall; function _Release: Integer; stdcall; end; da unser interface MyIInteger in keine klasse eingebunden ist funktioniert das so nicht deshalb müßen wir unsere VMT mit den 3 funktionen selber machen jede funktion die als übergabeparameter eines unserer interfaces hat, prüft ob das interface auf nil zeigt ist das der fall reservieren wir speicher für ein pointerarray das min. 3 einträge hat die 3 pointer müßen wir natürlich auf funktionen zeigen lassen die wir selber noch implementieren müssen... die im prinzip das machen was die standartfunktionen eines interfaces machen außerdem können wir hier auch noch unsere eigenen methoden mit einbauen... indem wir die VMT mit mehr einträgen machen (>3) auch felder sind möglich, was bei normalen interfaces nicht möglich wäre Fazit: der compiler übernimmt bei interfaces das was man bei normalen objecten mit create oder free selber machen müßte... man muß sich nicht um das aufräumen kümmern... speicherlecks sind eigentlich ausgeschlossen allerdings muß man sich um die VMT selber kümmern... das ist zwar im ersten augenblick komplizierter, aber wenn es einmal gemacht ist kann man nie wieder das freigeben oder erstellen von objekten vergessen in c++ ruft der compiler automatisch den construktor für ein objekt auf wenn es als lokale variable verwendet wird...ebenso den destruktor (natürlich kann man hier auch noch den zeiger auf ein objekt verlieren und ein speicherleck bekommen...) schade das sowas nicht bei delphie automatisch geht... darum der umweg über die interfaces aber großes plus bei interfaces ist das refcounting :) und kein TObject *juhu* den overhaed den TObjekt verursacht... *omg* da haben meine klassen wehniger eigene funktionen und felder als das was sie von TObject aufgedrückt bekommen.... eigentlich auch schade das man klassen nicht ohne TObjekt erstellen kann andererseits hat die VCL auch vorteile was besonders das RAD betrifft... interaktionen mit dem benutzer der anwendung werden doch extrem vereinfacht... naja, ist bissel verworen was ich da geschrieben habe... aber ich denke mal das es halbwegs richtig ist^^ ich schnapp mir morgen erstmal das asm-buch.... hab mit tasm noch nix gemacht... nur masm... und da wird einiges anders sein bei pascal lustig fand ich nur das ich die asm-funktion von waitcursor schneller kapiert habe als das delphie-construckt^^ kleiner schneller sauberer :) naja... ich lerne ja erst noch den delphi-syntax ;) mfg Dano |
Re: Unbegrenzt viele Nachkommastellen
Hi Dano,
das war im Grunde alles korrekt, und ein Kompliment von mir weil dues ziemlich schnell erfasst hast. Es gibt aber vielleicht noch einige kleinere Richtigstellungen: 1.) Delphi implementiert bei Interface Variablen ausschließlich das korrekte Initialisieren mit NIL und das korrekte Finalisieren mit NIL, mehr nicht. Diese beiden Aufgaben macht Delphi in geschützten Codeblöcken, also unsichtbaren try finally end; Blöcken. Werden mehrere Interface-Variablen in einer Procedure benutzt so gruppiert der Compiler diese Variablen im Stack immer als Array[] of IInterface. Deren Initialisierung und Finalisierung mit NIL wird dann durch Funktionen der RTL erledigt die ganz Arrays of IInterface auf NIL setzen. Das "auf NIL" setzen bedeutet das die RTL erstmal überprüft ob die Variable <> nil ist, wenn ja wird Valiable._Release; aufgerufen und Variable := nil; gesetzt. 2.) Interfaces können, müssen aber nicht das Reference Counting implementieren. Wenn sie es tuen dann nur aus dem Grunde um sich selber korrekt zerstören zu können. D.h. die Implementierung der Allokation + Deallokation der Interfaces wird nur durch die Interfaces erledigt. Dies beiden Punkte stellen das "Garbarge Collection" Feature dar. 3.) Die proceduralen Schnittstellen im DECMath -> math. Funktionen, rufen intern bei nicht-readonly Variablen immer eine Funkton auf. Diese Funktion hat drei Aufgaben, a.) Überprüfung ob Variable ein nil Interface enthält und falls ja ein neues IInteger Intrface allozieren, und wenn nein b.) Variable enthält ein Interface also Überprüfung ob .RefCount > 1 ist, wenn ja neues IInteger Interface allozieren und Inhalt aus dem alten ind das neue kopieren. Der Kopierschritt wird aber durch einen Parameter gesteuert. c.) am Schluß gibt die Funktion einen Zeiger auf einen Record zurück -> sozusagen wndelt sie den Datentyp Pointer(IInteger) in PIIntegerRecord(IInteger) um. Diese Funktion stellt also das "Copy on Write Demand" und "Autoallokation" Feature zur Verfügung. In den meisten Fällen sieht das so aus:
Delphi-Quellcode:
NAllocCopy() ruft intern NAlloc(A, True) auf, und diese Funktion führt obigen Punkt 3. aus.
procedure NInc(var A: IInteger; B: Integer);
begin with NAllocCopy(A)^ do ..... end; Durch die Deklaration mit "var A: IInteger" haben wir ja eine "by Reference" Aufrufkonvention, wir bekommen den Zeiger auf die Zeigervariable in der das IInteger steht, und somit können wir diesen Variablen neue IInteger Interfaces zuweisen. Es dürfte aber klar sein das solche Funktionen möglichst hochoptimiert sind. Im Falle von NAlloc() wird intern in den meisten Fällen nur 3 Assembler Instruktionen ausgeführt. Leider kennt Delphi keinen Precompiler und somit keine Makros. Man sollte also wenn man mit Interfaces arbeitet immer die Aufrufkonventionen "var" oder "const" benutzen, dies ist wichtig. 4.) Interfaces sind keine Zeiger auf VMT's !! Sie sind Zeiger auf einen Speicherbereich in dem die ersten 4 Bytes == Pointer ein Zeiger gespeichert wurde der der Zeiger auf eine VMT ist. Nach diesem Pointer kommen noch eventuell Daten, die verschiedenen Felder/Member des allozierten Interface Objectes. Im Falle von IInteger also ein Zeiger auf ein Array[]of Cardinal, eine Count, Size Variable und Negative um das Vorzeichen zu speichern. IInteger Interface Variablen könnte man also direkt zu einem Record casten und somit auf die internen Daten zugreifen. Man sollte das aber nicht machen ;) So, und alle diese Features waren noch vor dem ersten eingetippten Source ein zu erreichendes Ziel, d.h. ich habe mich nur deshalb für Interfaces und prozeduraler Schnittstelle entschieden da das die einzigste Möglichkeit im Delphi seinerzeit war. Gruß hagen |
Re: Unbegrenzt viele Nachkommastellen
hi Hagen :)
ich habe mal ne kleines test-interface zusammengebastelt ich deklariere ein interface initialisiere mit einer function meine felder und die VMT soweit läuft alles prima *juhu* nun bereiten mir aber aufrufe denen ich einen parameter übergebe probleme :(
Delphi-Quellcode:
wenn ich
type
IMyInterface = Interface(IInterface) function GetName: String; stdcall; procedure SetName(Name: String); stdcall; function GetRefCount: Integer; stdcall; property Name: String read GetName write SetName; end;
Delphi-Quellcode:
aufrufe pusht er zuerst den zeiger auf den string
TestInterface.Name:='Hallo! ;)';
dann pusht er den zeiger auf meinen interface record dann call't er die funktion SetName(Name: String) soweit alles ok *freu* jetzt kommt der übliche stackrahmen (push ebp, mov ebp,esp......) und dann will er den referenzzähler des string erhöhen, und das geht schief :( der holt sie den falschen zeiger vom stack ( -> exception).... generell verwechselt er die var's aufm stack :( die sind alle um eins verschoben..... ich denke mal das das interface automatisch ein self aufn stack haut(macht er ja auch), und vom compiler wird das in der function nicht berücksichtigt gibts für das problem ne lösung? mfg Dano ;) |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 16:49 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz