|
Gauß-Verfahren - Matrix lösen
Liste der Anhänge anzeigen (Anzahl: 1)
Hallo.
Nachdem mein Algorithmus zur Erstellung einer Dreiecksmatrix endlich fertig ist, muss ich nun leider feststellen, dass dieser bei größeren Matrizen (>12 Unbekannte/Zeilen) schon einige Minuten in Anspruch nimmt. (Selbstverständlich nimmt der Rechenaufwand mit der dritten Potenz der Anzahl der Unbekannten zu) Wer sich meinen Code im Anhang anschauen wird, wird feststellen, dass dies aufgrund der aufwändigen Umsetzung mit Stringrechnung nicht verwunderlich ist. Allerdings bin ich auf den Datentyp string umgestiegen, da ich einen ganzzahligen Datentypen benötige, und der größte Ordinaldatentyp, den es in Delphi gibt, ist in erster Linie erst einmal nur Integer. Da dieser jedoch nur bis 2^31-1 (also nur ca. 2,1 Mrd.) reicht, ist man da im mathematischen Sinne sehr schnell an den informationstechnischen Grenzen angelangt. (Wie groß ist in der Mathematik schon eine Zahl mit nur 10 Dezimalstellen, im Vergleich zu einer mit z. B. 1000 Stellen?) Gleitkommazahlen wie extended sind in der Hinsicht ein gutes Vorbild, jedoch für meine Zwecke nicht zu gebrauchen, da ich Operationen Div und Modulo (Divisison mit Rest) benötige, die mit Kommazahlen leider Gottes nicht funktionieren...Also habe ich meine eigenen Methoden (+, -, *, /) implementiert, die mit (unbegrenzten) Strings rechnen und das jeweilige Ergebnis als String wieder ausgeben können. (z. B. function APlusB(A, B: TPoint): TPoint; //TPoint als Bruch (X Zähler, Y Nenner zu verstehen)
Code:
Lange Rede, kurzer Sinn:
type
TPunkt = Packed Record //Bruch mit X als Zähler und Y als Nenner X: String; Y: String; end; function APlusB(A, B: TPunkt): TPunkt; //Addiere zwei Brüche begin //und so weiter end; Ist es möglich und wenn ja wie, den Code hinsichtlich der Effizienz und des Rechenaufwandes zu optimieren um bei großen Matrizen schneller ans Ziel zu kommen? Es sollte doch möglich sein, bis zu 40x40 große Matrizen in einer passablen Laufzeit zu lösen. Am einfachsten wäre es sicherlich, einfach auf extended umzusteigen, aber 1. können da durch die vielen Rechenschritte enorme Rundungsfehler auftreten (nur Brüche sind exakt und eindeutig, extended ist leider nicht beliebig genau) und 2. wird mir extended für z.B. Modulo und damit für die Bestimmung des ggT oder kgV nichts nützen. Praktisch ist mein Taschenrechner bei der Lösung von Matrizen in die Dreiecksmatrix mittels Gauß mindestens 10x so schnell...aber dennoch exakt! Ich möchte keine Kompromisse eingehen - schnell UND exakt. Ist es vielleicht doch ohne viel Aufwand möglich, einen eigenen, viel größeren ganzzahligen Datentypen - in der Größenordnung wie extended - zu implementieren? Und wenn ja, wie? Dann könnte ich mir das ganze aufwändige Gedattel mit den Strings sparen, denn ich bin sicher da liegt die größte Bremse.:-D Schon mal lieben Dank für die weisen Antworten :shock: PS: Code und Programm im Anhang, bei diesem würde die Lösung einer 40x41 Ref Matrix mindestens unübertrieben Stunden dauern!! |
AW: Gauß-Verfahren - Matrix lösen
Ich würde ein Datenformat wählen, welches Zahlen beliebiger Größe handhaben kann. Dann tauschst Du das aus und solltest zufrieden(er) sein.
 Hier ist ein Datentyp für 512-bit Integer.Und Hier sogar für beliebig große Zahlen (bis 2 Mio Stellen).Ich fände es interessant, Deine Ergebnisse zu sehen. Klar ist aber auch: Ein Algorithmus vom Aufwand O(n^3) wird bei großen n immer langsam. |
AW: Gauß-Verfahren - Matrix lösen
Ein Gauß 40 x 40 dürfte bei Floats so 1 sec. brauchen. Das Problem hier dürfte dein Zahlenformat sein. Wie wäre es hingegen, mit Floats zu arbeiten und zur Ausgabe sich eine FloatToFrac zu schreiben.
Hier das wäre mal ein Anfang. |
AW: Gauß-Verfahren - Matrix lösen
Es ist eigentlich üblich, bei der Lösung von Gleichungssystemen mit Gleitkommazahlen zu arbeiten. Es gibt bestimmte Verfahren, um Rundungsfehler zu minimieren (beispielsweise
QR-Zerlegung). Weshalb brauchst du Ganzzahlen? Du hast es begründet mit GGT und KGV, aber ich finde das in deinem Code nur im Zusammenhang mit den Bruch-Berechnungen. Die bräuchtest du mit Gleitkommazahlen ja gar nicht mehr. Was soll am Ende wirklich berechnet werden? |
AW: Gauß-Verfahren - Matrix lösen
Hallo,
ich würde das Problem auch in Abbildung des Gauß-Verfahrens sehen. Wenn ich dir jetzt als Beispiel das LGS 2,59X+ 7,657Y= 874584 und 4,55X + 18,456Y=44837 gebe, sucht du jetzt den kgVF von 2,59 und 4,55, nur um das LGS zu lösen? mfg frank |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
|
AW: Gauß-Verfahren - Matrix lösen
Hallo,
Zitat:
Zitat:
|
AW: Gauß-Verfahren - Matrix lösen
Ich dachte, er meint das Gaußsche Eliminationsverfahren, um Gleichungssysteme zu lösen. Weil: Eine 'Matrix lösen' kann nur Neo.
|
AW: Gauß-Verfahren - Matrix lösen
hallo,
als ich Neo laß, dachte ich zuerst an den Fisch (aber der heißt nemo). mfg |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Ich habe mal MATLAB angeworfen auf meinem Desktop-PC von 2008. Ein 40x40 Gleichungssystem wird in 0,15ms gelöst. Eingabe "x = A\b;" entspricht anschaulich A^(-1)*b benutzt aber LU-Zerlegung. Eine Gauss-Implementierung von Github schafft es immer noch in 0,6ms. Bei 400 Elementen ist es auffälliger, da braucht der Gauß 400ms und linsolve() 20ms. Zum Thema: Du musst auf jeden Fall mit dem String-gerechne aufhören ;-) Vll. als erste Maßnahme mal Int64 für Zähler/Nenner hernehmen, oder wenn es WIRKLICH rational bleiben muss, dann auf Byte-Arrays für Zähle/Nenner gehen. Oder halt etwas Gehirnschmalz in eine eigene Div/Mod Funktion für Extended stecken und doch Gleitkommazahlen verwenden. |
AW: Gauß-Verfahren - Matrix lösen
Japp. Selbst mein Blödgauss aus den 80gern schafft in 1 sec eine Matrix 500 x 500. Ich denke mal TE würde sowas womöglich schon reichen. Etwas umformuliert, erste Tests, die Quelle hab ich oben angegeben.
Delphi-Quellcode:
function FloatToFracStr(const Value: Extended): string; // Quelle "delfiphan"
const Eps = 1E-12; // Fehlertoleranz var P, LastP, Q, LastQ, TempP, TempQ, U, A, D: Extended; Numerator, Denominator: int64; begin Numerator := 0; Denominator := 0; // Initialisierung A := 1; P := 1; Q := 0; LastP := 0; LastQ := 1; U := Value; // Abbruchkriterien while (CompareValue(U, 0) <> 0) and (CompareValue(Value + A, Value) <> 0) and (CompareValue(A, Eps) >= 0) do begin // Einen ganzzahligen Anteil abspalten D := Round(U); U := U - D; // Update von P und Q: Kettenbruch nachführen. Es gilt: P / Q ~= Value TempP := P * D + LastP; TempQ := Q * D + LastQ; LastP := P; LastQ := Q; P := TempP; Q := TempQ; // Approximationsfehler A := 0.25 * Abs(P / Q - Value); // Bruch umkehren if U <> 0 then U := 1 / U; end; // Vor Integerkonversion auf Bereich überprüfen if (P > High(int64)) or (Q > High(int64)) or (P < Low(int64)) or (P < Low(int64)) then raise EIntOverflow.Create('FloatToFrac: int64 overflow.'); // Vorzeichen von Nenner zum Zähler if Q < 0 then Numerator := -Trunc(P) else Numerator := Trunc(P); Denominator := Abs(Trunc(Q)); if Denominator = 1 then Result := IntToStr(Numerator) else Result := Format('%d/%d', [Numerator, Denominator]); end; |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Code:
Dieser ist zwar mit bis auf extended ausdehnbare Zahlen anwendbar, aber auch nicht zu gebrauchen, da er mir bei Zahlen A und B jenseits von integer leider falsche Ergebnisse liefert, z. B. ist A=1000000000733131 MOD B=429596729935 = 328410174386, jedoch liefert mir diese Funktion in diesem Falle einen falschen Rest von result=1992659890.
function AModB(A, B: extended): integer;
begin result := Trunc(A-Trunc(A/B)*B); end; Ich hätte außerdem doch von Anfang an mit extended gerechnet und mir die aufwändigen Strings gespart, wenn ich da die Ungenauigkeit nicht hätte, denn spätestens ab der 19-20ten Nachkommastelle ist bei extended Schluss. Habe ich eine 40x40-Dreiecksmatrix, deren 40 Einträge in der Hauptdiagonalen alle 1/40 sind, ist die Determinante D=(1/40)^40 bzw. 1/40^40, und da sind wir schon weit unterhalb von 20 Nachkommastellen. Extended würde mir dann also Null liefern, was ja aber nicht richtig ist, und 1/40 ist eindeutig nicht Nichts sondern immerhin 0,025! Ich schätze ich bin einfach auf einen ganzzahligen Datentypen angewiesen, insofern hoffe ich, dass ich mit BigInt mehr erreichen kann. Wie gesagt sind nur Brüche exakt, Gleitkommazahlen nützen mir nichts. Und mit extended zu rechnen, um diese dann mittels FloatToFrac (Eps = 1E-12) in Brüche umzuformen nützt mir ebenfalls nichts, denn aus falschen Dezimalzahlen entstehen falsche Brüche! Brüche in Dezimalzahlen umwandeln ist problemlos, sofern es die Genauigkeit zulässt - umgekehrt aber nicht. Je größer die Matrizen, umso wichtiger scheint die Rechengenauigkeit zu werden. Relativ Schnell, (scheinbar) beliebig groß, aber vor allem eindeutig UND exakt - das ist das Problem. Integer (2^31-1) ist zu klein - und extended ist ungenau. There is a need of an data type with a range of extended - paired with a precision of integer. In diesem Sinne sagt Fritz zu seinen Freund Karl: "Ich kann ganz schnell multiplizieren. Nenne mir zwei Zahlen!" Da fragt Karl ihn: "Was ist 17*13?" Da antwortet Fritz: "200." Nach kurzem Überlegen meint Karl: "Das ist aber falsch!" "Na und?", meint Fritz, "aber schnell." Und ja, Richtigkeit sollte eine höhere Priorität haben als Schnelligkeit. |
AW: Gauß-Verfahren - Matrix lösen
Sagt Karl, keine Ahnung was rauskommt, Ergebnis kommt übermorgen..
Ich wäre dir übrigens dankbar wenn du meine Posts nicht mit LOL kommentiert. Ein Eps von 1E-12 ist durchaus üblich und für den Rest der Welt in den allermeisten Fällen ausreichend.. |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Wie wäre es außerdem, wenn du mal verrätst, wofür du das ganze brauchst? Als legitimen Anwendungsfall kann ich mir höchstens noch irgendwas im Bereich Kryptographie vorstellen. Aber für mich sieht es momentan eher so aus, als ob es komplett von hinten durch die Brust ins Auge ist. |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Sollte also die Determinante D also einmal D=1/40^40 groß sein, wäre diese durch den Datentypen extended nur unzureichend erfasst, denn alle folgenden Nachkommastellen würden durch Null ersetzt (ja das ist so). Würde man dann mit diesen nicht exakten Werten noch weiterrechnen, würden sich diese Ungenauigkeiten (je größer die Matrix ist) noch potenzieren - Stichwort Numerische Stabilität. Die Antwort zu deiner letzten Frage steht im Titel dieser Diskussion: Matrizen lösen. Aber man könnte auch etliche weitere Anwendungen nennen, Verschlüsselung/Primzahlen wäre nur eine von vielen. Eine Genauigkeit von 19 Nachkommastellen mag für Mittelschulmathematik wie 1+1 reichen, aber schon dieses Beispiel zeigt schon, dass man sehr schnell an den informationstechnischen Grenzen gelangt wenn man einen großen ganzzahligen Datentypen benötigt - zumindest vorerst in Delphi. Da ich viele mathematische Problemstellungen in Programme implementiere, bin ich auf dieses Problem des zu kleinen Integers und zu ungenauen Extended schon öfter gestoßen. |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Zitat:
Kannst es gerne testen:
Delphi-Quellcode:
procedure TForm1.Button1Click(Sender: TObject);
var c,x: Extended; i: integer; begin c := 1/100; x := 1; for i := 1 to 40 do x := c*x; ShowMessage(FloatToStr(x)); end; |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Wenngleich Brüche stets abbrechend oder periodisch sein müssen (per Definition), wäre bei einem großen Bruch die Länge der Periode unter Umständen größer als 19, und genau dann wäre es nicht mehr exakt da extended alle weiteren Nachkommastellen durch Null ersetzt!
Code:
Und diese minimalen Fehler können sich bei der weiteren Berechnung gravierend potenzieren - was ich zu vermeiden versuchen möchte, deshalb die Sache mit den Strings.
procedure TForm1.Button1Click(Sender: TObject);
var zahl: extended; begin zahl:=0.3333333333333333; //16 Nachkommastellen showmessage(floattostr(3*zahl)) //result=1 statt 0.9999999999999999 end; Man bräuchte also einen Gleitkommadatentypen der unendlich viele Nachkommastellen erfasste (Beispiel 1/3), da das aber natürlich nicht geht, kann ich mit Gleitkommazahlen nichts anfangen, also benötige ich einen Ganzzahligen in dieser Größenordnung. Ich wünschte lediglich, es gäbe einen ganzzahligen Datentypen wie Integer, der aber bisschen weiter hinaus reicht, denn 2^31-1 ist nun wirklich nichts! (Im mathematischen Sinne ist jede Zahl klein, aber z. B. 2^500 wäre ja wirklich schon eher brauchbar als nur 2,1 Milliarden, sogar Banker können sich größere Zahlen vorstellen) |
AW: Gauß-Verfahren - Matrix lösen
Du wirst dich von der Idee der Exaktheit sowieso früher oder später verabschieden müssen. Rationale Zahlen kannst du zwar noch exakt darstellen, aber spätestens bei den reellen Zahlen hört es eh auf. Was machst du, wenn in deinem Gleichungsssystem z.B. die Zahl Pi oder √2 vorkommt? Auch musst du bedenken, dass oft die Eingangsdaten schon nicht exakt sind, weil es sich z.B. um Messwerte handelt.
Zitat:
Das wäre ein besserer Ansatz als Unmengen von Performance zu verschwenden, um sich in scheinbarer Genauigkeit zu wiegen, die einem am Ende sowieso nichts nützt. Zitat:
|
AW: Gauß-Verfahren - Matrix lösen
Diese Diskussion à la 'Extended ist genau genug' ist Quark. Entschuldigung. Beim Rechnen mit sehr kleinen UND sehr großen Zahlen kommen falsche Ergebnisse heraus, außer! man rechnet genau. Und das kann man nun einmal nur mit exakten Brüchen machen. Ergo benötigt man als 'Zahl' Datentyp z.B. einen Record (oder ne Klasse) mit Zähler und Nenner. Dann definiert man noch die Operationen auf diesem Zahl-Datentyp und -wupps- werden die Ergebnisse genau.
Ich habe -wie erwähnt- mit Gauß und Extened bei Berechnungen zur Kälteleistung von Kühlkompressoren keine guten Erfahrungen gemacht. Es ist blöd, wenn die Kennlinien statt im Bereich von 600W dann bei -170 liegen, weil klitzekleine Ungenauigkeiten beim Rechnen passiert sind. Gut, ich hatte Glück, das LUP Dekomposition hier geholfen hat. Aber grundsätzlich sollte man das schon anders lösen. Ich unterstelle dem TE im übrigen, sich in der Zahlentheorie und mit Genauigkeitsrechnungen auszukennen. Ich denke, da muss man nicht mehr den Besserwisser raushängen lassen. Natürlich ist niemand gemeint, ich habe das nur präventiv gesagt ;-) |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Und Int64 kann ich leider nicht nehmen, da dies kein Ordinaldatentyp im Gegensatz zu Integer ist. Mit dem Methoden QR und LUP bin ich bisher noch nicht vertraut, deswegen hatte ich mir die Berechnung erst einmal ohne weiteren Aufwand erhofft. Ich werde das mit dem BigInt mal probieren. |
AW: Gauß-Verfahren - Matrix lösen
Das
Ding von Michael ist bekannt, oder? |
AW: Gauß-Verfahren - Matrix lösen
Liste der Anhänge anzeigen (Anzahl: 2)
Zitat:
Ich habe den Code halt auf extended umgestellt. Wie erwartet, ein schreckliches Ergebnis, und noch schlimmer...(Bild 1) Abhilfe schafft hier nur die FloatToFracStr von Björk....Dankeschön, besser als gar nichts. Jedoch treten auch hier Rundungsfehler ab einer bestimmten Matrixgröße auf, schade! (Bild 2) |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
|
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Leider aber unterstützt Delphi keine sog. Langzahlarithmetik. https://de.wikipedia.org/wiki/Langzahlarithmetik |
AW: Gauß-Verfahren - Matrix lösen
Da Du eine exakte Lösung möchtest, bringt Extended gar nichts. Das wusstest Du vorher, hast es auch bewiesen und hast es nun belegt.
Der Grund für deine langsame Implementierung liegt zum Einen in der Forderung nach Exaktheit und zum Anderen an der Umsetzung mittels Strings. Alternativen, d.h. Datenstrukturen, die beliebig lange Zahlen repräsentieren, wurden Dir hier auch genannt. Also: Umsetzen! :-) |
AW: Gauß-Verfahren - Matrix lösen
Eine Langzahlarithmetik benötigt man auch bei der Ermittlung der Prüfziffer einer IBAN (aus BLZ und Konto-Nummer) sowie bei der Prüfung der Gültigkeit einer IBAN.
Code:
Wie will man mit "normalen" Delphi-Möglichkeiten prüfen, ob die 24-stellige Zahl Modulo 97 genau 1 ergibt ?
Zur besseren Veranschaulichung das ganze zusammengefasst:
Bankleitzahl 70090100 Kontonummer 1234567890 BBAN 700901001234567890 alphanumerische Länderkennung DE numerische Länderkennung 1314 (D = 13, E = 14) numerische Länderkennung ergänzt um 00 131400 Prüfsumme 700901001234567890131400 Prüfsumme Modulo 97 90 Prüfziffer 08 (98 - 90, ergänzt um führende Null) Länderkennung +Prüfziffer + BBAN = IBAN DE08700901001234567890 Die Prüfung der IBAN erfolgt, indem ihre ersten vier Stellen ans Ende verschoben und die Buchstaben wieder durch 1314 ersetzt werden. Die Zahl 700901001234567890131408 Modulo 97 muss 1 ergeben. Dann ist die IBAN gültig, was auf dieses Beispiel zutrifft. Ich habe das gelöst durch ein Nachbilden der schriftlichen Division, wie wir das früher in der Schule gelernt haben. |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Delphi-Quellcode:
Mit dem Ergebnis 700901001234567890131408 mod 97 = 1
program iban;
var i,m : integer; const s : string = '700901001234567890131408'; begin m := 0; for i:=1 to length(s) do m := (m*10 + ord(s[i])-ord('0')) mod 97; writeln(s, ' mod 97 = ', m); end. |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Wie soll das denn funktionieren ohne einen unbegrenzten Datentyp wie String oder BigInt? Ich habe dasselbe noch mit einem Array of Byte versucht - dieses war noch langsamer als die Stringrechnung. Ich werde auf Java umsteigen, da sind große Int's gang und gebe :shock: |
AW: Gauß-Verfahren - Matrix lösen
Zitat:
Hier hat Dejan Vu dir zwei Datentypen/-strukturen verlinkt. Einfach mal anschauen, runterladen und ausprobieren. |
AW: Gauß-Verfahren - Matrix lösen
Habe mal in meinen Ururururururururalt-Sourcen aus Turbo-Pascal-Zeiten gesucht und noch was gefunden (ließ sich eben mit Delphi 7 kompilieren, aber ich gehe nicht davon aus, dass es fehlerfrei ist):
Delphi-Quellcode:
Das Teil hat 99 LongInts als Vorkommastellen und ebensoviele als Nachkommastellen.
program LongIntRechnen;
{$APPTYPE CONSOLE} uses SysUtils; { INI-Datei schreiben, aus der die Anzahl der Vorkomma- und Nachkomma- } { stellen gelesen wird, sowie das Maximum je Stelle } { Maxi müßte sich aus Maximum errechnen lassen. } { Im Programm müßte dazu noch eine Plausi eingebaut werden, Maximum } { darf höchstens 10000 sein und mindestens 10. } Const { eine Multiplikation muß je Zahl möglich sein } { deshalb Maximum = 10000, 10000 * 10000 = 100000000 } Maximum : Integer = 10; { Maxi enthält die Anzahl der Nullen in Maximum } Maxi : Byte = 1; { ohne Multiplikation ist bis 1000000000 möglich } { Anzahl der LongInt-Werte für Vor- und Nachkommastellen } { jede Vor- bzw. Nachkommastelle enthält 5 Ziffern (= 50)} MaxVorkomma = 99 ; { Zusammen maximal 5400 } MaxNachkomma = 99 ; { immer gerade Zahlen } { Stellenzahl muß durch } { zwei zu dividieren } { sein, da bei Multipli-} { kation sich die Stel- } { len verdoppeln } Type TPlusMinus = (Plus,Minus); TLangzahl = Record Vorzeichen : tPlusMinus; Vorkomma : ARRAY[1..MaxVorkomma ] OF LongInt; Nachkomma : ARRAY[1..MaxNachkomma] OF LongInt; END; {.INFO} FUNCTION Replicate ( ReplicateStr : String; Replicatei : Integer) : String; {*------------------------------------------------------------------*} {¦ wiederholt angegebenes Zeichen i mal. ¦} {*------------------------------------------------------------------*} {.INFO} VAR ReplicateStrTemp : String; Replicatei2 : Integer; BEGIN ReplicateStrTemp := ''; FOR Replicatei2 := 1 TO Replicatei DO ReplicateStrTemp := ReplicateStrTemp + ReplicateStr; Replicate := ReplicateStrTemp END; FUNCTION LongAdd ( a : TLangZahl; b : TLangZahl; Var c : TLangZahl): BOOLEAN; FORWARD; FUNCTION LongSub ( a : TLangZahl; b : TLangZahl; Var c : TLangZahl): BOOLEAN; FORWARD; FUNCTION LongPlausi (Var c : TLangZahl) : BOOLEAN; Var i : Word; BEGIN LongPlausi := True; WITH c DO BEGIN FOR i := 1 TO MaxVorkomma DO IF Vorkomma [i] >= Maximum THEN LongPlausi := FALSE; FOR i := 1 TO MaxNachkomma DO IF Nachkomma[i] >= Maximum THEN LongPlausi := FALSE; END; END; FUNCTION LongKorrektur (Var c : TLangZahl) : BOOLEAN; Var i : Word; bool : Boolean; BEGIN LongKorrektur := FALSE; WITH c DO BEGIN FOR i := MaxNachkomma DownTo 2 DO BEGIN IF (Nachkomma[i] < 0) THEN BEGIN Nachkomma[i ] := Maximum - Nachkomma[i] * -1; Nachkomma[i-1] := Nachkomma[i-1] - 1; END; END; IF (Nachkomma[1] < 0) THEN BEGIN Nachkomma[1] := Maximum - Nachkomma[1] * -1; Vorkomma[1] := Vorkomma[1] - 1; END; FOR i := 1 TO MaxVorkomma - 1 DO BEGIN IF (Vorkomma[i] < 0) THEN BEGIN Vorkomma[i] := Maximum - Vorkomma[i] * -1; Vorkomma[i+1] := Vorkomma[i+1] - 1; END; END; i := MaxVorkomma; IF (Vorkomma[i] < 0) THEN BEGIN IF (Vorkomma[i] * -1) >= Maximum THEN BEGIN Vorkomma[i] := Maximum + Maximum - Vorkomma[i] * -1; END ELSE BEGIN Vorkomma[i] := Vorkomma[i] * -1; END; END; FOR i := MaxNachkomma DownTo 2 DO BEGIN While Nachkomma[i] >= Maximum DO BEGIN Nachkomma[i-1] := Nachkomma[i-1] + 1; Nachkomma[i ] := Nachkomma[i ] - Maximum; END; END; While Nachkomma[1] >= Maximum DO BEGIN Vorkomma[1] := Vorkomma[1] + 1; Nachkomma[1] := Nachkomma[1] - Maximum; END; FOR i := 1 To MaxVorkomma - 1 DO BEGIN While Vorkomma[i] >= Maximum DO BEGIN Vorkomma[i+1] := Vorkomma[i+1] + 1; Vorkomma[i] := Vorkomma[i ] - Maximum; END; END; IF Vorkomma[MaxVorkomma] <= Maximum THEN LongKorrektur := TRUE; { Null ist immer positiv } Bool := TRUE; FOR i := 1 TO MaxVorkomma DO IF Vorkomma[i] <> 0 THEN Bool := False; FOR i := 1 TO MaxNachkomma DO IF Nachkomma[i] <> 0 THEN Bool := False; IF Bool THEN Vorzeichen := Plus; END; END; FUNCTION LongGreater ( a : TLangZahl; b : TLangZahl) : Boolean; VAR i : Integer; BEGIN LongKorrektur(a); LongKorrektur(b); IF (a.Vorzeichen = Plus) AND (b.Vorzeichen = Minus) THEN BEGIN LongGreater := TRUE; EXIT; END; IF (a.Vorzeichen = Minus) AND (b.Vorzeichen = Plus) THEN BEGIN LongGreater := FALSE; EXIT; END; IF (a.Vorzeichen = Plus) AND (b.Vorzeichen = Plus) THEN BEGIN FOR i := MaxVorkomma DownTo 1 DO BEGIN IF (a.Vorkomma[i] > b.Vorkomma[i]) THEN BEGIN LongGreater := TRUE; EXIT; END ELSE IF (a.Vorkomma[i] < b.Vorkomma[i]) THEN BEGIN LongGreater := FALSE; EXIT; END; END; FOR i := 1 TO MaxNachkomma DO BEGIN IF (a.Nachkomma[i] > b.Nachkomma[i]) THEN BEGIN LongGreater := TRUE; EXIT; END ELSE IF (a.Nachkomma[i] < b.Nachkomma[i]) THEN BEGIN LongGreater := FALSE; EXIT; END; END; END; IF (a.Vorzeichen = Minus) AND (b.Vorzeichen = Minus) THEN BEGIN FOR i := MaxVorkomma DownTo 1 DO BEGIN IF (a.Vorkomma[i] < b.Vorkomma[i]) THEN BEGIN LongGreater := TRUE; EXIT; END ELSE IF (a.Vorkomma[i] > b.Vorkomma[i]) THEN BEGIN LongGreater := FALSE; EXIT; END; END; FOR i := 1 TO MaxNachkomma DO BEGIN IF (a.Nachkomma[i] < b.Nachkomma[i]) THEN BEGIN LongGreater := TRUE; EXIT; END ELSE IF (a.Nachkomma[i] > b.Nachkomma[i]) THEN BEGIN LongGreater := FALSE; EXIT; END; END; END; LongGreater := FALSE; END; FUNCTION LongLower ( a : TLangZahl; b : TLangZahl) : Boolean; VAR i : Integer; BEGIN LongLower := FALSE; LongKorrektur(a); LongKorrektur(b); IF (a.Vorzeichen = Plus) AND (b.Vorzeichen = Minus) THEN BEGIN LongLower := FALSE; EXIT; END; IF (a.Vorzeichen = Minus) AND (b.Vorzeichen = Plus) THEN BEGIN LongLower := TRUE; EXIT; END; IF (a.Vorzeichen = Plus) AND (b.Vorzeichen = Plus) THEN BEGIN FOR i := MaxVorkomma DownTo 1 DO BEGIN IF (a.Vorkomma[i] < b.Vorkomma[i]) THEN BEGIN LongLower := TRUE; EXIT; END ELSE IF (a.Vorkomma[i] > b.Vorkomma[i]) THEN BEGIN LongLower := FALSE; EXIT; END; END; FOR i := 1 TO MaxNachkomma DO BEGIN IF (a.Nachkomma[i] < b.Nachkomma[i]) THEN BEGIN LongLower := TRUE; EXIT; END ELSE IF (a.Nachkomma[i] > b.Nachkomma[i]) THEN BEGIN LongLower := FALSE; EXIT; END; END; END; IF (a.Vorzeichen = Minus) AND (b.Vorzeichen = Minus) THEN BEGIN FOR i := MaxVorkomma DownTo 1 DO BEGIN IF (a.Vorkomma[i] > b.Vorkomma[i]) THEN BEGIN LongLower := TRUE; EXIT; END ELSE IF (a.Vorkomma[i] < b.Vorkomma[i]) THEN BEGIN LongLower := FALSE; EXIT; END; END; FOR i := 1 TO MaxNachkomma DO BEGIN IF (a.Nachkomma[i] > b.Nachkomma[i]) THEN BEGIN LongLower := TRUE; EXIT; END ELSE IF (a.Nachkomma[i] < b.Nachkomma[i]) THEN BEGIN LongLower := FALSE; EXIT; END; END; END; END; FUNCTION LongEqual ( a : TLangZahl; b : TLangZahl) : Boolean; Var i : Integer; bool : Boolean; BEGIN Bool := True; FOR i := 1 TO MaxVorkomma DO IF a.Vorkomma[i] <> b.Vorkomma[i] THEN bool := FALSE; FOR i := 1 TO MaxNachkomma DO IF a.Nachkomma[i] <> b.Nachkomma[i] THEN bool := FALSE; LongEqual := Bool; END; FUNCTION LongIsZero ( a : TLangZahl) : Boolean; Var i : Integer; bool : Boolean; BEGIN Bool := True; FOR i := 1 TO MaxVorkomma DO IF a.Vorkomma[i] <> 0 THEN bool := FALSE; FOR i := 1 TO MaxNachkomma DO IF a.Nachkomma[i] <> 0 THEN bool := FALSE; LongIsZero := Bool; END; FUNCTION LongSub ( a : TLangZahl; b : TLangZahl; Var c : TLangZahl) : Boolean; VAR i : Word; bool : Boolean; BEGIN LongSub := FALSE; IF LongKorrektur(a) AND LongKorrektur(b) THEN BEGIN IF LongGreater(a,b) THEN BEGIN IF (a.Vorzeichen = Plus) AND (b.Vorzeichen = Plus) THEN BEGIN For i := 1 TO MaxVorkomma DO c.Vorkomma[i] := a.Vorkomma[i] - b.Vorkomma[i]; For i := 1 TO MaxNachkomma DO c.Nachkomma[i] := a.Nachkomma[i] - b.Nachkomma[i]; c.Vorzeichen := Plus; END ELSE IF (a.Vorzeichen = Plus ) AND (b.Vorzeichen = Minus) THEN BEGIN a.Vorzeichen := Plus; b.Vorzeichen := Plus; For i := 1 TO MaxVorkomma DO c.Vorkomma[i] := a.Vorkomma[i] + b.Vorkomma[i]; For i := 1 TO MaxNachkomma DO c.Nachkomma[i] := a.Nachkomma[i] + b.Nachkomma[i]; c.Vorzeichen := Plus; END ELSE IF (a.Vorzeichen = Minus) AND (b.Vorzeichen = Minus) THEN BEGIN a.Vorzeichen := Plus; b.Vorzeichen := Plus; For i := 1 TO MaxVorkomma DO c.Vorkomma[i] := b.Vorkomma[i] - a.Vorkomma[i]; For i := 1 TO MaxNachkomma DO c.Nachkomma[i] := b.Nachkomma[i] - a.Nachkomma[i]; c.Vorzeichen := Plus; END END ELSE BEGIN IF (a.Vorzeichen = Plus) AND (b.Vorzeichen = Plus) THEN BEGIN For i := 1 TO MaxVorkomma DO c.Vorkomma[i] := b.Vorkomma[i] - a.Vorkomma[i]; For i := 1 TO MaxNachkomma DO c.Nachkomma[i] := b.Nachkomma[i] - a.Nachkomma[i]; c.Vorzeichen := Minus; END ELSE IF (a.Vorzeichen = Plus ) AND (b.Vorzeichen = Minus) THEN BEGIN a.Vorzeichen := Plus; b.Vorzeichen := Plus; For i := 1 TO MaxVorkomma DO c.Vorkomma[i] := a.Vorkomma[i] + b.Vorkomma[i]; For i := 1 TO MaxNachkomma DO c.Nachkomma[i] := a.Nachkomma[i] + b.Nachkomma[i]; c.Vorzeichen := Plus; END ELSE IF (a.Vorzeichen = Minus) AND (b.Vorzeichen = Minus) THEN BEGIN a.Vorzeichen := Plus; b.Vorzeichen := Plus; For i := 1 TO MaxVorkomma DO c.Vorkomma[i] := a.Vorkomma[i] - b.Vorkomma[i]; For i := 1 TO MaxNachkomma DO c.Nachkomma[i] := a.Nachkomma[i] - b.Nachkomma[i]; c.Vorzeichen := Minus; END ELSE IF (a.Vorzeichen = Minus) AND (b.Vorzeichen = Plus) THEN BEGIN a.Vorzeichen := Plus; b.Vorzeichen := Plus; For i := 1 TO MaxVorkomma DO c.Vorkomma[i] := a.Vorkomma[i] + b.Vorkomma[i]; For i := 1 TO MaxNachkomma DO c.Nachkomma[i] := a.Nachkomma[i] + b.Nachkomma[i]; c.Vorzeichen := Minus; END END; END ELSE BEGIN Writeln('a oder b sind zu groß',#7); EXIT; END; LongKorrektur(c); LongSub := TRUE; END; FUNCTION LongAdd ( a : TLangZahl; b : TLangZahl; Var c : TLangZahl) : BOOLEAN; VAR i : Word; BEGIN LongAdd := FALSE; IF LongKorrektur(a) AND LongKorrektur(b) THEN BEGIN IF ((a.Vorzeichen = Plus) AND (b.Vorzeichen = Plus)) OR ((a.Vorzeichen = Minus) AND (b.Vorzeichen = Minus)) THEN BEGIN For i := 1 TO MaxVorkomma DO c.Vorkomma[i] := a.Vorkomma[i] + b.Vorkomma[i]; For i := 1 TO MaxNachkomma DO c.Nachkomma[i] := a.Nachkomma[i] + b.Nachkomma[i]; IF (a.Vorzeichen = Minus) AND (b.Vorzeichen = Minus) THEN c.Vorzeichen := Minus; IF (a.Vorzeichen = Plus ) AND (b.Vorzeichen = Plus ) THEN c.Vorzeichen := Plus ; END ELSE IF (a.Vorzeichen = Plus) AND (b.Vorzeichen = Minus) THEN BEGIN b.Vorzeichen := Plus; LongSub(a,b,c); END ELSE IF (a.Vorzeichen = Minus) AND (b.Vorzeichen = Plus) THEN BEGIN a.Vorzeichen := Plus; LongSub(b,a,c); END; END ELSE BEGIN Writeln(a.Vorkomma[Maxvorkomma]:10); Writeln(b.Vorkomma[Maxvorkomma]:10); Writeln('a oder b sind zu groß'); EXIT; END; LongKorrektur(c); LongAdd := TRUE; END; FUNCTION Einezahl ( z : LongInt) : STRING; Var s : STRING; b : Byte; ch : Char Absolute b; i : Byte; l : LongInt; BEGIN IF z < 0 THEN z := z * -1; l := Maximum DIV 10; s := Copy('00000000000000',1,Maxi); FOR i := 1 To Maxi DO BEGIN b := 48 + z DIV l; s[i] := ch; z := z - ((b - 48) * l); l := l DIV 10; END; ch := s[1]; { Korrektur, wenn in der ersten Stelle ein Überlauf ist } IF b > 57 THEN BEGIN b := b - 10; s[1] := ch; s := '1' + s; END; EineZahl := s; END; FUNCTION LongString ( c : TLangZahl): String; Var LangZahl : String; b : Byte Absolute Langzahl; i : Word; BEGIN WITH c DO BEGIN IF Vorzeichen = Plus THEN Langzahl := '+' ELSE Langzahl := '-'; For i := MaxVorkomma Downto 1 DO Langzahl := Langzahl + EineZahl(Vorkomma[i]); Langzahl := Langzahl + ','; For i := 1 TO MaxNachkomma DO Langzahl := Langzahl + EineZahl(Nachkomma[i]); END; WHILE b < 75 do Langzahl := ' ' + Langzahl; LongString := Langzahl; END; FUNCTION LongMul ( a : TLangZahl; b : TLangZahl; Var c : TLangZahl): BOOLEAN; Var Help1 : TLangzahl; Help2 : TLangzahl; i : Integer; j : Integer; Test1 : Boolean; Test2 : Boolean; l : LongInt; k : Integer; n : Extended; BEGIN LongMul := FALSE; Test1 := FALSE; Test2 := FALSE; For i := 1 TO MaxVorkomma DO BEGIN Help1.Vorkomma[i] := 0; Help2.Vorkomma[i] := 0; c.Vorkomma[i] := 0; IF a.Vorkomma[i] <> 0 THEN Test1 := TRUE; IF b.Vorkomma[i] <> 0 THEN Test2 := TRUE; END; For i := 1 TO MaxNachkomma DO BEGIN Help1.Nachkomma[i] := 0; Help2.Nachkomma[i] := 0; c.Nachkomma[i] := 0; IF a.Nachkomma[i] <> 0 THEN Test1 := TRUE; IF b.Nachkomma[i] <> 0 THEN Test2 := TRUE; END; { es soll ein Wert mit Null multipliziert werden und raus c ist schon Null } IF NOT Test1 AND NOT Test2 THEN EXIT; { Kommastellen sind hier MaxNachkommastellen * 5 * 2 } IF LongKorrektur(a) AND LongKorrektur(b) THEN BEGIN { für die Multiplikation werden insgesamt doppelt soviele Stellen } { an Speicher benötigt, wie berechnet werden können } { alle weiteren Stellen führen zu einem Überlauf } FOR i := MaxVorkomma DownTo 1 DO BEGIN FOR j := 1 to MaxVorkomma DO BEGIN k := i + j - 1; l := a.Vorkomma[j] * b.Vorkomma[i]; IF (k > MaxVorkomma) AND (l <> 0) THEN BEGIN { Ist das Ergebnis größer als die maximal darstellbare Zahl } { Fehlermeldung ausgeben und raus } Writeln('Multiplikation: Überlauf in den Vorkommastellen',#7); Exit; END ELSE BEGIN IF k <= MaxVorkomma THEN help1.Vorkomma[k] := Help1.Vorkomma[k] + l; END; END; END; { Die Nachkommastellen haben ihren Übertrag in den Vorkommastellen } { zuerst nur die Nachkommastellen, deren Übertrag in die Nachkom- } { mastellen paßt } FOR i := MaxNachkomma DOWNTO 1 DO BEGIN FOR j := 1 to MaxNachkomma DO BEGIN k := i + j; { Werte hinter der letzten Kommastelle werden ignoriert } { ein Auf- oder Abrunden findet nicht statt } { die letzten Kommastellen werden aber Falsch } IF k <= MaxNachkomma THEN BEGIN help1.Nachkomma[k] := Help1.Nachkomma[k] + a.Nachkomma[j] * b.Nachkomma[i]; END ELSE BEGIN { Werte der Nachkommastellen sammeln, die außerhalb des ansprechbaren } { Bereiches liegen ( Gegenstück zum Überlauf bei den Vorkommastellen } Help2.Nachkomma[k - MaxNachkomma] := Help2.Nachkomma[k - MaxNachkomma] + a.Nachkomma[j] * b.Nachkomma[i]; END; END; END; { Umrechnen des Überlaufes der Nachkommastellen auf die letzte Nachkommastelle } { wenn Maximum = 10 dann i = 1 bis 9 100 i = 1 bis 5 1000 i = 1 bis 4 10000 i = 1 bis 3 } l := 1; i := 0; IF Maximum = 10 THEN j := 9 ELSE IF Maximum = 100 THEN j := 4 ELSE IF Maximum = 1000 THEN j := 3 ELSE IF Maximum = 10000 THEN j := 2 ELSE j := 1; IF j > MaxNachkomma THEN j := MaxNachkomma; REPEAT i := i + 1; l := l * Maximum; Help1.Nachkomma[MaxNachkomma] := Help1.Nachkomma[MaxNachkomma] + Help2.Nachkomma[i] DIV l; UNTIL (i >= j) ; { Nachkommastellen mit Übertrag in Vorkommastellen } FOR i := MaxNachkomma DOWNTO 1 DO BEGIN FOR j := 1 TO MaxVorkomma DO BEGIN k := i - j + 1; IF k > 0 THEN BEGIN help1.Nachkomma[k] := help1.Nachkomma[k] + a.Vorkomma[j] * b.Nachkomma[i]; END ELSE BEGIN k := (k * -1) + 1; help1.Vorkomma[k] := help1.Vorkomma[k] + a.Vorkomma[j] * b.Nachkomma[i]; END; END; END; { Nachkommastellen mit den Vorkommastellen multiplizieren } FOR i := MaxNachkomma DOWNTO 1 DO BEGIN FOR j := MaxVorkomma DOWNTO 1 DO BEGIN k := j - i; IF k <= 0 THEN BEGIN k := (k * -1) + 1; IF k <= MaxNachkomma THEN help1.Nachkomma[k] := help1.Nachkomma[k] + a.Nachkomma[i] * b.Vorkomma[j]; END ELSE BEGIN help1.Vorkomma[k] := help1.Vorkomma[k] + a.Nachkomma[i] * b.Vorkomma[j]; END; END; END; { sofern eine Variabel einen Übertrag enthält, diesen an die } { nächste Variabel weiter geben } FOR i := MaxNachkomma DownTo 2 DO BEGIN IF help1.Nachkomma[i] > Maximum THEN BEGIN l := Help1.Nachkomma[i] DIV Maximum; Help1.Nachkomma[i - 1] := Help1.Nachkomma[i - 1] + l; Help1.Nachkomma[i ] := Help1.Nachkomma[i ] - l * Maximum; END; END; IF help1.Nachkomma[1] > Maximum THEN BEGIN l := Help1.Nachkomma[1] DIV Maximum; Help1.Vorkomma[1] := Help1.Vorkomma[1] + l; Help1.Nachkomma[1] := Help1.Nachkomma[1] - l * Maximum; END; FOR i := 1 TO MaxVorkomma - 1 DO BEGIN IF help1.Vorkomma[i] > Maximum THEN BEGIN l := Help1.Vorkomma[i] DIV Maximum; Help1.Vorkomma[i + 1] := Help1.Vorkomma[i + 1] + l; Help1.Vorkomma[i ] := Help1.Vorkomma[i ] - l * Maximum; END; END; c := Help1; END ELSE BEGIN Writeln('a oder b sind zu groß'); EXIT; END; IF ((a.Vorzeichen = plus ) AND (b.Vorzeichen = plus )) OR ((a.Vorzeichen = minus) AND (b.Vorzeichen = Minus)) THEN c.Vorzeichen := plus ELSE c.Vorzeichen := minus; LongKorrektur(c); LongMul := TRUE; END; FUNCTION LongDiv ( a : TLangZahl; b : TLangZahl; Var c : TLangZahl): BOOLEAN; Var Help1 : TLangzahl; Help2 : TLangzahl; Help3 : TLangzahl; Help4 : TLangzahl; i : Integer; j : LongInt; k : Integer; l : Integer; m : Integer; n : Integer; Test1 : Boolean; Test2 : Boolean; BEGIN LongKorrektur(a); LongKorrektur(b); Test1 := FALSE; Test2 := FALSE; Help1.Vorzeichen := plus; Help2.Vorzeichen := plus; Help3.Vorzeichen := plus; Help4.Vorzeichen := plus; c.Vorzeichen := plus; For i := 1 TO MaxVorkomma DO BEGIN Help1.Vorkomma[i] := 0; Help2.Vorkomma[i] := 0; Help3.Vorkomma[i] := 0; Help4.Vorkomma[i] := 0; c.Vorkomma[i] := 0; IF a.Vorkomma[i] <> 0 THEN Test1 := TRUE; IF b.Vorkomma[i] <> 0 THEN Test2 := TRUE; END; For i := 1 TO MaxNachkomma DO BEGIN Help1.Nachkomma[i] := 0; Help2.Nachkomma[i] := 0; Help3.Nachkomma[i] := 0; Help4.Nachkomma[i] := 0; c.Nachkomma[i] := 0; IF a.Nachkomma[i] <> 0 THEN Test1 := TRUE; IF b.Nachkomma[i] <> 0 THEN Test2 := TRUE; END; { es soll ein Wert durch Null dividiert werden und raus, geht nicht } IF NOT Test1 AND NOT Test2 THEN EXIT; { Kehrwert von b errechnen } { erste Stelle in b suchen, die <> 0 ist } l := MaxVorkomma; While (b.Vorkomma[l] = 0) DO l := l - 1; IF l = 0 THEN BEGIN l := 1; While (b.Nachkomma[l] = 0) DO l := l + 1; l := l - 1; Help1.Nachkomma[l] := Maximum; END ELSE BEGIN Help1.Vorkomma[l] := Maximum; END; m := l * 2; FOR i := l DOWNTO 1 DO BEGIN FOR j := 1 TO MaxVorkomma DO BEGIN Help2.Vorkomma[j] := 0; Help3.Vorkomma[j] := 0; END; FOR j := 1 TO MaxNachkomma DO BEGIN Help2.Nachkomma[j] := 0; Help3.Nachkomma[j] := 0; END; j := 0; REPEAT Help3 := Help2; j := j + 1; Help2.Vorzeichen := Plus; Help1.Vorzeichen := Plus; b.Vorzeichen := Plus; FOR k := MaxNachKomma DOWNTO 1 DO Help2.Nachkomma[k] := Help2.Nachkomma[k] + b.Nachkomma[k]; FOR k := 1 TO MaxVorkomma DO Help2.Vorkomma[k] := Help2.Vorkomma[k] + b.Vorkomma[k]; LongKorrektur(Help2); Until LongGreater(Help2,Help1) OR LongEqual(Help2,Help1); c.Vorkomma[i] := c.Vorkomma[i] + j - 1; LongKorrektur(c); LongSub(Help1,Help3,Help4); FOR k := MaxNachKomma DOWNTO 1 DO Help3.Nachkomma[k] := 0; FOR k := 1 TO MaxVorkomma DO Help3.Vorkomma[k] := 0; Help3.Vorkomma[1] := 10; LongMul(Help4,Help3,Help1); END; { Hier liegt ggfls. noch ein Rest in Help1 vor, der noch berechnet werden muß, } { er ist jedoch auf die Nachkommastellen zu verteilen } FOR k := MaxNachKomma DOWNTO 1 DO Help3.Nachkomma[k] := 0; FOR k := 1 TO MaxVorkomma DO Help3.Vorkomma[k] := 0; IF LongGreater(Help1,Help3) THEN BEGIN FOR i := 1 TO MaxNachkomma DO BEGIN FOR j := 1 TO MaxVorkomma DO BEGIN Help2.Vorkomma[j] := 0; Help3.Vorkomma[j] := 0; END; FOR j := 1 TO MaxNachkomma DO BEGIN Help2.Nachkomma[j] := 0; Help3.Nachkomma[j] := 0; END; j := 0; REPEAT Help3 := Help2; j := j + 1; Help2.Vorzeichen := Plus; Help1.Vorzeichen := Plus; b.Vorzeichen := Plus; FOR k := MaxNachKomma DOWNTO 1 DO Help2.Nachkomma[k] := Help2.Nachkomma[k] + b.Nachkomma[k]; FOR k := 1 TO MaxVorkomma DO Help2.Vorkomma[k] := Help2.Vorkomma[k] + b.Vorkomma[k]; LongKorrektur(Help2); Until LongGreater(Help2,Help1) OR LongEqual(Help2,Help1); c.Nachkomma[i] := c.Nachkomma[i] + j - 1; LongKorrektur(c); LongSub(Help1,Help3,Help4); FOR k := MaxNachKomma DOWNTO 1 DO Help3.Nachkomma[k] := 0; FOR k := 1 TO MaxVorkomma DO Help3.Vorkomma[k] := 0; Help3.Vorkomma[1] := 10; LongMul(Help4,Help3,Help1); END; END; { a mit dem Kehrwert von b multiplizieren } Help1 := c; LongMul(a,Help1,c); { Kommastellen korrigieren } m := m - 1; FOR i := 1 TO m DO BEGIN FOR k := MaxNachkomma - 1 DOWNTO 2 DO c.Nachkomma[k] := c.Nachkomma[k - 1]; END; FOR i := 1 TO m DO BEGIN n := m - i + 1; IF (n > 0) AND (n <= MaxVorkomma) AND (i > 0) AND (i <= MaxNachkomma) THEN c.Nachkomma[i] := c.Vorkomma[n]; END; FOR i := 1 TO m DO BEGIN FOR k := 1 TO MaxVorkomma - 1 DO c.Vorkomma[k] := c.Vorkomma[k + 1]; c.Vorkomma[MaxVorkomma] := 0; END; { stimmt das so? } IF ((a.Vorzeichen = plus ) AND (b.Vorzeichen = plus )) OR ((a.Vorzeichen = minus) AND (b.Vorzeichen = Minus)) THEN c.Vorzeichen := plus ELSE c.Vorzeichen := minus; LongDiv := TRUE; END; PROCEDURE Linie1 (Var f : Text); Var i : Integer; BEGIN FOR i := 1 TO (MaxVorkomma + MaxNachkomma + 4) + (MaxVorkomma DIV 3) + (MaxNachkomma DIV 3) DO Write(f,'-'); Writeln(f); END; PROCEDURE Linie2 (Var f : Text); Var i : Integer; BEGIN FOR i := 1 TO (MaxVorkomma + MaxNachkomma + 4) + (MaxVorkomma DIV 3) + (MaxNachkomma DIV 3) DO Write(f,'='); Writeln(f); Writeln(f); END; PROCEDURE Zahl (Var f : Text; c : TLangzahl; ch : Char); Var i : Integer; BEGIN Write(f,ch,' '); case c.Vorzeichen of Plus : Write(f,'+'); minus : Write(f,'-'); end; FOR i := MaxVorkomma DOWNTO 1 DO BEGIN Write(f,c.Vorkomma[i]); IF ((i + 2) MOD 3 = 0) AND (i > 3) AND (i <= MaxVorkomma) THEN Write(f,'.'); END; Write(f,','); FOR i := 1 TO MaxNachkomma DO BEGIN Write(f,c.Nachkomma[i]); IF ((i ) MOD 3 = 0) AND (i < MaxNachkomma) THEN Write(f,'.'); END; Writeln(f); END; Var a : TLangZahl; b : TLangZahl; c : TLangZahl; i : Word; f : Text; BEGIN Assign(f,'LONGRECH.TXT'); If FileExists('LONGRECH.TXT') then Append(f) else ReWrite(f); a.Vorzeichen := Plus; b.Vorzeichen := Plus; c.Vorzeichen := Plus; For i := 1 TO MaxVorkomma Do BEGIN a.Vorkomma[i] := 0; b.Vorkomma[i] := 0; c.Vorkomma[i] := 0; END; For i := 1 TO MaxNachkomma Do BEGIN a.Nachkomma[i] := 0; b.Nachkomma[i] := 0; c.Nachkomma[i] := 0; END; Randomize; { höchster Wert je Variabel = Maximum - 1} a.Vorzeichen := Plus ; {minus} b.Vorzeichen := Plus ; {plus} For i := 1 TO MaxVorkomma DIV 2 do a.Vorkomma[i] := Random(Maximum - 1); For i := 1 TO MaxNachkomma - 1 do a.Nachkomma[i] := Random(Maximum - 1); For i := 1 TO MaxVorkomma DIV 2 do b.Vorkomma[i] := Random(Maximum - 1); For i := 1 TO MaxNachkomma - 1 do b.Nachkomma[i] := Random(Maximum - 1); LongKorrektur(a); LongKorrektur(b); IF LongPlausi(a) AND LongPlausi(b) THEN BEGIN Writeln(' ',LongString(a)); Writeln(' + ',LongString(b)); Writeln(Replicate('-',79)); LongAdd(a,b,c); Writeln(' = ',LongString(c)); Writeln(Replicate('=',79)); Zahl(f,a,' '); Zahl(f,b,'+'); Linie1(f); Zahl(f,c,'='); Linie2(f); Writeln(' ',LongString(a)); Writeln(' - ',LongString(b)); Writeln(Replicate('-',79)); LongSub(a,b,c); Writeln(' = ',LongString(c)); Writeln(Replicate('=',79)); Zahl(f,a,' '); Zahl(f,b,'-'); Linie1(f); Zahl(f,c,'='); Linie2(f); Writeln(' ',LongString(a)); Writeln(' * ',LongString(b)); Writeln(Replicate('-',79)); LongMul(a,b,c); Writeln(' = ',LongString(c)); Writeln(Replicate('=',79)); Zahl(f,a,' '); Zahl(f,b,'*'); Linie1(f); Zahl(f,c,'='); Linie2(f); Writeln(' ',LongString(a)); Writeln(' / ',LongString(b)); Writeln(Replicate('-',79)); LongDiv(a,b,c); Writeln(' = ',LongString(c)); Writeln(Replicate('=',79)); Zahl(f,a,' '); Zahl(f,b,'/'); Linie1(f); Zahl(f,c,'='); Linie2(f); END ELSE BEGIN Writeln('irgend ein Wert in a oder b ist zu groß'); END; Close(f); WriteLn('Fertig'); Readln; END. BEGIN Abbruch := 0; { Zähler Abbruchschranke } Wurzelwert := Radikand / 2; { der wird die Wurzel } TestRadikand := Wurzelwert; { Testvariabel } TeilerRadikand := Radikand; { Variabel zum Annähern } REPEAT TeilerRadikand := TeilerRadikand / 2; TestRadikand := Wurzelwert; Potenzwert := 1; REPEAT TestRadikand := TestRadikand * Wurzelwert; Potenzwert := Potenzwert + 1; UNTIL (Potenzwert = Wurzelexponent) OR (TestRadikand >= Radikand); IF TestRadikand > Radikand THEN Wurzelwert := Wurzelwert - TeilerRadikand; IF TestRadikand < Radikand THEN Wurzelwert := Wurzelwert + TeilerRadikand; Abbruch := Abbruch + 1; UNTIL (TestRadikand > (Radikand - Genauigkeit)) AND (TestRadikand < (Radikand + Genauigkeit)) OR (TestRadikand = Radikand) OR (TeilerRadikand = 0) OR (Abbruch >= MaximalSchleifen); Wurzelziehen := WurzelWert; END; {.INFO} FUNCTION LongWur ( Radikand : TLangzahl; Wurzelexponent : Word; MaximalSchleifen : Integer; Var c : TLangZahl) : Boolean; {*------------------------------------------------------------------*} {¦ Berechnet die wurzelexponente Wurzel aus dem Radikand. ¦} {¦ Je kleiner der Wert von Genauigkeit, um so präziser wird das ¦} {¦ Ergebnis bestimmt. ¦} {*------------------------------------------------------------------*} {.INFO} VAR Abbruch : Integer; TestRadikand : TLangzahl; TeilerRadikand : TLangzahl; Wurzelwert : TLangzahl; PotenzWert : Word; Help1 : TLangzahl; Help2 : TLangzahl; i : Integer; BEGIN LongWur := FALSE; Abbruch := 0; { Zähler Abbruchschranke } Help1.Vorzeichen := Plus; Help2.Vorzeichen := Plus; FOR i := 1 TO MaxVorkomma DO BEGIN Help1.Vorkomma[i] := 0; Help2.Vorkomma[i] := 0; c.Vorkomma[i] := 0; TestRadikand.Vorkomma[i] := 0; TeilerRadikand.Vorkomma[i] := 0; Wurzelwert.Vorkomma[i] := 0; END; FOR i := 1 TO MaxNachkomma DO BEGIN Help1.Nachkomma[i] := 0; Help2.Nachkomma[i] := 0; c.Nachkomma[i] := 0; TestRadikand.Nachkomma[i] := 0; TeilerRadikand.Nachkomma[i] := 0; Wurzelwert.Nachkomma[i] := 0; END; Help1.Nachkomma[1] := 5; LongMul(Radikand,Help1,WurzelWert); (* Wurzelwert := Radikand / 2; { der wird die Wurzel }*) TestRadikand := Wurzelwert; { Testvariabel } TeilerRadikand := Radikand; { Variabel zum Annähern } REPEAT LongMul(TeilerRadikand,Help1,Help2); TeilerRadikand := Help2; { TeilerRadikand := TeilerRadikand / 2;} TestRadikand := Wurzelwert; Potenzwert := 1; REPEAT LongMul(TestRadikand,WurzelWert,Help2); { TestRadikand := TestRadikand * Wurzelwert;} TestRadikand := Help2; Potenzwert := Potenzwert + 1; UNTIL (Potenzwert = Wurzelexponent) OR LongGreater(TestRadikand,Radikand) OR LongEqual(TestRadikand,Radikand); {(TestRadikand >= Radikand);} IF LongGreater(TestRadikand,Radikand) THEN BEGIN LongSub(Wurzelwert,TeilerRadikand,Help2); Wurzelwert := Help2; END; IF LongLower(TestRadikand,Radikand) THEN BEGIN LongAdd(Wurzelwert,TeilerRadikand,Wurzelwert); Wurzelwert := Help2; END; Abbruch := Abbruch + 1; UNTIL (LongGreater(TestRadikand,Radikand) AND LongLower(TestRadikand,Radikand)) OR LongEqual(TestRadikand,Radikand) OR LongIsZero(TeilerRadikand) OR (Abbruch >= MaximalSchleifen); c := WurzelWert; LongWur := TRUE; END; Meine Kommentare von damals verstehe ich nicht mehr so unbedingt, aber vielleicht ist's ja ein Ansatz für die Ideenfindung zur Lösung des Problems. Ansonsten: et is wie et is, frage mich bitte niemand, was ich mir seinerzeit dabei gedacht habe oder warum ich das produziert habe ;-) Müsste mit Turbo-Pascal 4 entstanden sein. |
AW: Gauß-Verfahren - Matrix lösen
Wenn es nur:-D darum geht, schnelle Langzahlarithmetik einzusetzen, kannst Du auch meine
MPArith-Bibliothek verwenden (die ca 150 Mio Dezimalstellen sollten ja ausreichen). Eine Schwierigkeit bei Problemen wie Deinem ist halt, das es kein fertige Lösung gibt, man es selbst programmieren und sich erstmal einarbeiten muß. Aber wenn Du Deine Stringroutinen durch mp_xxx-Routinen ersetzt, sollte es möglich sein. |
AW: Gauß-Verfahren - Matrix lösen
Was kriegst denn raus, wenn du (bei Floats) die Probe machst, also z.B. so. Da kann doch nix nennenswertes rauskommen?
Delphi-Quellcode:
function TGauss.GetMaxInversError: Extended; // E = A x A^-1;
var I, J, K: integer; Value: Extended; begin Result := 0; SetLength(FTemp, Count, Count); try for I := 0 to Count - 1 do for J := 0 to Count - 1 do begin Value := 0; for K := 0 to Count - 1 do Value := Value + FA[I, K] * FI[K, J]; FTemp[I, J] := Value; end; for I := 0 to Count - 1 do for J := 0 to Count - 1 do begin if I = J then Value := 1 else Value := 0; Result := Max(Result, Abs(Value - FTemp[I, J])); end; finally SetLength(FTemp, 0); end; end; |
AW: Gauß-Verfahren - Matrix lösen
Mal ein wenig zurück zur Ursprungsfrage...
Das Verfahren hat der olle Gaus entwickelt, um Rundungsfehler zu minimieren. Wenn ich nun durch die Rechnungen gar keine Rundungsfehler habe, brauche ich die auch nicht zu minimieren und kann ganz geradeaus a) Die Dreiecksform berechnen b) Rückwärtseinsetzen c) fertig sein was das genaue Rechnen betrifft, wäre es doch ganz easy sich eine Klasse zu schreiben, die von Haus aus Natürliche Zahlen bis 2^256 unterstützt. Wird durch eine Operation eine größere Zahl erforderlich, holt sich diese Klasse einen weiteren 256-Bit-Integer dazu ... Die Klasse implementiert dann Addition Subtraktion und Multiplikation (alles relativ einfach). Eine weitere Klasse besorgt das Zusammenfassen von Zähler und Nenner und am Ende der Berechnung die Division. |
| Alle Zeitangaben in WEZ +1. Es ist jetzt 07:22 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz