Der aktuelle Gleitkomma (ANSI C float, double) ermöglicht die Darstellung einer Approximation einer reellen Zahl.
Gibt es eine Möglichkeit, reelle Zahlen fehlerfrei darzustellen ?
Hier ist eine Idee, die alles andere als perfekt ist.
Zum Beispiel ist 1/3 0,33333333 ... (Basis 10) oder o.01010101 ... (Basis 2), aber auch 0,1 (Basis 3).
Ist es eine gute Idee, diese "Struktur" zu implementieren:
base, mantissa, exponent
1/3 könnte also 3 ^ -1 sein
{[11] = base 3, [1.0] mantissa, [-1] exponent}
Irgendwelche anderen Ideen?
Antworten:
Es hängt alles davon ab, was Sie tun möchten.
Was Sie beispielsweise zeigen, ist eine großartige Möglichkeit, rationale Zahlen darzustellen. Aber es kann immer noch nicht so etwas wie oder perfekt darstellen.eπ e
Tatsächlich haben viele Sprachen wie Haskell und Scheme die Unterstützung rationaler Zahlen eingebaut und diese in der Form gespeichert, wobei ganze Zahlen sind. a,beinb a , b
Der Hauptgrund dafür, dass diese nicht weit verbreitet sind, ist die Leistung. Gleitkommazahlen sind etwas ungenau, aber ihre Operationen sind in Hardware implementiert. Ihr vorgeschlagenes System ermöglicht eine höhere Präzision, erfordert jedoch mehrere Implementierungsschritte im Gegensatz zu einer einzelnen Operation, die in Hardware ausgeführt werden kann.
Es ist bekannt , dass einige reelle Zahlen unberechenbare, wie die sind Halte Zahlen . Im Gegensatz zu gibt es keinen Algorithmus, der seine Ziffern , bei dem wir die te Ziffer berechnen können, solange wir lange genug warten.nπ n
Wenn Sie echte Präzision für irrationale oder transzendentale Zahlen wünschen, müssen Sie wahrscheinlich ein System symbolischer Algebra verwenden und dann eine endgültige Antwort in symbolischer Form erhalten, die Sie einer beliebigen Anzahl von Ziffern annähern können. Aufgrund der oben beschriebenen Unentscheidbarkeitsprobleme ist dieser Ansatz jedoch notwendigerweise begrenzt. Es ist immer noch gut für Dinge wie die Annäherung von Integralen oder unendlichen Reihen.
quelle
Es gibt keine Möglichkeit, alle reellen Zahlen fehlerfrei darzustellen, wenn jede Zahl eine endliche Darstellung haben soll. Es gibt unzählige reelle Zahlen, aber nur unzählige endliche Zeichenfolgen von Einsen und Nullen, mit denen Sie sie darstellen können.
quelle
Es gibt einen ganzen Zweig der berechenbaren Mathematik, der sich mit exakter reeller Arithmetik befasst. Es wurden viele Datenstrukturen zur Darstellung exakter reeller Zahlen vorgeschlagen: Ziffernströme, Ströme affiner Kontraktionen, Cauchy-Sequenzen von Rationalen, Cauchy-Sequenzen von dyadischen Rationalen, Dedekind-Schnitte, Sequenzen von Shkrinking-Intervallen usw. Es gibt Implementierungen von exakten reellen Arithmetik-basierten zu diesen Ideen zum Beispiel:
Von diesen ist iRRAM das ausgereifteste und effizienteste. Marshall in einem experimentellen Projekt, während das dritte ein Studentenprojekt ist, aber auch das am leichtesten zugängliche. Es enthält eine sehr schöne Einführung, in der die Probleme bei der Berechnung der reellen Zahlen erläutert werden. Ich empfehle Ihnen dringend, sich diese anzuschauen.
Lassen Sie mich eine Bemerkung machen. Jemand wird einwenden, dass ein unendliches Objekt nicht von einem Computer dargestellt werden kann. In gewissem Sinne ist dies wahr, in einem anderen nicht. Wir müssen niemals eine ganze reelle Zahl darstellen, wir brauchen nur eine endliche Annäherungin jeder Phase der Berechnung. Wir brauchen also nur eine Darstellung, die ein Real bis zu einer bestimmten Genauigkeit darstellen kann. Sobald uns der Computerspeicher ausgeht, geht uns natürlich der Computerspeicher aus - aber das ist eine Einschränkung des Computers, nicht der Darstellung selbst. Diese Situation unterscheidet sich nicht von vielen anderen in der Programmierung. Beispielsweise verwenden Benutzer in Python Ganzzahlen und betrachten sie als "beliebig groß", obwohl sie natürlich die Größe des verfügbaren Speichers nicht überschreiten können. Manchmal ist Unendlichkeit eine nützliche Annäherung für eine sehr große endliche Zahl.
Außerdem höre ich oft die Behauptung, dass Computer nur mit berechenbaren reellen Zahlen umgehen können. Dabei fehlen zwei wichtige Punkte. Erstens haben Computer Zugriff auf Daten aus der Außenwelt, sodass wir auch (die nicht überprüfbare) Annahme treffen müssen, dass auch die Außenwelt berechenbar ist. Zweitens müssen wir unterscheiden, welche Realitäten ein Computer berechnen kann und welche Realitäten er darstellen kann. Wenn wir zum Beispiel Ziffernströme als Repräsentation von Real wählen, ist es durchaus möglich, ein nicht berechenbares Real darzustellen : Wenn uns jemand es geben würde, würden wir wissen, wie man es darstellt. Wenn wir uns jedoch dafür entscheiden, Real als Teile des Quellcodes darzustellen, die Ziffern berechnen, können wir offensichtlich keine nicht berechenbaren Real darstellen.
In jedem Fall wird dieses Thema am besten mit einer weiteren Lektüre behandelt.
quelle
Es gibt viele effektive Rational Number- Implementierungen, aber eine, die schon oft vorgeschlagen wurde und sogar mit einigen Irrationalen recht gut umgehen kann, ist Continued Fractions .
Zitat aus Continued Fractions von Darren C. Collins :
Zitat aus Mathworld - Periodic Continued Fractions
dh alle Wurzeln können als periodisch fortgesetzte Fraktionen ausgedrückt werden.
Es gibt auch einen exakten fortgesetzten Bruch für π, der mich überraschte, bis @AndrejBauer darauf hinwies, dass dies tatsächlich nicht der Fall ist.
quelle
In den Kommentaren gibt es eine Reihe von "exakten realen" Vorschlägen (z. B. fortgesetzte Brüche, lineare fraktionelle Transformationen usw.). Der typische Haken ist, dass Sie zwar Antworten auf eine Formel berechnen können, die Gleichheit jedoch häufig nicht entschieden werden kann.
Wenn Sie sich jedoch nur für algebraische Zahlen interessieren, haben Sie Glück: Die Theorie der realen geschlossenen Felder ist vollständig, o-minimal und entscheidbar. Dies wurde 1948 von Tarski bewiesen.
Aber da ist ein Fang. Sie möchten den Tarski-Algorithmus nicht verwenden, da er in der Komplexitätsklasse NONELEMENTARY enthalten ist, die so unpraktisch ist, wie es unpraktische Algorithmen nur können. Es gibt neuere Methoden, die die Komplexität auf DEXP reduzieren. Dies ist die beste, die wir derzeit kennen.
Beachten Sie, dass das Problem NP-schwer ist, da es SAT enthält. Es ist jedoch nicht bekannt (oder angenommen), dass es sich um einen NP handelt.
EDIT Ich werde versuchen, dies ein wenig mehr zu erklären.
Der Rahmen für das Verständnis all dessen ist ein Entscheidungsproblem, das als Satisfiability Modulo Theories, kurz SMT, bekannt ist. Grundsätzlich wollen wir SAT für eine Theorie lösen, die auf der klassischen Logik aufbaut.
Wir beginnen also mit der klassischen Logik erster Ordnung mit einem Gleichheitstest. Welche Funktionssymbole wir einschließen möchten und welche Axiome sie haben, bestimmt, ob die Theorie entscheidbar ist oder nicht.
Es gibt viele interessante Theorien, die im SMT-Framework zum Ausdruck kommen. Zum Beispiel gibt es Theorien über Datenstrukturen (z. B. Listen, Binärbäume usw.), mit denen die Richtigkeit von Programmen nachgewiesen werden kann, und die Theorie der euklidischen Geometrie. Für unseren Zweck betrachten wir jedoch Theorien verschiedener Arten von Zahlen.
Presburger Arithmetik ist die Theorie der natürlichen Zahlen mit Addition. Diese Theorie ist entscheidbar.
Peano-Arithmetik ist die Theorie der natürlichen Zahlen mit Addition und Multiplikation. Diese Theorie ist nicht entscheidbar, wie Gödel bekanntlich bewiesen hat.
Die Tarski-Arithmetik ist die Theorie der reellen Zahlen mit allen Feldoperationen (Addition, Subtraktion, Multiplikation und Division). Interessanterweise ist diese Theorie entscheidbar. Dies war zu dieser Zeit ein äußerst kontraintuitives Ergebnis. Sie könnten annehmen, dass es "schwieriger" ist, weil es eine "Obermenge" der natürlichen Zahlen ist, aber dies ist nicht der Fall; Vergleichen Sie beispielsweise die lineare Programmierung über die Rationalen mit der linearen Programmierung über die ganzen Zahlen.
Es mag nicht offensichtlich erscheinen, dass Zufriedenheit alles ist, was Sie brauchen, aber es ist. Wenn Sie beispielsweise testen möchten, ob die positive Quadratwurzel von 2 gleich der realen Kubikwurzel von 3 ist, können Sie dies als Erfüllbarkeitsproblem ausdrücken:
Alfred Tarski (1948), Eine Entscheidungsmethode für elementare Algebra und Geometrie .
quelle
Es ist möglich, eine sehr große Klasse von Zahlen, die als algebraische Zahlen bezeichnet werden, genau darzustellen , indem sie als Wurzeln von Polynomen behandelt werden.
quelle
quelle
Sie können nicht alle reellen Zahlen in einem Computer darstellen, aber Sie können viele darstellen. Sie könnten Brüche verwenden, die mehr Zahlen als Gleitkommazahlen darstellen. Sie können auch komplexere Dinge tun, z. B. die Darstellung von Zahlen als Wurzel eines Polynoms mit einer Annäherung, die unter der Newton-Methode gegen die Zahl konvergiert.
quelle
Es ist möglich, eine beliebige Zahl genau dort darzustellen, wo die Eingaben darstellbar sind, indem sie als eine Folge von Operationen gespeichert werden. So speichern Sie
1/3
beispielsweise1 divided by 3
, indem Sie durch Abbrechen von Operationen die nächste Operation vereinfachen, um eine genaue Antwort zu geben(1/3) * 3
. Dies kann auch Situationen behandeln, in denen Sie Irrationalitäten kennen, z. B.π
indem Sie diese in Ihren Berechnungen beibehalten.Es erfordert jedoch eine zunehmende Menge an Speicher für jede Zahl und - vorausgesetzt, Ihr Vereinfacher ist nicht perfekt - wird es wahrscheinlich eine immer größere Menge an Werten erfordern, an denen Sie viel arbeiten.
quelle