Discussion :

[kromartien]

Bonjour, je veux faire un programme en C de calcul de moyenne, mais je suis confronté à un problème de limitation de type.

En fait, j'ai un tableau de unsigned long de 5000 points, et je veux réaliser une moyenne sur ce tableau. La difficulté est que la somme directe a toutes les chances de ne pas fonctionner, car la somme de 5000 unsigned long risque ne ne pas tenir dans un unsigned long. Je voudrai faire un algo du type

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
double mean_extreme(unsigned long * tab_in , unsigned long i, unsigned long size);
{
     double moyenne_calculee;
     while(i!=(size/2)-1)
     {
          moyenne_calculee=((tab_in[i] + tab_in[size-i-1])/2.0 + mean_extreme(tab_in,i+1,size))/2.0;
     }
     return moyenne_calculee;
}

Ça a une chance de marcher ?

[Zavonen]

Une moyenne est un isobarycentre.
Tu peux appliquer le théorème d'associativité des barycentres.
Qui dit que le barycentre de
(P1,m1) .... (Pn,mn)
est le barycentre du
barycentre de
(P1,m1) .... (Pn-1,mn-1) avec la masse m1+m2+ ..mn-1
avec le point pondéré (Pn,mn)
dans ce cas de figure la moyenne de
x1, .....,xn
est le barycentre de la moyenne de
x1,...xn-1 avec la masse n-1
avec le point (xn,1)
Il suffit d'itérer:
Moyenne des deux premiers
Moyenne pondérée de cette moyenne avec la masse 2 et du troisième avec la masse 1
Moyenne pondérée de cette moyenne avec la masse 3 et du qautrième avec la masse 1
And so on till the end

[pseudocode]

La difficulté est que la somme directe a toutes les chances de ne pas fonctionner, car la somme de 5000 unsigned long risque ne ne pas tenir dans un unsigned long.

c'est pour ca qu'on a inventé les "double"...

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
double moyenne_calculee=0;
for(int i=0;i<size;i++)
    moyenne_calculee+=tab_in[i];
moyenne_calculee/=size;

[kromartien]

Pour la pondération des moyennes successives, ça me paraît être la bonne méthode.
Et autrement, est-ce que l'appel récursif est correct, l'appel va-t-il marcher ? Ce serait beau d'utiliser la récursion.

[sidahmed]

Bonjour,

Bonjour, je veux faire un programme en C de calcul de moyenne, mais je suis confronté à un problème de limitation de type.

En fait, j'ai un tableau de unsigned long de 5000 points, et je veux réaliser une moyenne sur ce tableau. La difficulté est que la somme directe a toutes les chances de ne pas fonctionner, car la somme de 5000 unsigned long risque ne ne pas tenir dans un unsigned long. Je voudrai faire un algo du type

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
double mean_extreme(unsigned long * tab_in , unsigned long i, unsigned long size);
{
     double moyenne_calculee;
     while(i!=(size/2)-1)
     {
          moyenne_calculee=((tab_in[i] + tab_in[size-i-1])/2.0 + mean_extreme(tab_in,i+1,size))/2.0;
     }
     return moyenne_calculee;
}

Ça a une chance de marcher ?

J'ai déroulé ton code à travers un tout petit exemple mais malheureusement ça marche pas !

Cependant, je voulais faire quelques remarques et suggestions à propos de ce code :
- Le compteur i n'est pas initialisé,
- La variable i n'a pas besoin d'être du type long, un simple int suffirait,
- As-tu vraiment besoin d'une version récursive ? Autrement dit une version itérative ne t'intéresse pas ?
-

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

i != (size / 2) - 1

Je pense que l'utilisation l'opérateur de comparaison < serait plus propre et plus logique !

Pour la pondération des moyennes successives, ça me paraît être la bonne méthode.

À mon avis, pourquoi ne pas changer l'échelle : une sorte de petite codification en divisant tous les éléments du tableau par 10, 100, 1000, 10000, ...etc tout dépend des éléments s'ils sont petits, grands, trop grands, ...etc
Et calculer la moyenne tranquillement sans le moindre souci !

À bientôt.

[kromartien]

J'ai réécrit la version récursive et fait une version itérative :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
 
double mean_extreme(unsigned long * tab_in , unsigned long i, unsigned long size)
{
	if(i<(size/2))
	{
		double moyenne_calculee;
		moyenne_calculee=((tab_in[i] + tab_in[size-i-1])/2.0 + mean_extreme(tab_in,i+1,size))/2.0;
	}
	else
	{
		return moyenne_calculee;
	}
}
 
double mean_ponderee(unsigned long * tab_in, unsigned long SIZE)
{
	unsigned long i;
	double current_mean=tab_in[0];
	for(i=0;i<SIZE-1;i++)
	{
		current_mean = (current_mean * ((i+1.0)/(i+2.0))) + tab_in[i+1])*(1.0/(i+2.0));
	}
	return current_mean;
}

[Nemerle]

z'etes un peu fou les gars... pseudocode a tout bien résumé...

[kromartien]

D'accord, j'ai utilisé ces deux algorithmes en concurrence :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
/*(1)*/
double mean_ponderee(unsigned long * tab_in, unsigned long SIZE)
{
	unsigned long i;
	double current_mean=tab_in[0];
	for(i=0;i<SIZE-1;i++)
	{
		current_mean = (current_mean * ((i+1.0)/(i+2.0))) + tab_in[i+1]*(1.0/(i+2.0));
	}
	return current_mean;
}
 
/*(2)*/
double mean_classic(unsigned long * tab_in, unsigned long SIZE)
{
	unsigned long i;
	double mean=0;
	for(i=0;i<SIZE;i++)
	{
		mean=mean+tab_in[i];
	}
	mean = mean/SIZE;
	return mean;
}

Et j'obtiens de part et d'autre le même résultat.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

22.498000(1), 22.498000(2)

Ça marche, voilà, le premier a tout de même l'avantage de prévenir un dépassement de capacité de type.

Merci beaucoup.

[Zavonen]

current_mean = (current_mean * ((i+1.0)/(i+2.0))) + tab_in[i+1]*(1.0/(i+2.0));

Voilà une ligne qui coûte cher:
trois additions type double
deux divisions type double
deux multiplications type double

alors que :
(current_mean*(i+1)+tab_in[i+1])/(i+2) ferait la même chose
avec seulement
une mutiplication double
une addition double
une addition int
une division double

[pseudocode]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
double mean_ponderee(unsigned long * tab_in, unsigned long SIZE)
{
	unsigned long i;
	double current_mean=tab_in[0];
	for(i=0;i<SIZE-1;i++)
	{
		current_mean = (current_mean * ((i+1.0)/(i+2.0))) + tab_in[i+1]*(1.0/(i+2.0));
	}
	return current_mean;
}

Ça marche, voilà, le premier a tout de même l'avantage de prévenir un dépassement de capacité de type.

Curieuse remarque vu que tous les calculs sont effectués en type "double".

[souviron34]

Voilà une ligne qui coûte cher:
trois additions type double
deux divisions type double
deux multiplications type double

alors que :
(current_mean*(i+1)+tab_in[i+1])/(i+2) ferait la même chose
avec seulement
une mutiplication double
une addition double
une addition int
une division double

et même :

j = i + 1
current_mean*(j+tab_in[j])/(i+2)

avec ton nombre d'opération (tu as oublié dans ton cas une addition int)

[kromartien]

Merci d'avoir corrigé ma formule, c'est vrai que j'ai fait ça de manière irréfléchie.

Le format de représentation des double peut-il vraiment contenir la gamme entière des unsigned long ? Ne risque-t-on pas d'arriver à des erreurs d'arrondis avec la méthode "brute" contrairement à la méthode de calcul de moyennes successives ??

[pseudocode]

Le format de représentation des double peut-il vraiment contenir la gamme entière des unsigned long ? Ne risque-t-on pas d'arriver à des erreurs d'arrondis avec la méthode "brute" contrairement à la méthode de calcul de moyennes successives ??

Déja, tu as pratiquement tous tes calculs qui sont effectués en précision "double":

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
double current_mean
int i
long tab_in[]
 
(current_mean*(i+1)+tab_in[i+1])/(i+2)

calculs 1:
(i+1) --> int+int -> int
(i+2) --> int+int -> int

calcul 2:
current_mean*(i+1) --> double*int --> double

calcul 3:
current_mean*(i+1)+tab_in[i+1] --> double + long --> double

calcul 4:
(current_mean*(i+1)+tab_in[i+1])/(i+2) --> double/int --> double

De plus, j'ai l'impression que la methode des moyennes successives va generer une erreur de plus en plus grande du fait des multiplications successives par (i+1)/(i+2)

[kromartien]

Les erreurs d'arrondi n'interviennent que lors d'un dépassement de la capcité de représentation du type. Je divise au final par i+2, mais le nombre obtenu n'est jamais irrationnel, le nombre de décimale est limité, et apparemment il n'excède pas ,dans le cas des moyennes pondérées successives, le nombre de décimales permis par le type double.

Par contre, lorsque je fais la somme directe, je peux être amené à supposer que la somme de tous ces unsigned long va donner un nombre dont la représentation de la mantisse peut excéder les capacités d'un double.

En tous cas, je divise des nombres entiers, pour une moyenne sur ~500 nombres. Ça ne fait pas plus de 1/500 comme valeur minimale représentée par un double, càd 0.002, c'est largement faisable pour un type double si la moyenne n'excède pas [un grand nombre]

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. C'est pour ça que je cherchais un algorithme qui ne faisait pas une somme irréfléchie, qui fait juste une sommation sur un nombre de digits limité, pour prévenir le dépassement de la capacité de type.

[pseudocode]

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. C'est pour ça que je cherchais un algorithme qui ne faisait pas une somme irréfléchie, qui fait juste une sommation sur un nombre de digits limité, pour prévenir le dépassement de la capacité de type.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long value = 0x7fffffffffffffffL;  // max long value = 2^63-1
 
// mean of 500 times the maximum "long" value
// mean_1: weighted, mean_2:non-weighted
double mean_1=value, mean_2=0;
for(int i=0;i<500;i++) {
	mean_1 = (mean_1*(i+1) + value)/(i+2);
	mean_2 += value;
}
mean_2/=500;
 
System.out.println("mean_1:"+(long)mean_1);
System.out.println("mean_2:"+(long)mean_2);
System.out.println("expected:"+(long)value);

Résultats:

mean_1:9223372036854775807
mean_2:9223372036854775807
expected:9223372036854775807

Plus interessant, si au lieu de faire la moyenne des "2^63-1", on fait la moyenne des "2^63-2" on obtient:

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

Comme la methode "pondéré" fait egalement des conversions en "double", on a la meme erreur d'arrondi.

[souviron34]

euh.. juste pour info....

en 32 bits, double max = e+308 ... ça laisse de la marge non ?

[pseudocode]

euh.. juste pour info....

en 32 bits, double max = e+308 ... ça laisse de la marge non ?

Oui mais les "double 32bits (IEEE 704)" n'offrent que 52 bits de mantisse (=chiffres significatifs), contre 63 bits pour les "long" et 64 bits pour les "unsigned long".

[Jedai]

euh.. juste pour info....

en 32 bits, double max = e+308 ... ça laisse de la marge non ?

Sauf que ça ne veut absolument pas dire que tu as une telle précision, tu n'as pas 308 digits de précision (ou 1000 bits de précision si tu préfères)... Il est bien plus intéressant de dire qu'on a 52 bits de mantisse (pour les double IEEE en tout cas), et 11 bits d'exposants (ce qui correspond à ton 10^308).

Néanmoins effectivement, avoir peur de dépasser la précision des double pour son calcul de moyenne me semble indiquer qu'on a un problème de choix de type : si on veut vraiment un résultat exact et qu'on a de très grand nombres, on utilise une bibliothèque mathématique avec des types numériques de précision arbitraire, sinon, on utilise l'algorithme "naïf", et on accepte de perdre un tout petit peu en précision de temps en temps.

--
Jedaï

[souviron34]

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

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

[pseudocode]

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

La perte de précision fait partie du dépassement de capacité.

Que le dépassement soit sur les 52 bits de mantisse ou les 11 bits d'exposant, quand ca dépasse: ca dépasse.