Discussion :

[Nemerle]

Salut,

comment calculeriez-vous avec une précision à deux chiffres après la virgule la somme des C(n,i)x^i(1-x)^(N-i) pour i de 0 à S<N, avec x<1 ? Pour N=5000 par exemple et S=4000...

[Invité(e)]

Bonjour,

Un petite question sur le terme à sommer : faut-il lire :

Code :

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

1
2
3
4
5
/   \
| N |  i     N-i
|   | x (1-x) 
| i |
\   /

ou

Code :

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

1
2
3
4
5
/   \          N-i
| N |  i (1-x)     
|   | x 
| i |
\   /

?

Si c'est la première solution, on retombe sur le binôme de Newton (en fait non puisse qu'on s'arrête à S < N ...)

[Nemerle]

il faut lire ta 1ière proposition.

effectivement, le problème vient de la somme partielle...

[pseudocode]

Si c'est la première solution, on retombe sur le binôme de Newton (en fait non puisse qu'on s'arrête à S < N ...)

Du coup, ca revient a calculer la somme pour S>=N et la retrancher à la somme globale ( = 1 ).

[Nemerle]

certes, mais ça n'avance pas le chimilimi...

[Invité(e)]

si on reprend le schéma du triangle, il y a peut etre quelque chose à fouiller :
Si N égale 5 et S 3

Code :

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

1
2
3
4
5
6
     1
    1 1
   1 2 1
  1 3 3 1 
 1 4 6 4 1
1 5 10105 1

On pourrait dire que la somme à trouver est 1 moins les coefficients collés à droite, mais je pense qu'on retombe sur un problème similaire avec beaucoup de coefficients à sommer.

EDIT :
En creusant, on pourrait peut-être approximer les coefficients à sommer à une loi gaussienne, leur somme à l'intégrale donc une loi normale. (Mes anciens prof de maths doivent s'en retourner dans leur classe)

[pseudocode]

certes, mais ça n'avance pas le chimilimi...

Ca fait déjà moins de terme à sommer si j'en juge ton exemple du 1er post.

En prenant le Log de la somme, ca allège un peu les calculs à faire, vu qu'on peut factoriser par Log(x) et Log(1-x).

[Nemerle]

En prenant le Log de la somme, ca allège un peu les calculs à faire, vu qu'on peut factoriser par Log(x) et Log(1-x).

Gné???? Le log d'une SOMME?

[pseudocode]

Gné???? Le log d'une SOMME?

Arf. J'ai besoin de vacances. Je pensais que le 1er terme de la somme valait 1 et donc que ca simplifiait la somme de Log.

Hum... bon. C'est vrai que c'est pas simple comme problème. Ca revient au calcul de la fonction de répartition d'une distribution binomiale, non ?

[JeitEmgie]

Salut,

comment calculeriez-vous avec une précision à deux chiffres après la virgule la somme des C(n,i)x^i(1-x)^(N-i) pour i de 0 à S<N, avec x<1 ? Pour N=5000 par exemple et S=4000...

çà me fait penser à une courbe de Bezier de degré N ?
…sauf que vous "coupez" au degré S dans l'évaluation…

courbe de Bezier :

B(t) = Somme de i=0 à N de C(n,i) * (1-t)^(N-i) * t^i * Pi

votre formule, sauf erreur :

F(x) = Somme de i=0 à S de C(n,i) * (1-x)^(N-i) * x^i

Donc votre F(x) serait une courbe de Bezier de degré N avec Pi=(1,1) pour tout i <= S et Pi=(0,0) pour i > S…

?

[Zavonen]

Il me semble que la solution de ce problème se trouve entre (en combinant) les deux articles:
Cumulative Binomial Distribution
et
Incomplete Beta Fonction
de Numerical recipes in C
adresse:
http://www.fizyka.umk.pl/nrbook/bookcpdf.html

[Nemerle]

Merci Zavonen, je vais regarder ASAP.

[JeitEmgie]

Merci Zavonen, je vais regarder ASAP.

examinez la similitude avec la courbe de Bezier, si c'est bien le cas ce n'est pas les algorithmes efficaces qui manquent… et dans votre cas vous n'avez qu'une dimension à évaluer…

par exemple :

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
26
27
28
 
/*
 Simplified Casteljau algorithm for only one dimension
 and control "points" only 1 and 0
 t in [0-1]
 p array of N (number of control points) float
 */
float evaluate1(float *p,int n, int s, float t)
{	
	// we evaluate only one coordinates of the Bezier
	// with P[0 -> S].x = 1 and P[S+1 -> N-1].x = 0
	// n the degree of the "curve" == number of control points - 1 == N - 1
 
	for(int i=0;i<=s;i++)
		p[i] = 1.0 ;
	for(int i=s+1;i<=n;i++)
		p[i] = 0.0 ;
 
	float t1 = (1.0 - t) ;
 
	for(int j=1;j<n;j++) {
		for(int i=0;i<n-j;i++) {
			p[i] = t1 * p[i] + t * p[i+1] ;
		}
	}
 
	return p[0] ;
}

[Nemerle]

Zavonen: oui, ça répond à mon besoin.

Mais finalement, on a implémenté la représentation en rationnel & la norme MPFR, pour calculer tout ça!