Je viens de parler de algorithme de sommation Kahan (ou compensé) pour minimiser le relancement , et J'aimerais savoir s'il ya des algorithmes équivalents pour la division et / ou la multiplication, ainsi que la soustraction (s'il s'agit d'un, je sais que l'associativité). Des exemples de mise en œuvre dans une langue, un pseudo-code ou des liens seraient géniaux!
merci
3 Réponses :
La soustraction est généralement manipulée via la méthode Kahan.
Pour la multiplication, il existe des algorithmes pour convertir un produit de deux nombres à virgule flottante en une somme de deux nombres à virgule flottante sans arrondissement, à quel point vous pouvez utiliser Kahan Sommation ou une autre méthode, en fonction de ce que vous devez faire ensuite avec le produit.
Si vous avez FMA (Fused Multiply-Add) disponible, cela peut être facilement accompli comme suit: < Pré> xxx
après ces deux opérations, si aucun débordement ou sous-fleuve ne se produit, division ... Eh bien, la division est mieux évitée. La division est lente et la division indemnisée est encore plus lente. Vous pouvez le faire, mais c'est brutalement dur sans FMA et non trivial avec elle. Mieux vaut concevoir vos algorithmes pour l'éviter autant que possible. Notez que tout cela devient une bataille perdue assez rapidement. Il y a une bande de situations très étroite où ces astuces sont bénéfiques - pour quelque chose de plus compliqué, il est beaucoup préférable de simplement utiliser une bibliothèque ponctuelle flottante de précision plus large comme p + r est exactement égal à a * b sans arrondir. Cela peut également être accompli sans FMA, mais c'est plutôt plus difficile. Si vous êtes intéressé par ces algorithmes, vous pouvez commencer par télécharger le crlibm Documentation , qui détaille plusieurs d'entre eux.
AFAIK, utilisant des types plus larges n'est qu'une mauvaise aide et aidera très peu si votre problème est mal conditionné ou que votre algorithme n'est pas stable.
@Michael Borgwardt: Cela dépend du problème. Si votre problème est mal conditionné, alors vos données d'entrée sont exactes (auquel cas augmenter la précision aidera réellement une fois que vous traversez certains seuils), ou la réponse est sans signification de toute façon (auquel cas cela n'a pas d'importance). Si votre algorithme est instable, cela dépend de la nature exacte de l'instabilité. Plus généralement, toutefois, tout problème pouvant être fixé en utilisant des arithmétiques compensés peut également être résolu en utilisant des types plus larges.
Aussi curieux que je suis, autant que j'aimerais tout savoir de tout ce qui concerne tout, je sais que je devrai régler à l'aide de bibliothèques et autres pour le moment, merci beaucoup pour votre réponse, je vais jeter un oeil à ça dès que possible. :)
Hmm que je peux usee pour cela? (ou un extrait de code utilisant l'instruction FMA avec des explications?)
@Geoff: Si vous utilisez la plupart des matériels de produits de base (x86, bras), vous n'avez pas d'instruction FMA de toute façon disponible, il n'y a donc pas trop de point. Si vous utilisez PPC ou Itanium ou l'une des autres architectures plus exotiques qui ont FMA , vous pouvez généralement l'obtenir directement avec un compilateur intégré à C, ou le FMA () < / Code> Fonction définie dans
Notez que vous pouvez toujours effectuer un FMA à l'aide de la fonction FMA () dans
Bien sûr, ni la mise en œuvre de la bibliothèque, je n'utilise pas actuellement (MSVC9, mais avec l'intention d'être portable à Linux) ou de Boost Support STD :: FMA. soupir. Arithmétique compensé? J'ai fait une recherche rapide à ce terme et je n'ai pas grandi beaucoup. Aussi, lipforge.ens-lyon.fr/frrs/shownotes.php? version_id = 123 me donne l'impression que cela ne sera pas beaucoup d'aide pour FMA ... Y a-t-il une meilleure expression de recherche que je pourrais utiliser cela pourrait m'aider? Au pire, je pourrais utiliser C ++ (ou pseudo) -code pour celui-ci (ne l'a pas encore trouvé).
@Geoff: Les notes de crlibm ne vont pas vraiment sur la manière de simuler un FMA , mais ils discutent d'un certain nombre de procédures qui vous permettent de contourner le manque d'un. En particulier, vous pourriez être intéressé par MUL12 () , qui fait la même chose "exprimer un produit comme une somme sans arrondi" comme je discuté sans l'utilisation de FMA .
Donc, l'algorithme énuméré à la page 15 convient à la page 15? ( lipforge.ens-lyon.fr/frrs/ download.php / 16 / crlibm-0.8beta3.pdf )
@Geoff: Correct, avec la mise en garde qu'il n'est exacte que dans le mode arrondi à proches par défaut à proches.
Hmm, eh bien, je suppose que je pourrais en faire l'utiliser tant que j'ajouterai une note qu'elle nécessite que le mode d'arrondi par défaut de ronde à proximité soit correct. Une autre question rapide cependant: pour améliorer la précision, l'extension de la précision de la précision des calculs intermédiaires (par exemple, une fonction prend un double et renvoie un double mais fonctionne sur de longs doubles à l'intérieur de la fonction pour les variables temporaires, uniquement pour replier le dos pour le retour. la valeur) fonctionne toujours quelles que soient les circonstances, car la coulée à un type plus petit tronque? J'ai remarqué que cette astuce pourrait être utilisée avec l'algorithme de sommation de Kahan.
@Geoff: coulée sur un type de type à virgule flottante plus petit, il ne tronque pas. De manière générale, cette approche vous procurera une précision un peu plus de précision, mais il existe des circonstances particulières dans lesquelles cela peut entraîner une perte de précision en raison de l'arrondi supplémentaire qui se produit lorsque vous convertiez en double (ces cas sont rares, cependant)
Ça a du sens. Quels types de cas pourraient entraîner une perte de précision due à l'arrondissement par conversion? Y a-t-il un exemple particulier que vous pourriez donner? À quel point ces cas sont-ils rares, sont-ils aussi rares que le débordement pourrait être?
J'ai oublié d'ajouter, est la perte de précision plus problématique que si je n'allonge pas la précision de la précision?
conception d'algorithmes pour être Numériquement stable est une discipline académique et un domaine de recherche en soi droit. Ce n'est pas quelque chose que vous pouvez faire (ou apprendre) de manière significative via des "feuilles de triche" - cela nécessite des connaissances mathématiques spécifiques et doit être effectuée pour chaque algorithme spécifique. Si vous voulez apprendre à faire cela, la référence dans l'article Wikipedia semble plutôt bonne: Nicholas J. Higham, précision et stabilité des algorithmes numériques, société de mathématiques industrielles et appliquées, Philadelphie, 1996. ISBN 0-89871-355- 2
Un moyen relativement simple de diagnostiquer la stabilité d'un algorithme consiste à utiliser Arithmétique intervalle .
L'objectif d'arithmétique indemnisé n'améliore généralement pas la stabilité. Plus souvent, il est de satisfaire une précision dure liée à un algorithme stable.
Intéressant, merci pour les liens, je vais y jeter un coup d'oeil quand j'ai une chance!
@Stephen, ah. Je ne savais pas qu'il y avait une différence. : S toujours intéressant cependant. :)
Vous méritez richement une uppote pour votre référence à Nicholas J. Higham's Précision et stabilité des algorithmes numériques . Je cherchais une ressource telle que celle-ci pour une très longue période. Merci!
Vous pouvez utiliser des bignums et des fractions rationnelles plutôt que des numéros de points flottants auquel cas vous n'êtes limité que par la disponibilité finie de la mémoire pour contenir la précision requise.
Pas une option, le solveur est déjà à la mémoire. Merci quand même.