Calcul des réels: virgule flottante vs TTE vs théorie des domaines vs etc
19
Actuellement, le calcul des réels dans les langages les plus populaires se fait toujours via des opérations en virgule flottante. D'un autre côté, des théories comme l'effectivité de type deux (TTE) et la théorie des domaines promettent depuis longtemps le calcul exact des réels. De toute évidence, le problème de la précision en virgule flottante n'a pas diminué en pertinence, alors pourquoi ces théories ne sont-elles pas devenues plus courantes et pourquoi n'y a-t-il pas d'implémentations plus visibles?
Par exemple, y a-t-il des domaines d'applications où nous ne nous soucions pas beaucoup des erreurs en virgule flottante? Y a-t-il des problèmes de complexité importants?
Je travaille dans le calcul en nombre réel et j'aimerais connaître la vraie réponse. Mais je peux spéculer. C'est un problème sociologique, je pense.
La communauté des personnes qui travaillent sur l'arithmétique réelle exacte se compose de théoriciens qui n'ont pas l'habitude de développer des logiciels. Ils relèguent donc généralement la tâche d'implémentation aux étudiants (une exception notable est l' iRRAM de Norbert Müller ), ou ils ont leurs propres implémentations de jouets .
Les gens qui font ont la programmation nécessaire mojo ne pas l'arrière - plan théorique nécessaire. Sans une assise théorique solide, il est difficile de concevoir correctement l'arithmétique réelle exacte. Par exemple, c'est une erreur d'ajouter de nombreux nombres réels dans une forboucle, car vous obtiendrez des performances inacceptables en raison de la perte de précision. Si vous voulez ajouter beaucoup, beaucoup de réels, vous devez le faire avec une structure arborescente, en tenant compte des grandeurs des sommes partielles. Une autre chose qui est difficile à traverser est que <et =comme la fonction booléenne totale sur les réels n'existe tout simplement pas (vous pouvez avoir =mais elle retourne falseou elle diverge et <diverge quand on lui donne deux réels égaux).
Enfin, il n'est pas du tout clair que nous savons comment implémenter des bibliothèques pour une véritable arithmétique réelle. Ce ne sont pas les bibliothèques habituelles qui définissent simplement certains types de données et certaines fonctions. Souvent, l'arithmétique réelle exacte nécessite des modes de contrôle spéciaux. Par exemple, iRRAM prend en charge l'exécution principale du programme (il détourne littéralement main), ainsi que les entrées et sorties standard, afin qu'il puisse réexécuter le programme en cas de perte de précision. Ma bibliothèque d'arithmétique réelle à Haskell se déroule dans une Stagedmonade (qui est essentiellement la Readermonade). La plupart des gens s'attendent à ce que les vrais chiffres soient "juste un autre type de données", mais j'ai des doutes à ce sujet.
Je suis presque entièrement ingénieux sur l'arithmétique réelle exacte, mais ne pourrait-on pas y implémenter la sommation de Kahan?
jjg
1
Hmm, je ne pense pas. Considérez l'arithmétique réelle exacte comme une arithmétique d'intervalle qui s'auto-ajuste la précision intermédiaire pour atteindre la précision de sortie souhaitée.
Andrej Bauer
3
En plus du manque de compréhension des programmeurs sur le fait que les nombres réels sont des objets infinis et ses conséquences sur ce qui peut être fait par programmation, je pense que le manque de support matériel est également important. Il est difficile de convaincre les gens d'utiliser quelque chose avec beaucoup de temps et de mémoire pour la justesse.
Kaveh
1
J'ai vu qu'il y avait une certaine activité dans l'implémentation du calcul réel avec des types coinductifs. Il me semble que les types coinductifs sont encore assez difficiles à obtenir correctement (je ne suis certainement pas un expert en la matière), mais pensez-vous que cela soit prometteur pour une utilisation plus répandue du calcul réel exact?
SorcererofDM
3
Toute implémentation qui utilise des flux de chiffres, ou toute autre chose qui a un taux de convergence fixe, est handicapée dès le départ en ce qu'elle convergera trop lentement. En outre, les implémentations basées sur les flux ont tendance à vous forcer à calculer toutes les approximations précédentes pour obtenir la suivante, ce qui est également une erreur de conception.
Andrej Bauer
10
En général, les gens se soucient toujours des erreurs en virgule flottante. Cependant, je ne suis pas d'accord avec Andrej, et je ne pense pas que les flotteurs soient préférés aux réels de précision arbitraire (pour la plupart) pour des raisons sociologiques.
Je crois que l'argument principal contre le calcul exact des réels est celui de la performance . Donc, la réponse courte est, chaque fois que les performances sont plus importantes que la précision, vous voudrez utiliser des nombres à virgule flottante .
L'application qui vient à l'esprit est l'utilisation de la dynamique des fluides computationnelle pour concevoir l'aérodynamique des voitures ou des avions, où de petites erreurs de calcul sont facilement compensées par les gains astronomiques de l'utilisation d' unités à virgule flottante dédiées trouvées dans de nombreux processeurs répandus.
En particulier, le problème de la représentation d'une large gamme de nombres réels en utilisant un nombre fixe de bits n'est pas aussi trivial qu'il puisse paraître à première vue. En simulation numérique, les valeurs peuvent varier considérablement (par exemple en cas de turbulence), donc les calculs à virgule fixe ne sont pas appropriés.
Même lorsque la précision n'est pas fixée par le matériel, l'utilisation de nombres de précision arbitraires peut être plus lente de plusieurs ordres de grandeur que l'utilisation de nombres à virgule flottante. En fait, même dans le cas idéal où tous les nombres sont rationnels, des opérations simples comme inverser une matrice peuvent entraîner de grands dénominateurs difficiles à contrôler (voir ici pour un exemple). De nombreux grands packages d'optimisation linéaire utilisent des virgules flottantes avec des modes d'arrondi appropriés pour trouver des solutions approximatives en raison de ce problème exact (voir par exemple, la majorité des programmes trouvés ici ).
y a-t-il des écarts prouvés entre une certaine forme de calcul réel exact et un calcul en virgule flottante?
SorcererofDM
1
Pas que je sache, j'ai peur. Sean Gao a des résultats intéressants sur la complexité des procédures de décision approximative sur les réels (voir son résumé de thèse ) et bien sûr le dénominateur à l'inverse d'une matrice croît au pire comme son déterminant .
cody
-6
π
Mon point étant que si vous voulez calculer exactement, vous devez avoir des espaces réservés pour les noms spéciaux ainsi que les noms familiers les naturels. À un moment donné, vous allez vouloir approximer la valeur exacte afin de l'appliquer à quelque chose dans le monde réel. En fin de compte, il est beaucoup plus efficace de traiter tout le problème comme des approximations dès le départ, sauf si vous avez des besoins très spécialisés.
En général, les gens se soucient toujours des erreurs en virgule flottante. Cependant, je ne suis pas d'accord avec Andrej, et je ne pense pas que les flotteurs soient préférés aux réels de précision arbitraire (pour la plupart) pour des raisons sociologiques.
Je crois que l'argument principal contre le calcul exact des réels est celui de la performance . Donc, la réponse courte est, chaque fois que les performances sont plus importantes que la précision, vous voudrez utiliser des nombres à virgule flottante .
L'application qui vient à l'esprit est l'utilisation de la dynamique des fluides computationnelle pour concevoir l'aérodynamique des voitures ou des avions, où de petites erreurs de calcul sont facilement compensées par les gains astronomiques de l'utilisation d' unités à virgule flottante dédiées trouvées dans de nombreux processeurs répandus.
En particulier, le problème de la représentation d'une large gamme de nombres réels en utilisant un nombre fixe de bits n'est pas aussi trivial qu'il puisse paraître à première vue. En simulation numérique, les valeurs peuvent varier considérablement (par exemple en cas de turbulence), donc les calculs à virgule fixe ne sont pas appropriés.
Même lorsque la précision n'est pas fixée par le matériel, l'utilisation de nombres de précision arbitraires peut être plus lente de plusieurs ordres de grandeur que l'utilisation de nombres à virgule flottante. En fait, même dans le cas idéal où tous les nombres sont rationnels, des opérations simples comme inverser une matrice peuvent entraîner de grands dénominateurs difficiles à contrôler (voir ici pour un exemple). De nombreux grands packages d'optimisation linéaire utilisent des virgules flottantes avec des modes d'arrondi appropriés pour trouver des solutions approximatives en raison de ce problème exact (voir par exemple, la majorité des programmes trouvés ici ).
la source
Mon point étant que si vous voulez calculer exactement, vous devez avoir des espaces réservés pour les noms spéciaux ainsi que les noms familiers les naturels. À un moment donné, vous allez vouloir approximer la valeur exacte afin de l'appliquer à quelque chose dans le monde réel. En fin de compte, il est beaucoup plus efficace de traiter tout le problème comme des approximations dès le départ, sauf si vous avez des besoins très spécialisés.
la source