Somme (algorithmique)
Un article de Wikipédia, l'encyclopédie libre.
Alors que l'addition semble l'opération la plus banale qui soit, avec un ordinateur, la qualité et la précision du résultat relèvent souvent du mode de représentation des nombres en jeu, de leurs ordres de grandeur, de l'ordre des opérations, du type d'ordinateur (16, 32 et 64 bits) du langage de programmation et de sa maîtrise (par défaut, Python calcule en précision infinie, ce qui n'est pas le cas de C ou Fortran). Les sources d'erreurs peuvent être plus ou moins évidentes.
On rappelle que la norme actuelle IEEE_754 permet de comparer l'algorithmique et les résultats sur des machines différentes grâce à un code portable des nombres.
Source d'erreur classiques:
- modulo: 32000+1000 = -32536 lorsque les entiers sont codés sur seulement 16 bits signés, et le plus grand entier (avant le modulo) est 32767 (2^15-1) (2^16=-32768)
- non associativité (1e-10+1.)-1. = 0. et 1e-10+(1.-1. ) =1e-10 (dans le cas où on est en simple précision, avec 'esp' de l'ordre de 1.19e-7)
- soit N réels égaux de valeur M. Selon les valeurs N et M, on peut avoir jusqu'à 10% d'erreur pour une simple sommation sans précaution. Par exemple, si N vaut 1e8 et M -1e14, l'erreur atteint 7% en simple précision !
- sens de la sommation : si on somme des petits nombres vers les grands nombres, on resistera mieux a une propagation des erreurs d'arrondi
Algorithmes:
- Kahan, 1960, cf la page (en) dans wikipedia en attendant
- Rump et al., 2005 , cf [1] et code (matlab)
