Trouvé sur un blog : calculer les "produits sauf un"
Jean-Claude Arbaut
calculer tous les p(k) = a(1)*...*a(n) o� seul a(k)
n'appara�t pas dans le produit.
Solution: faire les "produits cumul�s" dans un sens,
puis dans l'autre, et faire les produits des deux.
Exemple
p q r s # la liste
1 p pq pqr # produit cumul� de gauche � droite
qrs rs s 1 # produit cumul� de droite � gauche
qrs prs pqs pqr # produit des lignes
fu2 fr.comp.algorithmes
alainv...@gmail.com
wrote:
> On dispose d'une liste de nombres a(1),... a(n), et on veut
> n'apparaît pas dans le produit.
>
> Solution: faire les "produits cumulés" dans un sens,
> puis dans l'autre, et faire les produits des deux.
>
> Exemple
>
> p q r s # la liste
>
> qrs rs s 1 # produit cumulé de droite à gauche
Bonjour Jean-Claude,
Pour la somme des produits diminués on peut
calculer H*P , H somme des inverses = sum{ a(i)^ -1 , i de 1 à n}
P =prod{ a(i) , i de 1 à n} .
Pour les produits de lignes P^(n-1) ,
Alain
Patrick Coilland
Soit (n-1)+(n-1)+(n-2)=3n-4 multiplications et 2n emplacements m�moire
Alors que calculer pqrs puis diviser successivement par p, q r et s
n�cessite log2(n) multiplications + n divisions et n+1 emplacements m�moire
alainv...@gmail.com
>
> Solution: faire les "produits cumulés" dans un sens,
> puis dans l'autre, et faire les produits des deux.
>
> Exemple
>
> p q r s # la liste
>
> qrs rs s 1 # produit cumulé de droite à gauche
Bonjour Jean-Claude ,
" qrs prs pqs pqr # produit des lignes"
4 produits de 3 facteurs soit, par symétrie, 3 produits complets
de 4 facteurs ,
D'une manière générale pour n facteurs Prod{a(i) ,i de 1 à n} ^(n-1) .
Pour la somme tu avais si h =somme{a(i)^ -1 }
somme incomplète: h*Prod{a(i)}
Alain
Jean-Claude Arbaut
> Jean-Claude Arbaut a �crit :
>> On dispose d'une liste de nombres a(1),... a(n), et on veut
>> calculer tous les p(k) = a(1)*...*a(n) o� seul a(k)
>> n'appara�t pas dans le produit.
>>
>> Solution: faire les "produits cumul�s" dans un sens,
>> puis dans l'autre, et faire les produits des deux.
>>
>> Exemple
>>
>> p q r s # la liste
>>
>> 1 p pq pqr # produit cumul� de gauche � droite
>> qrs rs s 1 # produit cumul� de droite � gauche
>>
>> qrs prs pqs pqr # produit des lignes
>>
>>
>> http://sig9.com/node/417
>>
>> fu2 fr.comp.algorithmes
>
> Soit (n-1)+(n-1)+(n-2)=3n-4 multiplications et 2n emplacements m�moire
Ca n�cessite n emplacements m�moire, qui sont de toute fa�on
indispensables pour la sortie.
> Alors que calculer pqrs puis diviser successivement par p, q r et s
> n�cessite log2(n) multiplications + n divisions et n+1 emplacements m�moire
log2(n) multiplications, vraiment ?
Pourtant, il me semble, en posant des parenth�ses comme
on veut, on aura un arbre � n feuilles, donc n-1 noeuds
(c'est la profondeur de l'arbre qui peut �tre ramen�e
� log2(n)). A moins qu'une astuce m'ait �chapp�.
Et �a n�cessite des divisions (et aussi de v�rifier si
on divise par z�ro), l'autre non.
Quoi qu'il en soit, je trouvais cela joli, et �a semble
�tre le plus facile � coder.
alainv...@gmail.com
>
> Solution: faire les "produits cumulés" dans un sens,
> puis dans l'autre, et faire les produits des deux.
>
> Exemple
>
> p q r s # la liste
>
> qrs rs s 1 # produit cumulé de droite à gauche
Bonjour Jean Claude,
"qrs prs pqs pqr # produit des lignes "
soit (pqrs)^3 .
D'une manière générale:
Prod{ a(i) de 1 à n } ^(n -1) ,
pour la somme des produits incomplets:
qrs+ prs+ pqs +pqr et plus généralement
Prod{ a(i) de 1 à n } *Somme{1/a(i) de 1 à n } ,
Amicalement,
Alain
Jean-Claude Arbaut
> Quoi qu'il en soit, je trouvais cela joli, et �a semble
> �tre le plus facile � coder.
Quelques timings avec gcc -O2 et les deux m�thodes,
pour voir la diff�rence entre th�orie et machine r�elle :-)
A) celle que j'ai post�e: une boucle dans
un sens, une boucle dans l'autre, 3n multiplications
B) la "naturelle": le produit complet puis des divisions
n multiplications et n divisions, sans faire de test
de division par z�ro
Dans les deux cas on travaille avec un tableau de N "double"
La machine est un Core 2 Duo, sous Linux et gcc 4.3.3
Tadaaaam...roulement de tambour :-)
pour N<16380, A est meilleure que B (3.3 fois plus
rapide)
pour N>16400, B est meilleure que A (1.13 fois plus
rapide)
(avec -O6, les rapports valent 2 dans les deux cas)
Je suppose que le "saut" correspond � une limite de cache,
mais j'ai du mal � interpr�ter: d'apr�s les docs que je trouve,
le cache L1 fait 32k et le cache L2 fait 2M, or la limite
semble se situer � 256k (deux tableaux de 128k, un our l'entr�e
et un pour la sortie).
On doit pouvoir am�liorer en ajoutant des instructions de
prefetch dans les boucles, en faisant un "unroll", et
dans la m�thode B, en parall�lisant les multiplications
et les divisions avec les instructions SSE.
D'ailleurs, en jetant un oeil au code, avec -O6 les divisions
de la m�thode B sont parall�lis�es automatiquement.
Armel
4a23f660$0$17749$ba4a...@news.orange.fr...
� noter qu'il faut faire tr�s attention � la stabilit� de l'algo lors de
l'utilisation de flottants, car si a(k) est tr�s petit, le r�sultat p(k) =
p(tous) / a(k) risque d'�tre tr�s impr�cis!
cette impr�cision cro�t quand un a(k) quelconque tend vers z�ro
d'ailleurs!!! il suffit d'un k quelqconque avec a(k)=0 pour que tout soit
faux!
il peut �tre alors n�cessaire d'utiliser l'algorithme sans division.
Armel