Ein Rechner, der auf Vereinigungen disjunkter Intervalle rechnet

 (victorpoughon.github.io)
2 Punkte von GN⁺ 11 일 전 | 1 Kommentare | Auf WhatsApp teilen
  • Nimmt die Vereinigung disjunkter Intervalle als Eingabe und kann damit die vier Grundrechenarten, Funktionsaufrufe und Potenzen ausführen; interval union arithmetic lässt sich direkt im Browser berechnen
  • Das Ergebnisintervall enthält garantiert die Werte, die entstehen, wenn man aus den Eingabe-Vereinigungen Werte auswählt und denselben Ausdruck über den reellen Zahlen berechnet; auch Division durch ein Intervall, das 0 enthält, kann in Form getrennter Vereinigungen verarbeitet werden
  • Bei 1 / [-2, 1] ergibt sich [-∞, -0.5] U [1, +∞], und bei tan([pi/3, 2*pi/3]) ergibt sich [-∞, -1.732] U [1.732, +∞]; unterstützt also diskontinuierliche Ergebnisintervalle und Unendlichkeitsgrenzen
  • Unterstützt verschiedene Schreibweisen und Funktionen wie [a, b], [a, b] U [c, d], verschachtelte Intervallsyntax, lo, hi, hull, log10, cos, min, max
  • Im Vollpräzisionsmodus werden mittels IEEE-754-Doppelpräzision und nach außen gerundet Intervalle zurückgegeben, die den tatsächlichen Wert einschließen; charakteristisch ist etwa, dass 0.1 + 0.2 als [0.29999999999999993, 0.3000000000000001] angezeigt wird

Überblick

  • Ein Rechner für Vereinigungen disjunkter Intervalle, der neben gewöhnlichen reellen Zahlen auch eine Implementierung von interval union arithmetic unterstützt
    • Das Intervall [a, b] steht für alle Zahlen von a bis b, und [a, b] U [c, d] bedeutet die Vereinigung voneinander getrennter Intervalle
    • Es handelt sich um eine Erweiterung der gewöhnlichen Intervallarithmetik, bei der auch Division durch ein Intervall, das 0 enthält, unter Erhaltung der Abgeschlossenheit berechnet werden kann
  • Garantierte Enthaltungseigenschaft
    • Wählt man aus den Eingabe-Vereinigungen jeweils beliebige reelle Zahlen und berechnet denselben Ausdruck über den reellen Zahlen, ist das Ergebnis garantiert in der ausgegebenen Vereinigung enthalten
  • Kann Unsicherheit ausdrücken
    • Beispielergebnis für 50 * (10 + [-1, 1]) ist [450, 550]
  • Unterstützt komplexe Intervallausdrücke
    • Mit dem Operator U lassen sich Ausdrücke wie ( [5, 10] U [15, 16] ) / [10, 100] eingeben
    • Beispielergebnis: [0.05, 1.6]
  • Rechenergebnisse können selbst getrennte Vereinigungen sein
    • 1 / [-2, 1] ergibt [-∞, -0.5] U [1, +∞]
    • tan([pi/3, 2*pi/3]) ergibt [-∞, -1.732] U [1.732, +∞]
  • Im Vollpräzisionsmodus lässt sich der Rechner wie ein normaler Taschenrechner verwenden, liefert aber gleichzeitig Intervallergebnisse, die den tatsächlichen Wert einschließlich Gleitkomma-Präzisionsproblemen einschließen
    • Als Beispiel wird für 0.1 + 0.2 das Ergebnis [0.29999999999999993, 0.3000000000000001] gezeigt

Syntax

  • Grundlegende Schreibweise unterstützt
    • Intervallschreibweise [a, b]
    • Beispiel: [0.5, 0.6]
  • Vereinigungsschreibweise unterstützt
    • Form [a, b] U [c, d]
    • Beispiel: [0, 1] U [5, 6]
  • Vier Grundrechenarten und Potenzen unterstützt
    • Addition A + B, Beispiel ➤ [90, 100] + [-2, 2], Ergebnis [88, 102]
    • Subtraktion A - B, Beispiel ➤ [14, 16] - [8, 12], Ergebnis [2, 8]
    • Multiplikation A * B, Beispiel ➤ [-5, 10] * [2, 4], Ergebnis [-20, 40]
    • Division A / B, Beispiel ➤ [2, 4] / [-1, 2], Ergebnis [-∞, -2] U [1, +∞]
    • Potenz A ^ B, Beispiel ➤ [2, 3] ^ [-2, 3], Ergebnis [0.1111, 27]
  • Funktionen und Konstanten unterstützt
    • Funktionsaufrufe in der Form function(...)
    • log10([1, 10000]) ergibt [0, 4]
    • Eingabe von Konstantennamen wird unterstützt
    • pi ergibt [3.1415926535897927, 3.1415926535897936]
  • Gemischte Eingabe aus Zahlen und Intervallen möglich
    • Intervalle können mit der Klammernotation wie [1, 2] eingegeben werden
    • Zahlen wie 3.14 werden als schmales Intervall der Breite 0, also [3.14, 3.14], interpretiert
    • Im Vollpräzisionsmodus gibt es dabei Detailunterschiede
    • 1.55 + [-0.002, 0.002] ergibt [1.548, 1.552]
  • Verschachtelte Intervallsyntax unterstützt
    • [0, [0, 100]] kann eingegeben werden und ergibt [0, 100]
    • Dabei werden auch die inneren Zahlen, die die Intervallgrenzen definieren, selbst als Intervalle interpretiert
    • In verschachtelten Intervallen wird für ein Intervall an einer Grenzposition dessen Obergrenze verwendet
    • Durch dieses Design kann Arithmetik auch auf die Grenzen selbst angewendet werden
    • [0, cos(2*pi)] ergibt [0, 1]

Unterstützte Funktionen

  • Konstanten unterstützt
    • inf, ∞, pi, e
    • [-inf, 0] * [-inf, 0] ergibt [0, +∞]
  • Funktionen zum Extrahieren von Grenzen unterstützt
    • lo(A) gibt die Untergrenze zurück
      • lo([1, 2]) ergibt [1, 1]
    • hi(A) gibt die Obergrenze zurück
      • hi([1, 2]) ergibt [2, 2]
  • Berechnung der Intervallhülle unterstützt
    • hull(A) umschließt eine Vereinigung als einzelnes Intervall
    • hull([1, 2] U [99, 100]) ergibt [1, 100]
  • Grundlegende mathematische Funktionen unterstützt
    • abs(A), Beispiel abs([-10, 5]), Ergebnis [0, 10]
    • sqrt(A), Beispiel sqrt([9, 49]), Ergebnis [3, 7]
    • sqinv(A), Beispiel sqinv([4, 64]), Ergebnis [-8, -2] U [2, 8]
  • Logarithmus- und Exponentialfunktionen unterstützt
    • log(A), Beispiel log([0, 1]), Ergebnis [-∞, 0]
    • log2(A), Beispiel log2([64, 1024]), Ergebnis [6, 10]
    • log10(A), Beispiel log10([0.0001, 1]), Ergebnis [-4, 0]
    • exp(A), Beispiel exp([-∞, 0] U [1, 2]), Ergebnis [0, 1] U [2.718, 7.389]
  • Trigonometrische und arkustrigonometrische Funktionen unterstützt
    • cos(A), Beispiel cos([pi/3, pi]), Ergebnis [-1, 0.5]
    • sin(A), Beispiel sin([pi/6, 5*pi/6]), Ergebnis [0.5, 1]
    • tan(A), Beispiel tan([pi/3, 2*pi/3]), Ergebnis [-∞, -1.732] U [1.732, +∞]
    • acos(A), Beispiel acos([-1/2, 1/2]), Ergebnis [1.047, 2.094]
    • asin(A), Beispiel asin([0, 1]), Ergebnis [0, 1.571]
    • atan(A), Beispiel atan([-10, 2]), Ergebnis [-1.471, 1.107]
  • Funktionen für Minimum und Maximum unterstützt
    • min(A, B), Beispiel min([1, 2], [0, 6]), Ergebnis [0, 2]
    • max(A, B), Beispiel max([0, 10], [5, 6]), Ergebnis [5, 10]

Vollpräzisionsmodus

  • Implementiert nach außen gerichtetes Runden auf IEEE-754-Doppelpräzisions-Gleitkommazahlen
    • Verwendet den number-Typ von JavaScript
    • Garantiert, dass das Ergebnisintervall den tatsächlichen Wert enthält, der entsteht, wenn derselbe Ausdruck über den reellen Zahlen mit unendlicher Präzision berechnet wird
  • Enthält das Beispiel 0.1 + 0.2
    • 0.3 lässt sich in Doppelpräzisions-Gleitkommazahlen nicht exakt darstellen
    • Die Intervallarithmetik berechnet daher ein Intervall, das 0.3 enthält
  • Verhalten bei aktiviertem Vollpräzisionsmodus
    • Vom Nutzer eingegebene Zahlen werden als kleinstes Intervall interpretiert, das den dem eingegebenen Dezimalausdruck nächstliegenden IEEE-754-Wert enthält, wobei beide Grenzen nicht mit diesem Wert identisch sind
    • Ausgegebene Zahlen werden mit allen verfügbaren Dezimalstellen angezeigt
    • Verwendet Number.toString()
  • Verhalten bei deaktiviertem Vollpräzisionsmodus
    • Vom Nutzer eingegebene Zahlen werden als degeneriertes Intervall interpretiert, dessen beide Grenzen dem dem eingegebenen Dezimalausdruck nächstliegenden IEEE-754-Wert entsprechen
    • Ausgegebene Zahlen werden mit höchstens 4 Nachkommastellen angezeigt
    • Verwendet Number.toPrecision()

Bugs

  • Es wird erwähnt, dass im Rechner möglicherweise noch Bugs vorhanden sind
  • Für Fehlermeldungen wird ein GitHub-Issue-Link bereitgestellt

Open Source

  • Sowohl Interval Calculator als auch die Rechen-Engine not-so-float sind als Open Source veröffentlicht
  • Enthält einen Spendenlink zu GitHub Sponsors

Zukünftige Arbeiten

  • Der Vollpräzisionsmodus soll in zwei Steuerelemente aufgeteilt werden
    • Eingabeinterpretation
    • Anzeigepräzision
  • Die Variable ans soll hinzugefügt werden
    • Speicher für das Ergebnis der vorherigen Eingabe
  • Ein Schnittmengen-Operator oder eine entsprechende Funktion soll hinzugefügt werden
  • Die Intuitivität der Priorität des Operators U soll verbessert werden
  • Die Eingabe einer leeren Vereinigung soll unterstützt werden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 11 일 전
Hacker-News-Kommentare
  • Als Autor würde ich sagen: Rundung nach außen ist in der Intervallarithmetik zwar der bekannteste Umgang mit Präzisionsproblemen, aber ich finde es schade, wenn nur das Aufmerksamkeit bekommt. Die in Forschungsarbeiten beschriebene Enthaltenseigenschaft funktioniert auf allen Skalen, und deshalb ergeben sich Resultate wie 50 * (10 + [-1, 1]) = [450, 550] ganz natürlich. Wenn man darauf noch eine Union-Ebene setzt, kann man sogar Dinge wie die echte Umkehrfunktion der Quadratfunktion behandeln, und wenn man statt sqrt einmal sqinv(64) ausprobiert, merkt man schnell, wie das gemeint ist. Tatsächlich habe ich diesen Interval Calculator gebaut, um eine Implementierung von interval union arithmetic zu testen, an der ich für ein anderes Projekt gearbeitet habe, ein backwards updating spreadsheet. Die Implementierung ist not-so-float, verwandte Projekte sind bidicalc und die HN-Diskussion
    • Ich würde gern verstehen, wie sich die implementierte Arithmetik vom Standard IEEE 1788 unterscheidet. Mich würde auch interessieren, in welchem Verhältnis die beiden verlinkten Arbeiten zu diesem Standard stehen. Musste man, um die im Artikel erwähnten Probleme zu lösen, wirklich komplett neu anfangen, oder hätte man auch auf dem IEEE-Standard aufbauen können?
    • Wirklich großartig, ich werde definitiv noch weiter damit herumspielen. Zwei Dinge interessieren mich besonders: Erstens, wie schwer wäre es, mehrwertige Funktionen hinzuzufügen? Es wäre zum Beispiel sehr schön, bei asin(1) auch ohne Mathematica die vollständige Menge [pi/2, pi/2] + n[2pi, 2pi] zu bekommen. Zweitens fand ich die erläuternde Formulierung zur Interpretation von vom Benutzer eingegebenen Zahlen etwas verwirrend. So wie ich es verstehe, müssten die Ausgabegrenzwerte des kleinsten Intervalls, das den Eingabewert enthält, die beiden nächstliegenden IEEE-754-Zahlen sein, die den Eingabewert einschließen. In der jetzigen Formulierung liest es sich für mich eher wie IEEE754(input)+[-epsilon, epsilon], was eine andere Bedeutung hätte
  • Das ist wirklich gut. Auch Matt Keeters Arbeit zu impliziten Flächen und Optimierung mit Intervallmathematik ist in diesem Zusammenhang sehr spannend. In diesem Vortrag gibt es dazu etwas zu sehen
  • Ich habe auch einen Graphing Calculator auf Basis von interval arithmetic, das könnte also interessant sein. Man kann ihn direkt als formulagraph ausprobieren, und dieser Artikel erklärt die Funktionsweise und den zugehörigen Code
    • Mein erster Eindruck war, dass es GrafEq ähnelt. Das alte GrafEq fiel mir sofort wieder ein
  • Ich fand das Thema auch spannend und habe einmal eine einfache Math::Interval-Bibliothek in Raku geschrieben. Es ist raku-Math-Interval, ein Experiment auf Basis der eingebauten Junction- und Range-Klassen von Raku, und es war eine ziemlich interessante Erfahrung
  • Sehr schön, danke fürs Teilen. Ich fände es noch besser, wenn bei Intervallen angezeigt würde, ob die obere und untere Grenze enthalten sind. Die Schreibweise, die ich gewohnt bin, verwendet nach außen offene Klammern, wenn ein Wert nicht enthalten ist, und bei Unendlichkeiten immer genauso. Zum Beispiel ]-∞, -1] U [0.5, +∞[; das dazwischen ausgeschlossene Intervall wäre dann ]-1, 0.5[. So wie ich es verstanden habe, scheinen auch min und max in diesem Sinn interpretiert zu werden. Außerdem wäre eine UI-Idee praktisch: Wenn man auf eine Formel im Ergebnisbereich klickt oder tippt, könnte sie in das Eingabefeld kopiert werden
    • Ich habe die verlinkte Arbeit gelesen, und dort werden nur abgeschlossene Intervalle behandelt. Eine interval union wird als Menge abgeschlossener, voneinander getrennter Intervalle definiert, wobei nur die Grenzen der äußeren extremen Intervalle ±∞ sein dürfen
    • Man könnte eine solche Schreibweise unterstützen, aber der Code würde dadurch deutlich komplexer werden. Deshalb habe ich mich sehr früh dagegen entschieden. Trotzdem könnte das eine schöne Erweiterung sein
    • Ich war davon auch etwas verwirrt. Die Standardnotation, die ich kannte, waren runde Klammern, aber vielleicht passt das in ASCII-Umgebungen nicht so gut
  • Sehr cool. Ich habe nicht alle Operationen vollständig verstanden, aber schon das, was ich verstanden habe, fand ich beeindruckend. Ich hätte mir gewünscht, im Unterricht früher mit Arithmetik auf Intervallen in Berührung zu kommen. Ähnliche Konzepte tauchen ja schon in Konfidenzintervallen in der Grundstatistik oder beim ± in quadratischen Gleichungen auf, aber es hat mich immer etwas gestört, dass man mit dem Ergebnis nicht als einem einzigen Datenobjekt weiterrechnen konnte und stattdessen die beiden ±-Werte jedes Mal getrennt behandeln musste. Natürlich verstehe ich, warum Lehrkräfte schnell zu Anwendungen kommen wollen und deshalb nicht tiefer einsteigen. Trotzdem wäre zumindest ein Hinweis schön gewesen, dass auch für solche Objekte eine allgemeine Arithmetik möglich ist. Was hier gezeigt wird, geht zwar deutlich weiter, aber es fühlt sich für mich wie eine Bestätigung an, dass es sinnvoll ist, Intervalle als Daten mit eigenem Verhalten zu betrachten
  • Ich wünschte, ich hätte von interval arithmetic gewusst, als ich zum ersten Mal die Zeitintervall-Bibliothek tick in Clojure verwendet habe. Diese Bibliothek enthält auch eine Implementierung von Allen's Interval Algebra und übernimmt das für praktische Berechnungen nützliche Konzept diskreter Intervallmengen. Das passt zum Beispiel gut zu HR-Aufgaben wie der Berechnung von Urlaubsintervallmengen innerhalb eines Jahres. Ich kannte nur Allens Arbeit und habe die Vorteile solcher Mengen eher zufällig entdeckt. Der Code ist in juxt/tick
  • Der Nutzen dieses Werkzeugs ist für mich klar erkennbar, aber persönlich fände ich einen probabilistischen Rechner wahrscheinlich noch nützlicher. Bei einem Ergebnis wie 1 / [-1, 2] erfährt man zum Beispiel nicht, welche Werte wie plausibel sind, und selbst wenn man eine gleichverteilte Eingabe annimmt, scheint die Ausgabe offensichtlich nicht gleichverteilt zu sein
  • Ich habe vor Kurzem auch etwas Ähnliches implementiert, allerdings mit Blick auf Mengenmitgliedschaft. Deshalb brauchte ich für eine vollständige Boolean-Analyse von Intervallmitgliedschaft eine Komplementoperation. Da die Intervalle hier alle abgeschlossene Mengen sind, wird das Komplement zu einem offenen Intervall, aber für meinen Anwendungsfall war nicht wichtig, ob Endpunkte enthalten sind, deshalb habe ich offene und abgeschlossene Intervalle nicht eigens unterschieden. Außerdem würde ich sagen, dass bei ungenauer Arithmetik oft nicht einmal sauber definiert ist, ob eine Menge offen oder abgeschlossen ist
  • Die Erweiterung der Logik auf union of intervals wirkt sehr stark, aber ich frage mich nach der Komplexität. Wenn eine einzelne Operation zwei Intervalle erzeugen kann, scheint bei N Operationen im schlimmsten Fall ein exponentielles Wachstum möglich zu sein. Dann wäre das für typische Anwendungen wie abstract interpretation vielleicht unpraktisch, solange man ab einer gewissen Anzahl keine Approximation einführt
    • Das ist ein berechtigter Punkt, und in abstract interpretation ist dieses Problem gut bekannt. Wie du sagst, setzt man normalerweise eine Obergrenze für die Objektgröße und führt Intervalle zusammen, wenn diese Grenze überschritten wird. Zumindest in der abstract interpretation werden aber wohl auch oft präzisere Domänen als Intervalle verwendet