Quel algorithme est le plus précis pour calculer la somme d'un tableau trié de nombres?

Etant donné une suite finie croissante de nombres positifs . Lequel des deux algorithmes suivants est le meilleur pour calculer la somme des nombres?$z_{1} ,z_{2},.....z_{n}$

s=0; 
for \ i=1:n 
    s=s + z_{i} ; 
end

Ou:

s=0; 
for \ i=1:n 
s=s + z_{n-i+1} ; 
end

À mon avis, il serait préférable de commencer à ajouter les nombres du plus grand au plus petit, car l'erreur devient de plus en plus petite. Nous savons également que lorsque nous ajoutons un très grand nombre à un très petit nombre, le résultat approximatif peut être le grand nombre.

Est-ce correct? Quoi d'autre peut être dit?

L'ajout de nombres à virgule flottante arbitraires donnera généralement une erreur d'arrondi, et l'erreur d'arrondi sera proportionnelle à la taille du résultat. Si vous calculez une somme unique et commencez par ajouter les plus grands nombres en premier, le résultat moyen sera plus grand. Donc, vous commenceriez à ajouter avec les plus petits nombres.

Mais vous obtenez un meilleur résultat (et cela s'exécute plus rapidement) si vous produisez quatre sommes, par exemple: Commencez avec sum1, sum2, sum3, sum4 et ajoutez quatre éléments de tableau à tour de rôle à sum1, sum2, sum3, sum4. Étant donné que chaque résultat n'est en moyenne que le 1/4 de la somme d'origine, votre erreur est quatre fois plus petite.

Mieux encore: ajoutez les nombres par paires. Ajoutez ensuite les résultats par paires. Ajoutez à nouveau ces résultats par paires, et ainsi de suite jusqu'à ce qu'il vous reste deux chiffres à ajouter.

Très simple: utilisez une précision plus élevée. Utilisez le double long pour calculer une somme de doubles. Utilisez double pour calculer une somme de flottants.

Proche de la perfection: recherchez l'algorithme de Kahan, décrit précédemment. Mieux encore utilisé en ajoutant en commençant par le plus petit nombre.

S'agit-il d'entiers ou de nombres à virgule flottante? En supposant que ce soit une virgule flottante, je choisirais la première option. Il est préférable d'ajouter les plus petits nombres les uns aux autres, puis d'ajouter les plus grands nombres plus tard. Avec la deuxième option, vous finirez par ajouter un petit nombre à un grand nombre à mesure que j'augmente , ce qui peut entraîner des problèmes. Voici une bonne ressource sur l'arithmétique en virgule flottante: ce que tout informaticien devrait savoir sur l' arithmétique en virgule flottante

La réponse de animal_magic est correcte: vous devez ajouter les nombres du plus petit au plus grand, mais je veux donner un exemple pour montrer pourquoi.

Supposons que nous travaillons dans un format à virgule flottante qui nous donne une précision stupéfiante de 3 chiffres. Maintenant, nous voulons ajouter dix nombres:

[1000, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Bien sûr, la réponse exacte est 1009, mais nous ne pouvons pas l'obtenir dans notre format à 3 chiffres. Arrondi à 3 chiffres, la réponse la plus précise que nous obtenons est 1010. Si nous ajoutons du plus petit au plus grand, sur chaque boucle, nous obtenons:

Loop Index        s
1                 1
2                 2
3                 3
4                 4
5                 5
6                 6
7                 7
8                 8
9                 9
10                1009 -> 1010

Nous obtenons donc la réponse la plus précise possible pour notre format. Supposons maintenant que nous ajoutons du plus grand au plus petit.

Loop Index        s
1                 1000
2                 1001 -> 1000
3                 1001 -> 1000
4                 1001 -> 1000
5                 1001 -> 1000
6                 1001 -> 1000
7                 1001 -> 1000
8                 1001 -> 1000
9                 1001 -> 1000
10                1001 -> 1000

Étant donné que les nombres à virgule flottante sont arrondis après chaque opération, tous les ajouts sont arrondis, augmentant notre erreur de 1 à 9 par rapport à l'exacte. Imaginez maintenant si votre ensemble de nombres à ajouter avait un 1000, puis cent 1 ou un million. Notez que pour être vraiment précis, vous devez additionner les deux plus petits nombres, puis utiliser le résultat dans votre ensemble de nombres.

Pour le cas général, j'utiliserais la sommation compensée (ou la sommation de Kahan). À moins que les numéros ne soient déjà triés, leur tri sera beaucoup plus coûteux que leur ajout . La sommation compensée est également plus précise que la sommation triée ou la sommation naïve (voir le lien précédent).

En ce qui concerne les références, ce que tout programmeur devrait savoir sur l'arithmétique à virgule flottante couvre les points de base avec suffisamment de détails pour que quelqu'un puisse le lire en 20 (+/- 10) minutes et comprendre les bases. "Ce que tout informaticien devrait savoir sur l'arithmétique à virgule flottante" de Goldberg est la référence classique, mais la plupart des gens que je connais qui recommandent que le papier ne l'ont pas lu eux-mêmes en détail, car il fait environ 50 pages (plus que cela, dans certains imprimés) et écrits en prose dense, j'ai donc du mal à recommander cela comme référence de première ligne pour les gens. C'est bon pour un deuxième regard sur le sujet. Une référence encyclopédique est la précision et la stabilité des algorithmes numériques de Higham, qui couvre ce matériau, ainsi que l'accumulation d'erreurs numériques dans de nombreux autres algorithmes; c'est aussi 680 pages, donc je ne regarderais pas cette référence non plus.

Les réponses précédentes discutent déjà de la question dans son ensemble et donnent de bons conseils, mais il y a une bizarrerie supplémentaire que je voudrais mentionner. Sur la plupart des architectures modernes, la forboucle que vous avez décrite serait exécutée de toute façon avec une précision étendue de 80 bits , ce qui garantit une précision supplémentaire, car toutes les variables temporaires seront placées dans des registres. Vous disposez donc déjà d'une forme de protection contre les erreurs numériques. Cependant, dans des boucles plus compliquées, les valeurs intermédiaires seront stockées en mémoire entre les opérations, et donc tronquées à 64 bits. je suppose que

s=0; 
for \ i=1:n 
    printf("Hello World");
    s=s + z_{i} ; 
end

suffit pour obtenir une précision moindre dans votre sommation (!!). Soyez donc très prudent si vous souhaitez imprimer-déboguer votre code tout en vérifiant l'exactitude.

Pour les personnes intéressées, cet article décrit un problème dans une routine numérique largement utilisée (factorisation QR révélatrice de rang de Lapack) dont le débogage et l'analyse étaient très délicats précisément à cause de ce problème.

Des 2 options, l'ajout du plus petit au plus grand produira moins d'erreur numérique que l'ajout du plus grand au plus petit.

Cependant, il y a> 20 ans dans ma classe "Méthodes numériques", l'instructeur l'a déclaré et il m'est venu à l'esprit que cela introduisait toujours plus d'erreurs que nécessaire en raison de la différence relative de valeur entre l'accumulateur et les valeurs ajoutées.

Logiquement, une solution préférable consiste à ajouter les 2 plus petits nombres dans la liste, puis à réinsérer la valeur additionnée dans la liste triée.

Pour le démontrer, j'ai élaboré un algorithme qui pourrait le faire efficacement (dans l'espace et dans le temps) en utilisant l'espace libéré lorsque les éléments ont été supprimés du tableau principal pour créer un tableau secondaire des valeurs sommées qui ont été intrinsèquement ordonnées depuis les ajouts. étaient des sommes de valeurs toujours croissantes. À chaque itération, les "astuces" des deux tableaux sont ensuite vérifiées pour trouver les 2 plus petites valeurs.

Puisque vous n'avez pas restreint le type de données à utiliser, pour obtenir un résultat parfaitement précis, utilisez simplement des nombres de longueur arbitraire ... dans ce cas, l'ordre n'aura pas d'importance. Ce sera beaucoup plus lent, mais l'obtention de la perfection prend du temps.

Utiliser l'ajout d'arbre binaire, c'est-à-dire choisir la moyenne de la distribution (nombre le plus proche) comme racine de l'arbre binaire, et créer un arbre binaire trié en ajoutant des valeurs inférieures à gauche du graphique et des valeurs plus grandes à droite et ainsi de suite . L'ajout de tous les nœuds enfants d'un parent unique récursivement dans une approche ascendante. Cela sera efficace car l'erreur moyenne augmente avec le nombre de sommations et dans une approche d'arbre binaire, le nombre de sommations est de l'ordre de log n en base 2. Par conséquent, l'erreur moyenne serait moindre.

Ce que Hristo Iliev a dit ci-dessus à propos des compilateurs 64 bits préférant les instructions SSE et AVX au FPU (AKA NDP) est absolument vrai, du moins pour Microsoft Visual Studio 2013. Cependant, pour les opérations à virgule flottante double précision que j'utilisais, j'ai trouvé il est en fait plus rapide, et en théorie plus précis, d'utiliser le FPU. Si c'est important pour vous, je vous suggère de tester différentes solutions avant de choisir une approche finale.

Lorsque je travaille en Java, j'utilise très fréquemment le type de données BigDecimal à précision arbitraire. C'est tout simplement trop facile, et on ne remarque généralement pas la diminution de la vitesse. Le calcul des fonctions transcendantales avec des séries infinies et sqrt en utilisant la méthode de Newton peut prendre une milliseconde ou plus, mais il est faisable et assez précis.

Je n'ai laissé cela ici /programming//a/58006104/860099 (lorsque vous y allez, cliquez pour «afficher l'extrait de code» et l'exécuter par le bouton

C'est un exemple JavaScript qui montre clairement que la somme à partir de la plus grande donne une plus grande erreur

arr=[9,.6,.1,.1,.1,.1];

sum     =             arr.reduce((a,c)=>a+c,0);  // =  9.999999999999998
sortSum = [...arr].sort().reduce((a,c)=>a+c,0);  // = 10

console.log('sum:     ',sum);
console.log('sortSum:',sortSum);