Algorithme récursif de calcul de moyenne

Citation:

---

Envoyé par souviron34

Jedai tu n'as pas assez fait la sieste aujourd'hui... :aie:

Je ne parle pas de précision.... Mais de l'objection soulevée par Kromartien sur les dépassements de capacité...

---

Oh, d'accord, si tu le comprends comme ça, ton objection fait tout à fait sens, néanmoins je pense que Kromartien pensait à la précision en disant ça, en effet il a dit plus tard :

Citation:

---

j'avais juste un doute sur une somme de beaucoup de grands nombres, on peut aboutir à un chiffre qui dépasse la plage de représentation de la mantisse d'un double.

---

Ok, c'est pas très clair non plus remarque...

--
Jedaï

Citation:

---

Envoyé par souviron34

Jedai tu n'as pas assez fait la sieste aujourd'hui... :aie:

Je ne parle pas de précision.... Mais de l'objection soulevée par Kromartien sur les dépassements de capacité...

---

Le truc c'est que quand la somme des termes atteint une certaine valeur, on perd de la précision.

Imaginons qu'on a D qui vaut 2^n;
Pour que D soit modifié en lui sommant une valeur, il faut que cette valeur soit assez grande.

Imaginons qu'on lui rajoute un entier long, mais qui n'est pas assez grand pour modifier D, alors D ne sera pas modifié.

C'est pas grave, car on a pas assez de chiffres significatifs pour le représenter. Mais si on lui somme suffisamment d'entiers longs pour que le vrai résultat soit modifié, là il y a un problème, parce que dans le calcul, D sera resté constant.
Mais c'est peut-être négligeable, vu les ordres de grandeur considérés.

------

Pseudocode : la manière dont tu as effectué la somme des termes pondérés n'est pas correcte, parce que dans les calculs intermédiaires tu agrandis le résultat précédent (quand tu le multiplies par (i+1)), tu le sommes au terme suivant, puis tu divises par (i+2).

Kromartien multipliait directement par le quotient (i+1)/(i+2) afin de ne pas faire ça, puis il rajoute le terme pondéré. C'est ça la différence.

Par contre, il faut veiller à ce que le compilateur ne réorganise pas l'expression du calcul, ce dont on est pas du tout sûr.

Citation:

---

Envoyé par HanLee

Kromartien multipliait directement par le quotient (i+1)/(i+2) afin de ne pas faire ça, puis il rajoute le terme pondéré. C'est ça la différence.

---

Arg... cette méthode la est pire encore !!!

Code:

---

mean_1 = mean_1*((i+1.0)/(i+2.0)) + value/(i+2.0);

---

Code:

---

1 2 3 4

// avec long value = 0x7fffffffffffffffL; mean_1: 9223372036854775807 mean_2: 9223372036854775807 expected:9223372036854775807

---

Code:

---

1 2 3 4

// avec long value = 0x7000000000000001L; mean_1: 8070450532247924736 mean_2: 8070450532247928832 expected:8070450532247928833

---

Citation:

---

Envoyé par pseudocode

Arg... cette méthode la est pire encore !!!

Code:

---

mean_1 = mean_1*((i+1.0)/(i+2.0)) + value/(i+2.0);

---

Code:

---

1 2 3 4

// avec long value = 0x7fffffffffffffffL; mean_1: 9223372036854775807 mean_2: 9223372036854775807 expected:9223372036854775807

---

Code:

---

1 2 3 4

// avec long value = 0x7000000000000001L; mean_1: 8070450532247924736 mean_2: 8070450532247928832 expected:8070450532247928833

---

---

J'm'en doutais quand même, qu'on perdrait de la précision à chaque fois, vu le nombre de calculs supplémentaires.

Bon au moins on est fixés!

Sinon en utilisant une methode permettant de faire la moyenne pondérée de deux valeurs il y a moyen de faire tout le tableau de la maniere suivante

On a un tableau dont chaque case à deux variables : La valeur et le poids.

Code:

---

1 2 3 4

_________________________________________ Valeur |12|40|25|3 |84|7 |21|45|13|12|0 |18|76|1 | Poids |1 |1 |1 |1 |1 |1 |1 |1 |1 |1 |1 |1 |1 |1 | -----------------------------------------

---

Et à chaque passage dans le tableau on regarde le poids du premier element puis on fait la moyenne des paires de meme poids pour obtenir :

Code:

---

1 2 3 4

__________________________ Valeur |26|14|45.5|33|12.5|9 |38.5| Poids |2 |2 |2 |2 |2 |2 |2 | --------------------------

---

Puis cas plus interessant

Code:

---

1 2 3 4

___________________ Valeur |20|39.25|10.75|38.5| Poids |4 |4 |4 |2 | -------------------

---

Ici on garde un terme rebut de poids 2 (c'est normale)
Ensuite

Code:

---

1 2 3 4

_________________ Valeur |29.625|10.75|38.5| Poids |8 |4 |2 | -----------------

---

Ici on a plus deux termes de même poids , on entre dans la deuxieme phase : se debarasser des rebuts. On va donc a present faire des reduction terme à terme par la droite pour reduire au maximum les ecarts de poids entre termes

Code:

---

1 2 3 4

_________ Valeur |29.625|20| Ici pour reduire encore les possibilités de depassements de capacitée on reduit Poids |8 |6 | les poids 4 et 2 à 2 et 1 pour garder les rapports mais reduire les produits obtenus ... ---------

---

Et enfin ...

Code:

---

1 2 3 4

____ Valeur |25.5| Pareil que precedement Poids |14 | les poids 8 et 6 passent à 4 et 3 pour garder les rapports mais reduire les produits obtenus ... ----

---

Bien sur ca ne resout pas tous les problemes d'imprecision mais ca le diminue pas mal et l'algorithme s'execute au pire en Teta(n*Lb(n)/2) (je ne sais pas faire le char Teta, si tant est qu'il existe je suis preneur ;)...)

Citation:

---

Envoyé par GuJman

Sinon en utilisant une methode permettant de faire la moyenne pondérée de deux valeurs il y a moyen de faire tout le tableau de la maniere suivante (...)

---

Oui, c'est une méthode très utilisée en analyse numérique pour réduire les erreurs. D'ailleurs c'est un peu la meme idée de la représentation Mantisse/Exposant des double.

Citation:

---

je ne sais pas faire le char Teta, si tant est qu'il existe je suis preneur ;)

---

Θ