Somme (algorithmique)
- Somme (algorithmique)
-
Pour les articles homonymes, voir
Somme.
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 résistera mieux à 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)
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Somme (algorithmique) de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
ALGORITHMIQUE — L’objet de l’algorithmique est la conception, l’évaluation et l’optimisation des méthodes de calcul en mathématiques et en informatique. Un algorithme consiste en la spécification d’un schéma de calcul, sous forme d’une suite d’opérations… … Encyclopédie Universelle
Somme de controle — Somme de contrôle La somme de contrôle (en anglais checksum) est un concept de la théorie des codes utilisé pour les codes correcteurs, elle correspond à un cas particulier de contrôle par redondance. Elle est largement utilisée en informatique… … Wikipédia en Français
Somme de contrôle — La somme de contrôle (le terme anglais checksum est également employé), parfois appelé « empreinte », est un nombre qu on ajoute à un message à transmettre pour permettre au récepteur de vérifier que le message reçu est bien celui qui a … Wikipédia en Français
Vérification de somme — Somme de contrôle La somme de contrôle (en anglais checksum) est un concept de la théorie des codes utilisé pour les codes correcteurs, elle correspond à un cas particulier de contrôle par redondance. Elle est largement utilisée en informatique… … Wikipédia en Français
Probleme de la somme de sous-ensembles — Problème de la somme de sous ensembles Le problème de la somme de sous ensembles aussi noté SSP (de l anglais Subset Sum Problem) est un problème important en complexité algorithmique et en cryptologie. Le problème est le suivant : étant… … Wikipédia en Français
Problème de la somme d'un sous-ensemble — Problème de la somme de sous ensembles Le problème de la somme de sous ensembles aussi noté SSP (de l anglais Subset Sum Problem) est un problème important en complexité algorithmique et en cryptologie. Le problème est le suivant : étant… … Wikipédia en Français
Problème de la somme de sous-ensembles — Le problème de la somme de sous ensembles aussi noté SSP (de l anglais Subset Sum Problem) est un problème important en complexité algorithmique et en cryptologie. Le problème est le suivant : étant donné un ensemble E de n entiers, existe t … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Constante d'Euler-Mascheroni — En mathématiques, la constante d Euler Mascheroni, ou constante d Euler, est une constante mathématique, utilisée principalement en théorie des nombres, définie comme la limite de la différence entre la série harmonique et le logarithme naturel.… … Wikipédia en Français
