Hallo, ich brauche mal eure Hilfe.

Im Rahmen meiner Diplomarbeit habe ich ein Programm geschrieben und habe dabei folgendes Problem. Ein lineares Gleichungssystem mit ca. 500 Variablen soll gelöst werden. Dazu benutze ich wen es interressiert das Austauschverfahren nach Bialy.
Leider bekomme ich nach ungefähr 100 Rechenschritten einen Fehler in mein System, weil die Zeichenlänge in Delphi bei Gleitkommazahlen begrenzt ist. Dieser Fehler setzt sich fort und verfälscht mein Ergebnis erheblich.

Meiner Meinung nach ist die einzige Lösung mit Strings zu rechnen. Zwar sind die Rechenoperationen dann langsamer, aber dafür habe ich dann die Genauigkeit, die ich brauche.

Mich würde interessieren, wie ich Rechenoperationen wie Addition, Multiplikation und Division mit Strings durchführen kann.

Für euer Hilfe wäre ich euch sehr dankbar.

Naja, man muss ja nicht unbedingt Srings nehmen. Arrays tun es auch, und man hat da nicht die Probleme mit den nicht darstellbaren Steuerzeichen. Ich glaube, hier geistert irgendwo eine Unit rum, die große Integer verwalten kann. Etwas entsprechendes sollte es auch für Real-Typen geben.

Zum Verfahren: Ich kenne das nicht, aber wenn es schon nach 100 Rechenschritten signifikante Rundungsfehler gibt, dann sollte man evtl. auch an der Ursache danach suchen.
Neigt dein Problem generell dazu, für Rundungsfehler anfällig zu sein? Einige Systeme sind so bösartig, dass sie sich zwar theoretisch exakt lösen lassen, aber derart fies sind, dass Rundungsfehler die praktische Berechnung fast unmöglich machen. (Bestimmte Matrizen (Hilbermatrix?) z.B. lassen sich nicht wirklich invertieren, und das schon bei einer Größe von 20x20).
Ist das verwendete Verfahren denn numerisch einigermaßen stabil?

Verwendest du bisher Double (64 Bit, 15 bis 16 Stellen) oder Extended (80 Bit, 19 bis 20 Stellen) als Datentyp?

Ich verwende derzeit extended als Datantyp.

Ich habe mich auch bewußt für das Austaushverfahren entschieden, weil es im Gegensatz zum Gauss, genauer rechnet.

Man kann ein Gleichungssystem auch iterativ lösen (Gauss-Seidel, SOR, ..., da gibt's noch ein halbes Duzend weitere Verfahren), wobei du so lange iterierst bist die gewünschte Genauigkeit erreicht ist. Direkte Verfahren wie Gauss-Seidel sind bei grösseren Systemen nicht zu empfehlen, da du keine Kontrolle über die Genauigkeit hast.

Falls du keine Verluste haben willst würde ich mit Zahlen aus Q rechnen. Das heisst du speicherst dir jeweils Zähler und Nenner - z.B. als int64. Das ist mathematischer eleganter als die vorgeschlagene Methode mit den Strings; du bist nämlich unabhängig von einem Zahlensystem. Deswegen kriegst du auch keine Probleme mit periodischen Brüchen (z.B. 0.33333). Bei Strings ist das ein Problem.

Also ich würde das mit BCD-Zahlen machen, das müsste der Prozessor sogar unterstützen (mit asm).
Ansonsten kannst dus ja auch mit Strings machen, jedes Nibble eine Ziffer. Wenn das zu aufwändig ist halt jedes Byte eine Ziffer.
Damit solltest du dann genauso rechnen können wie mans in der Grundschule lernt (schriftliches addieren/subtrahieren/multiplizieren/dividieren).

Oder du emulierst quasi eine ALU, aber ob sich das rentiert weiß ich auch nicht.

Um das nochmals zu verdeutlichen...

Die Strings werden die Genauigkeit erhöhen aber dir nicht alle Steine aus dem Weg räumen. Wenn du den falschen Algorithmus wählst bringt es nicht sehr viel, mit einer erhöhten Genauigkeit zu rechnen (ausser du rechnest mit exakter Genauigkeit). Wenn der Fehler in deinem Algorithmus linear mit den Anzahl Schritten wächst, dann hat das Endresultat einen halb so kleinen Fehler, wenn die Genauigkeit verdoppelt wird. Die Fehlerfortpflanzung kann aber schon mal nicht linear sein; dann musst du unter Umständen sehr viel mehr rechnen, um mit dem "falschen" Algorithmus ein gutes Resultat zu kriegen.
Bei den Strings musst du nämlich auch runden; da der Dezimalbruch (wie schon oben beschrieben) bei einer Division schon mal periodisch werden kann.

Bei Gauss-Elimination kommt vielleicht schon mal folgende Rechensequenz vor:

Je höher die Genauigkeit, desto grösser die Katastrophe. Auch wenn man statt mit 0 zu vergleichen einen Toleranzbereich einbaut, kann es zu einer ähnlichen Katastrophe kommen (geht halt unter Umständen länger bis es passiert).

Tip: Wenn du mit Zahlen aus Q rechnest (siehe oben) kannst du besser schlafen, da das ganze dann garantiert funktioniert (vor allem für eine Diplomarbeit...).

Das ist ja das schöne an Strings, man kann sie (fast) beliebig lang machen.
Für periodische Sachen kann man ja nach z.B. 2000 Stellen abbrechen. Was ist schon ein kByte-String?

SnuffMaster23 hat folgendes geschrieben:

Das ist ja das schöne an Strings, man kann sie (fast) beliebig lang machen. Für periodische Sachen kann man ja nach z.B. 2000 Stellen abbrechen. Was ist schon ein kByte-String?

* Die obere Rechnung geht auch bei 2000 Stellen noch schief.
* Bei 2000 Stellen benötigt eine simple Multiplikation zwischen zwei Zahlen rund 4 Millionen Grundoperationen.
* Bei der Lösung des beschriebenen Problems bräuchtest du 500*500*200 = 500 mb RAM

Bei der Grösse des beschriebenen Gleichungssystems sollte man schon etwas auf Effizienz achten, wenn man nicht Tage aufs Resultat warten will.

Rechnet man hingegenen mit rationalen Zahlen (Zahlen aus Q),
* braucht eine Zahl so viel Speicher wie 2 Integers,
* besteht eine Multiplikation/Division aus 2 Integer-Multiplikationen (abgesehen vom Kürzen, wenn man das konsequent überall machen will),
* hat man ein garantiert exaktes Ergebnis.

Von BCD würde ich auf jeden Fall die finger lassen. diese werden intern auch über die FPU also mit gleicher Wahrscheinlichkeit wie die extendeds gerechnet. Ferner habe ich das in der Zeit, in der ich mich mit ähnlichem beschäftige noch nicht gesehen (ich nehme an floattostr wird wohl einen Grund haben, warum es nicht einfach die asm-BCD convert Befehle benutzt). Außerdem geht das glaube ich nur über asm, was der Autor offenbar nicht kennt ich ihm aber ans Herz legen würde und zusätzlich ist der Witz an BCD doch nur sich die Umwandlung von Binär nach Dezimal zu ersparen, das ist aber nicht sein Problem.

Falls du selber eine Bigint schreiben möchtest, dann schau dir die Befehle adc, sbb, mul, div an und falls du asm nicht wirklich verwenden willst dann mach es halt



evt. funktionieren die beiden carry Befehle nur mit word ptr. übertrag ist Variable.

Hiermit hättest du zumindest die Hardwareunterstützung und es geht um einiges schneller.

Zitat:

* Bei der Lösung des beschriebenen Problems bräuchtest du 500*500*200 = 500 mb RAM

Das Thema ist ja recht interessant...wollte nur mal auf einen kleinen Schussligkeitsfehler hinweissen.

500 * 500 = 250.000
250.000 * 200 = 50.000.000

also dann nur noch ca. 50 MB

Naja, auch falsch: 500 * 500 * 1000 = 250 MB
Ich meine ein Nibble reicht ja für eine Ziffer. Also 2000 Stellen = 1000 Byte.
Man kann das ja auch Hexadezimal auffassen, dann wird nichts verschwendet und der Wertebereich wird erheblich größer.

Aber braucht trotzdem noch zu viel Speicher...

Platon hat folgendes geschrieben:

Das Thema ist ja recht interessant...wollte nur mal auf einen kleinen Schussligkeitsfehler hinweissen.

Schussligkeitsfehler? Ja ich habe 200 statt 2000 geschrieben. Es sind tatsächlich sage und schreibe 500 mb bzw. wenn du's geschickt programmierst 250.
Wie auch immer: Wegen der extrem langen Berechnungszeit macht's so oder so keinen Sinn.

Könnte man das ganze nicht mit einem Typ bestehend aus 2 dynamischen Arrays of Byte und einem Boolean machen? Ich würde in dem einen dynamischen Array alle Ziffern vor dem Komma und in dem anderen alle nach dem Komma der Reihe nach reinschreiben. Der Booleanwert würde angeben, ob das ganze ein Vorzeichen hat. Dann betrachtet man jedes Byte als Ziffer einer Zahl zur Basis 256 und schreibt Funktionen die das ganze wie in der Grundschule schriftlich addieren, subtrahieren, multiplizieren und dividieren.
Der Vorteil gegenüber Strings wäre, dass es sich sicherlich leichter rechnen lässt, der Nachteil, dass man auch eine Funktion bräuchte, die das Array in einen String umwandelt, der dann auch noch die Zahl im Zehnersystem wiedergeben soll.
In einer Zahl die ein Kilobyte großmwäre, könnte man, wenn man 511 Byte Vorkommaziffern und 512 Byte Nachkommaziffern annimmt, Zahlen bis zu 4.079644068·10e1230 mit einer Genauigkeit von 9.574977460·10e-1234 abspeichern. Das solle mehr als genug sein.

Das Komma kann dann aber nicht überall sein. Nur alle 8 Bits wäre das möglich. Deine Lösung ist mehr oder weniger eine selbstprogrammierte Fliesskommazahl.
Wie ich aber schon gesagt habe reicht dann zwar die Genauigkeit aber du rechnest viel zu viel dafür.

Ich wiederhole und fasse zusammen:

• Array/Strings: Wer es schafft mit Arrays/Strings ein allgemeines Gleichungssystem wie oben beschrieben auf 100 Stellen genau mit einem direkten Verfahren wie Gauss-Elimination zu lösen und die Berechnungszeit weniger als 1h beträgt kriegt nen Preis von mir.
  
• Rationale Zahlen: Exaktes Ergebnis, aber immer noch recht langsam.
  
• Geeignete Methoden mit Extended: Du hast dein Ergebnis auf über 15 Stellen nach dem Komma in weniger als einer Sekunde. Die QR-Zerlegung mittels Householder-Matrizen müsste genügend genaue Resultate liefern. Oder halt eben Gauss-Seidel und co. Gauss-Seidel selbst konvergiert zwar schlecht nach einer gewissen Zeit.

delfiphan hat folgendes geschrieben:

Deine Lösung ist mehr oder weniger eine selbstprogrammierte Fliesskommazahl.

Falsch, das wäre eine Festkommazahl (mit variabler Größe).



@Senex: Wieso sollte man mit einem String weniger leicht rechnen können wie mit einem Array?
Ein String ist ein dynamisches Array, bzw. genauso zu behandeln. Du sparst dir halt SetSize .
Mit String meinte ich (und die anderen wohl auch) nicht die Stringdarstellung einer Zahl.

Die Idee ganze Bytes als Ziffern aufzufassen find ich genial, man könnte aber gleich 4 Bytes nehmen, die sind genauso schnell zu verarbeiten bzw. insgesamt in 1/4 der Zeit.