Une app de calculatrice ? Tout le monde peut en faire une, non ?

> « Une app de calculatrice ? Tout le monde peut en faire une » → en réalité, non

• Une calculatrice doit afficher correctement le résultat d’expressions mathématiques, et c’est bien plus difficile qu’il n’y paraît
• Sur la calculatrice d’iOS, (10^100) + 1 − (10^100) est calculé à tort comme 0
• Mais Android affiche correctement 1, et la manière dont cela a été rendu possible est vraiment incroyable

Google et Hans-J. Boehm

• Google a recruté le célèbre programmeur Hans-J. Boehm
• Boehm est l’expert qui a défini la sémantique des variables partagées en C++
• Mais la mission qui lui a été confiée était, contre toute attente, le développement d’une app de calculatrice

Le problème des nombres à virgule flottante

• Les nombres à virgule flottante ne peuvent pas représenter exactement des valeurs comme 0.3 ou 10^100
• Autrement dit, une calculatrice fondée sur les flottants n’est pas fiable
• Une autre approche est nécessaire pour obtenir des calculs exacts

La solution avec les Bignum

• Le problème des calculs entiers peut être résolu en utilisant des Bignum (entiers de précision arbitraire)
• Un Bignum est un type entier qui s’étend dynamiquement en fonction de la mémoire disponible
• Le problème de (10^100) + 1 - (10^100) est résolu si l’on utilise des Bignum
• Mais cela ne règle pas les opérations sur les fractions

Fractions et nombres algébriques

• Les fractions (des valeurs comme 3/4) peuvent être gérées en stockant numérateur et dénominateur avec des Bignum
• En revanche, les irrationnels comme π ou √2 ne peuvent pas être représentés ainsi
• Boehm a tenté une représentation fondée sur les polynômes
  • Par exemple, √2 peut être représenté par l’équation x² - 2 = 0
  • Mais π ne peut pas non plus être représenté de cette manière

Nombres réels constructifs (Constructive Real Numbers)

• Boehm a exploré le concept de « Recursive Real Arithmetic (RRA) »
• L’idée consiste à calculer une valeur dans la précision demandée par l’utilisateur
• Par exemple, si l’on demande π avec une erreur de 0.01, le système renvoie 3.14
• Mais cette approche complique les comparaisons exactes

Le problème de la représentation exacte de zéro

• Avec l’approche RRA, 1 - 1 pourrait être représenté non pas par 0, mais par 0.0000000001
• Cela pose un problème du point de vue de l’expérience utilisateur (UX)
• Boehm a commencé à chercher une solution en collaboration avec d’autres chercheurs

L’algorithme de Richardson-Fitch

• En 1994, Dan Richardson et John Fitch ont résolu le problème de la comparaison de nombres dans certaines opérations
• Mais cet algorithme est tellement lent qu’il est inutilisable en pratique
• Par exemple, déterminer que 1 ≠ 1 - e^(-e^1000) exige plus d’opérations qu’il n’y a d’atomes dans l’univers

Combiner RRA et arithmétique rationnelle

• Boehm a alors eu l’idée de combiner les avantages de RRA et de l’arithmétique rationnelle
• Pour les opérations simples (par ex. 6 × 9 ou 8 / 3), on utilise l’arithmétique rationnelle
• On n’utilise RRA que lorsqu’un irrationnel intervient
• Au final, les nombres sont représentés sous la forme rationnel × réel

Représentation symbolique (Symbolic Representation)

• Les nombres spéciaux comme π ou √2 utilisent une représentation symbolique plutôt que RRA
• Par exemple, π est stocké comme le symbole « π » et converti en nombre seulement si nécessaire
• Cette représentation symbolique est utilisée non seulement pour les quatre opérations, mais aussi pour les fonctions trigonométriques (sin, cos, tan), les logarithmes et les fonctions exponentielles

La solution finale

• Tous les nombres sont stockés sous la forme rationnel × réel (représentation symbolique ou RRA)
• Quand c’est possible, l’arithmétique rationnelle est utilisée pour préserver l’exactitude
• La représentation symbolique est exploitée au maximum afin de minimiser les opérations RRA
• Au final, un système de calculatrice parfait, équilibrant vitesse et précision, a été mis au point

Conclusion

• La calculatrice Android créée par Boehm et son équipe n’est pas un programme banal
• Elle fournit des résultats exacts tout en s’appuyant sur des algorithmes rapides et efficaces
• Ce n’est pas « juste une app de calculatrice », mais un système mathématiquement sophistiqué

> « La prochaine fois que vous utiliserez la calculatrice Android, pensez à tous les efforts qu’elle renferme ! »

[street62]

Petite digression, mais c’est intéressant que l’IA neo l’ait traduit par « c’est le genre de truc que n’importe qui peut faire », avec ce ton un peu relâché. L’original était « Anyone could make that », donc il n’y avait pas vraiment cette nuance taquine, haha, mais ça colle parfaitement.

[gurugio]

Quand j’étais étudiant en licence, il y avait un cours où l’on fabriquait à la main une carte 8086 en la soudant, puis où l’on connectait un pavé numérique et un écran LCD texte, avant d’aller jusqu’à créer une calculatrice (qui ne faisait que les quatre opérations) en assembleur 8086.
J’ai réussi à faire fonctionner la carte et à connecter le clavier et l’écran LCD, mais je n’ai pas réussi à faire la calculatrice.
À l’époque, je pensais ne pas avoir de talent pour le logiciel, alors j’ai trouvé un emploi comme ingénieur hardware, mais finalement je travaille aujourd’hui dans le développement logiciel.
La calculatrice, c’était vraiment difficile.

[yunsub2]

« geojana » → c’est bien « geojana ». 😃

[carnoxen]

Une app de calculatrice ? Tout le monde peut en faire une, non ?

Bon courage pour gérer les nombres à virgule flottante ? mdr

[tribela]

Quand on parle d’application de calculatrice, moi ça me fait penser à la calculatrice par défaut de Windows. Si on calcule 2+2*2, on obtient 8 et non 6. J’imagine que c’est fait exprès, mais je ne comprends pas du tout pourquoi. Je me souviens qu’autrefois, en calculant la quantité d’alcool dans un cocktail, j’avais obtenu une quantité d’alcool supérieure au volume total de la boisson, ce qui m’avait bien déconcerté.

[khrad]

Une appli de calculatrice ? Tout le monde peut en créer une, non ?

C’est le fonctionnement classique d’une calculatrice électronique ordinaire, où l’expression précédente est calculée immédiatement à chaque fois qu’on appuie sur un opérateur ; vous n’avez utilisé que des calculatrices scientifiques ?

[ned0909]

Je compatis totalement. Je me suis lancé dans une calculatrice en me disant que c’était bien parce qu’il n’y avait pas de serveur, puis j’en ai bavé à corriger toutes les erreurs de calcul et les bugs qui n’arrêtaient pas de surgir.

[ganadist]

Aperçu de l’implémentation dans le code source

Explication de la logique des opérations de calcul dans le code source

Code de traitement des entiers

Code de traitement des nombres réels

[aer0700]

« Une appli de calculatrice ? N’importe qui peut en faire une, non ? » → En fait, non
J’ai l’impression qu’on peut appliquer ça à une infinité de cas, lol

« Python ? C’est super facile, non ? » → En fait, non

[tsboard]

J’ai eu exactement la même pensée en regardant. hahaha

« JavaScript ? C’est carrément du gâteau » → En fait, pas du tout

[joyfui]

« (10^100)+1−(10^100) »
Oh, incroyable, la calculatrice de l’iPhone affiche 0, celle d’Android affiche 1.
Mais quand on cherche sur Google, le résultat affiché est 0...

[GN⁺]

Commentaire Hacker News

• Histoire intéressante. Une manière plus puissante de représenter les nombres consiste à utiliser les fractions continues. Les fractions continues permettent de représenter efficacement les nombres réels et rationnels
  • Fait amusant : selon un manuel de mathématiques pas si ancien, il était considéré comme probable qu'il n'existe pas d'algorithmes d'addition/multiplication pour les fractions continues. Pourtant, en 1972, Bill Gosper a démontré que les fractions continues conviennent parfaitement à l'arithmétique
  • Je travaille sur une bibliothèque Python appelée reals. Elle est conçue pour remplacer les types Decimal ou Fraction. Elle manipule les fractions continues en utilisant les techniques de Bill Gosper
• C'est dommage que le lien ait été raccourci au point de ne plus être cliquable. Voici le vrai lien vers l'article
• J'ai éclaté de rire en lisant le titre. IEEE 754 est le pire, mais reste meilleur que tout le reste. En voyant les exemples, j'ai pensé qu'il s'agirait de Kahan summation ou d'un système complet d'algèbre informatique. Je n'avais jamais entendu parler de la Recursive Real Arithmetic
  • J'y ai gagné un aperçu sur l'un des premiers héros du C++. Cela rappelle à quel point des choses qui paraissent simples peuvent être profondes
• Le tarif du métro de NYC est de 2,90 $. Quand j'ai utilisé PCalc sur iOS pour calculer la valeur restante de ma MetroCard, j'ai obtenu -8.881784197E-16 au lieu de 0. Cela n'arrive pas avec la calculatrice d'Apple
  • J'ai contacté le développeur, qui m'a répondu qu'Apple utilise sa propre bibliothèque mathématique et qu'il faudrait en trouver une autre pour la remplacer
• Presque personne n'a créé une application de calculatrice complète. Je parle d'une vraie calculatrice complète, comme la TI-89
  • J'utilise un émulateur de TI-89 sur Android. Il n'a même pas la moitié des fonctionnalités de certaines applications Android et ne fonctionne pas très bien
• Le principal inconvénient du passage à la RRA n'est pas seulement l'expérience utilisateur. Quand le résultat vaut 0.0000000..., la calculatrice ne peut pas déterminer si elle est capable de calculer l'inverse de ce nombre
  • Par exemple, 1/(atan(1/5)-atan(1/239)-pi/4) affiche « impossible à calculer ». Même en essayant 1/(atan(1/5)-atan(1/239)-pi/4+10^(-100000)), cela affiche toujours « impossible à calculer »
• Presque aucun nombre ne peut être représenté en virgule flottante IEEE. La probabilité qu'un nombre aléatoire soit théoriquement indescriptible est peut-être d'environ 100 %
  • Certains problèmes peuvent être évités en utilisant des bignums. La crise existentielle passagère est dissipée
• Quelqu'un sait si les calculatrices TI avancées, comme la TI-92, utilisaient ce système ? Il y avait un mode « rationnel », donc elles utilisaient peut-être la RRA
• Cette manière d'utiliser la « recursive real arithmetic » (RRA) m'a rappelé une excellente discussion avec Conal Elliot. On y parlait du passage d'une représentation discrète des choses à une représentation continue
  • Par exemple, autrefois les polices étaient représentées comme des blocs de pixels, alors qu'aujourd'hui elles sont perçues comme des lignes/vecteurs. L'informatique ne devrait pas consister uniquement à apprendre les derniers outils commerciaux, mais aussi à rechercher la vérité
• J'ai joué avec le code source de la calculatrice de l'Android Open Source Project. Google l'a déplacé vers Google Play Services, mais l'ancien code source reste disponible
  • Cela résout quelques vrais problèmes, et j'aimerais pouvoir l'utiliser dans une bibliothèque. Il y avait une discussion sur quelques bibliothèques dans l'article précédent