Pertinence des calculs en virgule fixe et en précision arbitraire

Je vois très peu de bibliothèques / packages informatiques à virgule non flottante. Étant donné les diverses inexactitudes de la représentation en virgule flottante, la question se pose de savoir pourquoi il n'y a pas au moins certains domaines où cette précision accrue pourrait valoir la complexité de travailler avec des virgules fixes.

Y a-t-il des difficultés MAJEURES à utiliser, disons, un solveur de valeurs propres à virgule fixe? À quel point seraient-elles lentes / rapides, inexactes / précises?

Connexes: ceci et cela

L'utilisation de l'arithmétique à virgule fixe peut être appropriée dans certaines circonstances. Généralement pour le calcul scientifique (au moins dans le sens où la plupart des gens y pensent), il n'est pas approprié en raison de la nécessité d'exprimer les grandes plages dynamiques rencontrées. Vous citez des problèmes de valeurs propres à titre d'exemple, mais très souvent en science, on s'intéresse aux plus petites valeurs propres d'une matrice (par exemple, dans le calcul de l'état fondamental d'un système quantique). La précision des petites valeurs propres sera généralement assez détériorée par rapport aux grandes valeurs propres si vous utilisez un point fixe. Si votre matrice contient des entrées qui varient par de grands ratios, les petites valeurs propres peuvent être complètement inexprimables dans la précision de travail. C'est un problème avec la représentation des nombres; ces arguments sont valables quelle que soit la façon dont vous effectuez les calculs intermédiaires. Vous pourriez éventuellement travailler sur une mise à l'échelle à appliquer aux résultats calculés, mais maintenant vous venez d'inventer la virgule flottante. Il est facile de construire des matrices dont les éléments se comportent bien, mais dont les valeurs propres sont excessivement mal comportées (commeMatrices de Wilkinson , ou même des matrices avec des entrées entièrement entières ). Ces exemples ne sont pas aussi pathologiques que cela puisse paraître, et de nombreux problèmes à la pointe de la science impliquent des matrices très mal comportées, donc utiliser un point fixe dans ce contexte est une mauvaise idée (TM).

Vous pourriez faire valoir que vous connaissez l'ampleur des résultats et que vous ne voulez pas gaspiller de bits sur l'exposant, alors parlons des intermédiaires. L'utilisation du point fixe exacerbera généralement les effets des annulations catastrophiques et des arrondis, à moins que vous ne vous efforciez vraiment de travailler avec une plus grande précision. La pénalité de performance serait énorme, et je suppose que l'utilisation d'une représentation en virgule flottante avec la même largeur de bit de mantisse serait plus rapide et plus précise.

Un domaine où le point fixe peut briller est dans certains domaines du calcul géométrique. Surtout si vous avez besoin d'une arithmétique exacte ou connaissez la plage dynamique de tous les nombres à l'avance, le point fixe vous permet de profiter de tous les bits de votre représentation. Par exemple, supposons que vous vouliez calculer l'intersection de deux lignes et que les extrémités des deux lignes soient normalisées pour s'asseoir dans le carré de l'unité. Dans ce cas, le point d'intersection peut être représenté avec plus de bits de précision qu'en utilisant un nombre à virgule flottante équivalent (ce qui gaspillera des bits sur l'exposant). Or, il est presque certainement vrai que les nombres intermédiaires requis dans ce calcul doivent être calculés avec une plus grande précision, ou du moins très soigneusement (comme lorsque vous divisez le produit de deux nombres par un autre nombre, vous devez être très prudent ). À cet égard, le point fixe est plus avantageux du point de vue de la représentation que du point de vue informatique, et j'irais jusqu'à dire que cela est généralement vrai lorsque vous pouvez établir des limites supérieures et inférieures définies sur la plage dynamique de vos sorties d'algorithme . Cela arrive rarement.

Je pensais que les représentations en virgule flottante étaient grossières ou inexactes (pourquoi gaspiller des bits sur un exposant?!). Mais avec le temps, je me suis rendu compte que c'est vraiment l'une des meilleures représentations possibles pour les nombres réels. Les choses dans la nature apparaissent sur des échelles logarithmiques, de sorte que les données réelles finissent par couvrir un large éventail d'exposants. Aussi, pour atteindre la précision relative la plus élevée possible, il faut travailler sur des échelles logarithmiques, ce qui rend le suivi d'un exposant plus naturel. Le seul autre concurrent pour une représentation "naturelle" est l' indice de niveau symétrique . Cependant, l'addition et la soustraction sont beaucoup plus lentes dans cette représentation, et il manque le support matériel de l'IEEE 754. Une énorme quantité de réflexion a été mise sur les standards à virgule flottante, par un pilier d'algèbre linéaire numérique. Je pense qu'il sait quelle est la "bonne" représentation des nombres.

Pour illustrer pourquoi l'arithmétique exacte / l'arithmétique à virgule fixe est si rarement utilisée, considérez ceci:

• Dans la méthode des éléments finis, comme dans presque toutes les autres méthodes utilisées dans le calcul scientifique, nous arrivons à des systèmes linéaires ou non linéaires qui ne sont que des approximations du monde réel. Par exemple, dans le FEM, le système linéaire à résoudre n'est qu'une approximation de l'équation différentielle partielle d'origine (qui ne peut elle-même être qu'une approximation du monde réel). Alors, pourquoi faire d'énormes efforts pour résoudre quelque chose qui n'est qu'une approximation?

• La plupart des algorithmes que nous utilisons aujourd'hui sont de nature itérative: méthode de Newton, Gradients conjugués, etc. Nous terminons ces itérations chaque fois que nous sommes convaincus que la précision de l'itérative approximative à la solution du problème est suffisante. En d'autres termes, nous terminons avant d'avoir la solution exacte. Comme précédemment, pourquoi utiliser l'arithmétique exacte pour un schéma itératif alors que nous savons que nous ne calculons que des approximations?

Si vous regardez cette bibliothèque pour un arrondi correct: CRlibm , vous verrez dans la documentation qu'en général, les algorithmes doivent être prouvés précis (avec des preuves motivées). Pourquoi? La stabilité et la vitesse de convergence d'un résultat d'une fonction n'ont pas de réponse "universelle". En bref, il n'y a "pas de déjeuner gratuit" - vous devez travailler pour prouver que votre raisonnement est correct. Cela est dû au comportement des fonctions modélisées, pas au matériel sous-jacent (que vous utilisiez des unités entières ou à virgule flottante, mais oui, les deux ont des "gotchas", comme le débordement / le débordement, les nombres dénormaux, etc.) Même si le résultat que vous recherchez converge vers un entier, l'algorithme utilisé pour trouver le résultat n'est pas nécessairement très stable.

Eigen est une bibliothèque C ++ qui a une variété d'algorithmes pour résoudre des matrices, chacune avec des propriétés différentes. Cette page contient un tableau qui discute des compromis vitesse / précision pour les différents algorithmes utilisés pour résoudre une matrice. Je soupçonne que la bibliothèque Eigen peut faire ce que vous voulez. :-)

Pour de beaux exemples où l'arithmétique de haute précision a été utile en mathématiques, jetez un œil au livre Mathematics by Experiment de Jonathan Borwein et David Bailey. Il y a aussi cette suite , que je n'ai pas lue.