Une calculatrice qui calcule sur des unions d’intervalles disjoints

• Prend en entrée une union d’intervalles disjoints et peut effectuer les quatre opérations, des appels de fonctions et même des puissances, avec calcul direct d’interval union arithmetic dans le navigateur
• L’intervalle résultat contient nécessairement la valeur obtenue si l’on évalue la même expression sur les réels avec des valeurs choisies dans l’union d’entrée, et la division par un intervalle contenant 0 peut aussi être traitée sous forme d’union disjointe
• Prise en charge des résultats en intervalles discontinus et des bornes infinies, par exemple 1 / [-2, 1] donne [-∞, -0.5] U [1, +∞] et tan([pi/3, 2*pi/3]) donne [-∞, -1.732] U [1.732, +∞]
• Prend en charge diverses notations et fonctions comme [a, b], [a, b] U [c, d], la syntaxe d’intervalles imbriqués, lo, hi, hull, log10, cos, min, max
• En mode précision totale, renvoie des intervalles qui englobent la valeur réelle grâce à un arrondi extérieur fondé sur IEEE 754 double précision, avec par exemple 0.1 + 0.2 affiché comme [0.29999999999999993, 0.3000000000000001]

---

Vue d’ensemble

• Il s’agit d’une calculatrice qui travaille sur des unions d’intervalles disjoints, avec prise en charge d’interval union arithmetic en plus des réels ordinaires
  • L’intervalle [a, b] désigne tous les nombres de a à b, et [a, b] U [c, d] représente l’union de plusieurs intervalles séparés
  • C’est une extension de l’arithmétique d’intervalles classique, qui permet aussi de calculer la division par un intervalle contenant 0 tout en conservant la fermeture
• Garantie de propriété d’inclusion
  • Si l’on choisit arbitrairement un réel dans chacune des unions d’entrée puis qu’on évalue la même expression sur les réels, le résultat est nécessairement contenu dans l’union de sortie
• Possibilité d’exprimer l’incertitude
  • Exemple donné : le résultat de 50 * (10 + [-1, 1]) est [450, 550]
• Prise en charge de calculs sur des expressions d’intervalles complexes
  • On peut saisir des expressions comme ( [5, 10] U [15, 16] ) / [10, 100] avec l’opérateur U
  • Exemple de résultat : [0.05, 1.6]
• Le résultat d’une opération peut être une union disjointe
  • 1 / [-2, 1] donne [-∞, -0.5] U [1, +∞]
  • tan([pi/3, 2*pi/3]) donne [-∞, -1.732] U [1.732, +∞]
• En mode précision totale, elle peut être utilisée comme une calculatrice classique tout en fournissant des intervalles qui englobent la valeur réelle, y compris les problèmes de précision en virgule flottante
  • Exemple : 0.1 + 0.2 donne [0.29999999999999993, 0.3000000000000001]

Syntaxe

• Prise en charge de la notation de base
  • Prise en charge de la notation d’intervalle [a, b]
  • Exemple : [0.5, 0.6]
• Prise en charge de la notation d’union
  • Prise en charge de la forme [a, b] U [c, d]
  • Exemple : [0, 1] U [5, 6]
• Prise en charge des quatre opérations et des puissances
  • Addition A + B exemple ➤ [90, 100] + [-2, 2] résultat [88, 102]
  • Soustraction A - B exemple ➤ [14, 16] - [8, 12] résultat [2, 8]
  • Multiplication A * B exemple ➤ [-5, 10] * [2, 4] résultat [-20, 40]
  • Division A / B exemple ➤ [2, 4] / [-1, 2] résultat [-∞, -2] U [1, +∞]
  • Puissance A ^ B exemple ➤ [2, 3] ^ [-2, 3] résultat [0.1111, 27]
• Prise en charge des fonctions et des constantes
  • Prise en charge des appels de fonction sous la forme function(...)
  • log10([1, 10000]) donne [0, 4]
  • Prise en charge de la saisie des noms de constantes
  • pi donne [3.1415926535897927, 3.1415926535897936]
• Possibilité de mélanger nombres et intervalles en entrée
  • On peut saisir un intervalle avec une syntaxe entre crochets comme [1, 2]
  • Un nombre comme 3.14 est interprété comme un intervalle étroit de largeur nulle [3.14, 3.14]
  • En mode précision totale, il existe des différences de détail à ce sujet
  • 1.55 + [-0.002, 0.002] donne [1.548, 1.552]
• Prise en charge de la syntaxe d’intervalles imbriqués
  • On peut saisir [0, [0, 100]] et obtenir [0, 100]
  • Même les nombres internes qui définissent les bornes d’un intervalle sont tous interprétés comme des intervalles
  • Dans un intervalle imbriqué, un intervalle placé en position de borne prend sa borne supérieure
  • Cette conception permet d’appliquer de l’arithmétique aux bornes elles-mêmes
  • [0, cos(2*pi)] donne [0, 1]

Fonctions prises en charge

• Prise en charge des constantes
  • inf, ∞, pi, e pris en charge
  • [-inf, 0] * [-inf, 0] donne [0, +∞]
• Prise en charge des fonctions d’extraction des bornes
  • lo(A) renvoie la borne inférieure
    • lo([1, 2]) donne [1, 1]
  • hi(A) renvoie la borne supérieure
    • hi([1, 2]) donne [2, 2]
• Prise en charge du calcul de l’enveloppe d’intervalle
  • hull(A) enveloppe une union dans un seul intervalle
  • hull([1, 2] U [99, 100]) donne [1, 100]
• Prise en charge des fonctions mathématiques de base
  • abs(A) exemple abs([-10, 5]) donne [0, 10]
  • sqrt(A) exemple sqrt([9, 49]) donne [3, 7]
  • sqinv(A) exemple sqinv([4, 64]) donne [-8, -2] U [2, 8]
• Prise en charge des fonctions logarithmiques et exponentielles
  • log(A) exemple log([0, 1]) donne [-∞, 0]
  • log2(A) exemple log2([64, 1024]) donne [6, 10]
  • log10(A) exemple log10([0.0001, 1]) donne [-4, 0]
  • exp(A) exemple exp([-∞, 0] U [1, 2]) donne [0, 1] U [2.718, 7.389]
• Prise en charge des fonctions trigonométriques et réciproques
  • cos(A) exemple cos([pi/3, pi]) donne [-1, 0.5]
  • sin(A) exemple sin([pi/6, 5*pi/6]) donne [0.5, 1]
  • tan(A) exemple tan([pi/3, 2*pi/3]) donne [-∞, -1.732] U [1.732, +∞]
  • acos(A) exemple acos([-1/2, 1/2]) donne [1.047, 2.094]
  • asin(A) exemple asin([0, 1]) donne [0, 1.571]
  • atan(A) exemple atan([-10, 2]) donne [-1.471, 1.107]
• Prise en charge des fonctions minimum et maximum
  • min(A, B) exemple min([1, 2], [0, 6]) donne [0, 2]
  • max(A, B) exemple max([0, 10], [5, 6]) donne [5, 10]

Mode précision totale

• Implémentation d’un arrondi extérieur sur des flottants double précision IEEE 754
  • Utilise le type number de JavaScript
  • L’intervalle résultat est garanti contenir la valeur réelle que donnerait le calcul de la même expression sur les réels avec une précision infinie
• Présence du cas 0.1 + 0.2
  • 0.3 ne peut pas être représenté exactement en flottant double précision
  • L’interval arithmetic effectue donc un calcul d’intervalle qui contient 0.3
• Comportement quand le mode précision totale est activé
  • Les nombres saisis par l’utilisateur sont interprétés comme le plus petit intervalle qui contient la valeur IEEE 754 la plus proche de leur représentation décimale saisie, avec des bornes de part et d’autre différentes de cette valeur
  • Les nombres en sortie sont affichés avec tous les chiffres décimaux disponibles
  • Utilise Number.toString()
• Comportement quand le mode précision totale est désactivé
  • Les nombres saisis par l’utilisateur sont interprétés comme un intervalle dégénéré dont les deux bornes sont égales à la valeur IEEE 754 la plus proche de la représentation décimale saisie
  • Les nombres en sortie sont affichés avec au maximum 4 décimales
  • Utilise Number.toPrecision()

Bugs

• Il est mentionné qu’il peut encore rester des bugs dans la calculatrice
• Un lien vers les issues GitHub est fourni pour signaler les problèmes

Open source

• Interval Calculator et son moteur de calcul not-so-float sont tous deux publiés en open source
• Inclut un lien de soutien GitHub Sponsors

Travaux à venir

• Le mode précision totale sera scindé en deux contrôles distincts
  • Interprétation des entrées
  • Précision d’affichage
• Ajout prévu de la variable ans
  • Variable stockant le résultat de la saisie précédente
• Ajout prévu d’un opérateur ou d’une fonction d’intersection
• Amélioration prévue de l’intuitivité de la priorité de l’opérateur U
• Prise en charge prévue de la saisie d’une union vide

[GN⁺]

Commentaires sur Hacker News

• En tant qu’auteur, je dirais que l’arrondi vers l’extérieur est surtout l’aspect le plus connu de l’arithmétique d’intervalles pour gérer les problèmes de précision, mais je trouve dommage que toute l’attention se concentre là-dessus. La propriété d’inclusion dont parlent les articles de recherche fonctionne à toutes les échelles, ce qui donne naturellement des résultats comme 50 * (10 + [-1, 1]) = [450, 550]. En ajoutant par-dessus une couche d’unions, on peut aussi traiter de vraies fonctions inverses comme celle du carré, et on le sent bien en essayant sqinv(64) plutôt que sqrt. En réalité, ce calculateur d’intervalles a été créé pour tester une implémentation d’arithmétique sur unions d’intervalles que je développais pour un autre projet, un tableur à mise à jour rétroactive. L’implémentation est not-so-float, et les projets liés sont bidicalc ainsi que la discussion HN
  • Je me demande en quoi l’arithmétique implémentée diffère du standard IEEE 1788. J’aimerais aussi savoir quel lien les deux articles cités ont avec ce standard. Pour résoudre les problèmes évoqués dans le billet, fallait-il repartir complètement de zéro, ou bien était-il possible de construire au-dessus du standard IEEE ?
  • C’est vraiment génial, et j’ai bien envie de continuer à jouer avec. Je me pose surtout deux questions. D’abord, à quel point serait-il difficile d’ajouter des fonctions multivaluées ? Par exemple, ce serait formidable de pouvoir obtenir, pour asin(1), l’ensemble complet [pi/2, pi/2] + n[2pi, 2pi] sans avoir besoin de Mathematica. Ensuite, la phrase expliquant l’interprétation des nombres saisis par l’utilisateur m’a semblé un peu ambiguë. Pour moi, les bornes de sortie du plus petit intervalle contenant la valeur d’entrée devraient être les deux nombres IEEE 754 les plus proches qui encadrent cette valeur, alors qu’avec la formulation actuelle j’ai l’impression de lire quelque chose comme IEEE754(input)+[-epsilon, epsilon], ce qui me semble différent
• C’est vraiment excellent. Le travail de Matt Keeter sur les surfaces implicites et l’optimisation à l’aide des mathématiques d’intervalles vaut aussi le détour. On peut voir des éléments liés dans cette présentation
• J’ai moi aussi un calculateur de tracé basé sur l’arithmétique d’intervalles, donc ça pourrait t’intéresser. Il y a formulagraph, qu’on peut essayer directement, et cet article explique son fonctionnement ainsi que le code associé
  • Ma première impression a été que cela ressemblait à GrafEq. Ça m’a rappelé l’ancien GrafEq
• Je me suis aussi amusé avec ça, au point d’écrire une petite bibliothèque Math::Interval en Raku. C’est raku-Math-Interval, une expérimentation construite à partir des classes Junction et Range intégrées à Raku, et c’était une expérience assez intéressante
• Très bien, merci de l’avoir partagé. Je pense que ce serait encore mieux si les intervalles indiquaient si la borne inférieure et la borne supérieure sont incluses ou non. La notation que je connais utilise des crochets tournés vers l’extérieur quand la valeur n’est pas incluse, et l’applique aussi toujours à l’infini. Par exemple, on écrirait ]-∞, -1] U [0.5, +∞[ et l’intervalle exclu au milieu serait ]-1, 0.5[. Si j’ai bien compris, min et max semblent aussi s’interpréter ainsi ici. Et une idée d’UI pratique serait de pouvoir cliquer ou toucher une formule dans la zone de résultat pour la recopier dans le champ de saisie
  • En lisant l’article lié, j’ai vu qu’il ne décrivait ici que des intervalles fermés. Une union d’intervalles y est définie comme un ensemble d’intervalles fermés et disjoints, et seules les bornes des intervalles extrêmes peuvent être ±∞
  • Il serait possible de prendre en charge une telle notation, mais le code deviendrait bien plus complexe. C’est pourquoi j’ai décidé assez tôt de ne pas la gérer. Cela dit, ça pourrait quand même faire une belle fonctionnalité supplémentaire
  • Cette partie m’a aussi un peu dérouté. La notation standard que je connaissais utilisait des parenthèses rondes, mais j’imagine que ce n’est peut-être pas très adapté dans un contexte ASCII
• Très impressionnant. Je n’ai pas complètement compris toutes les opérations, mais rien que ce que j’ai saisi m’a déjà beaucoup marqué. Je me dis qu’on aurait aimé rencontrer l’arithmétique sur les intervalles un peu plus tôt en cours. On voit déjà des idées proches avec les intervalles de confiance en statistiques de base ou le ± des équations du second degré, mais on ne peut jamais enchaîner les calculs sur le résultat comme sur une seule donnée ; il faut toujours traiter séparément les deux valeurs du ±, et ça m’a toujours semblé frustrant. Bien sûr, je comprends qu’un enseignant veuille vite passer aux applications et n’entre pas dans les détails. Mais j’aurais aimé au moins qu’on laisse entendre qu’une arithmétique générale est possible sur de tels objets. Ce qui est montré ici va beaucoup plus loin, mais j’ai l’impression d’y voir une validation de l’idée qu’un intervalle peut être considéré comme une donnée à part entière avec son propre comportement
• J’aurais aimé connaître l’arithmétique d’intervalles quand j’ai commencé à utiliser tick, la bibliothèque d’intervalles temporels en Clojure. Cette bibliothèque inclut aussi une implémentation de l’algèbre des intervalles d’Allen, et elle adopte également la notion d’ensemble d’intervalles discrets, utile pour des calculs métiers. Par exemple, cela convient bien à des tâches RH comme calculer l’ensemble des périodes de congés appartenant à une année donnée. Je ne connaissais au départ que les travaux d’Allen, et j’ai découvert presque par hasard les avantages de ce type d’ensembles. Le code est dans juxt/tick
• Je vois bien l’utilité de cet outil, mais personnellement je pense qu’un calculateur probabiliste me serait plus utile. Par exemple, un résultat comme 1 / [-1, 2] n’indique pas quelle valeur est la plus plausible, et même si on suppose une distribution uniforme en entrée, la sortie n’a clairement pas l’air de suivre une distribution uniforme
• J’ai aussi implémenté quelque chose de similaire récemment, mais sous l’angle de l’appartenance ensembliste. J’avais donc besoin d’une opération de complément pour faire une analyse booléenne complète sur l’appartenance à un intervalle. Ici, les intervalles sont tous des ensembles fermés, donc leur complément donne des intervalles ouverts, mais dans mon cas d’usage le fait d’inclure ou non les extrémités n’avait pas d’importance, donc je n’ai pas vraiment distingué intervalles ouverts et fermés. D’ailleurs, avec une arithmétique imprécise, on peut aussi considérer que le fait même qu’un ensemble soit ouvert ou fermé n’est pas toujours bien défini
• Étendre la logique aux unions d’intervalles paraît très élégant, mais je me demande quelle est la complexité. Si une seule opération peut produire deux intervalles, on a l’impression qu’après N opérations il peut y avoir, selon les cas, une croissance exponentielle. Du coup, j’ai peur que cela devienne irréaliste pour des usages courants comme l’interpretation abstraite, à moins d’introduire une approximation au-delà d’un certain nombre d’intervalles
  • C’est une remarque juste, et ce problème est bien connu du côté de l’interprétation abstraite. Comme tu le dis, on fixe en général une limite sur la taille des objets, puis on fusionne les intervalles quand cette limite est dépassée. Cela dit, au moins en interprétation abstraite, on utilise souvent aussi des domaines plus précis que les simples intervalles