calcul parallèle de série infinie

Question

J'ai juste une question rapide, sur la façon d'accélérer les calculs de séries infinies. Ceci est juste un des exemples: arctan (x) = x - x^3/3 + x^5/5 - x^7/7 + ....

Disons que vous avez des bibliothèque qui vous permettent de travailler avec de grands nombres, alors la première solution évidente serait de commencer à ajouter/soustraire chaque élément de la séquence jusqu'à atteindre la cible N.

Vous pouvez également pré-enregistrer X^n pour chaque prochaine élément au lieu de calculer x^(n + 2) vous pouvez faire lastX * (x^2)

Mais dans l'ensemble, il semble être une tâche très séquentielle, et que pouvez-vous faire pour utiliser plusieurs processeurs (8+)? ?

Merci beaucoup!

EDIT: Je vais devoir calculer quelque chose de 100k à 1m itérations. C'est une application basée sur C++, mais je cherche une solution abstraite, donc ça ne devrait pas avoir d'importance. Merci pour votre réponse.

Answer 1

Vous devez décomposer le problème pour qu'il corresponde au nombre de processeurs ou de threads dont vous disposez. Dans votre cas, vous pourriez avoir par exemple un processeur travaillant sur les termes pairs et un autre travaillant sur les termes impairs. Au lieu de précalculer x^2 et d'utiliser lastX * (x^2), vous utilisez lastX * (x^4) pour ignorer tous les autres termes. Pour utiliser 8 processeurs, multipliez le terme précédent par x^16 pour ignorer 8 termes.

post-scriptum La plupart du temps, lorsqu'on leur présente un problème comme celui-ci, il vaut la peine de chercher un moyen plus efficace de calculer le résultat. De meilleurs algorithmes battent plus de puissance la plupart du temps.

Answer 2

Eh bien, pour cet exemple, vous pourriez résumer la série (si j'ai les crochets dans les bons endroits):

(-1)^i * (x^(2i + 1))/(2i + 1) 

ensuite sur le processeur 1 de 8 calculer la somme des termes pour i = 1, 9, 17, 25, ...

Puis, le processeur 2 de 8 calculer la somme des termes pour i = 2, 11, 18, 26, ...

et ainsi de suite, finalement additionner les sommes partielles.

Ou, vous pourriez faire comme vous (presque) suggérer, donner i = 1..16 (disons) au processeur 1, i = 17..32 au processeur 2 et ainsi de suite, et ils peuvent calculer chaque puissance successive de x de la précédente. Si vous voulez plus de 8x16 éléments dans la série, attribuez-en plus à chaque processeur en premier lieu. Je doute que, pour cet exemple, il vaut la peine de paralléliser, je soupçonne que vous obtiendrez une précision double précision sur 1 processeur alors que les threads parallèles sont encore en train de se réveiller; mais c'est juste une supposition pour cet exemple, et vous pouvez probablement beaucoup de séries pour lesquelles la parallélisation en vaut la chandelle. Et, comme l'a déjà dit @Mark Ransom, un meilleur algorithme devrait battre à chaque fois la force brute et beaucoup de processeurs.

Answer 3

Si vous essayez de calculer la valeur de pi à des millions d'endroits ou quelque chose, vous devez d'abord être très attentif au choix d'une série qui converge rapidement et qui se prête à la parallélisation. Ensuite, si vous avez assez de chiffres, il deviendra finalement rentable de les répartir entre plusieurs processeurs; vous devrez trouver ou écrire une bibliothèque bignum qui peut le faire.

Notez que vous pouvez factoriser les variables de différentes manières; par exemple .:

atan(x)= x - x^3/3 + x^5/5 - x^7/7 + x^9/9 ... 
     = x*(1 - x^2*(1/3 - x^2*(1/5 - x^2*(1/7 - x^2*(1/9 ... 

Bien que la deuxième ligne est plus efficace qu'une mise en œuvre naïve de la première ligne, ce dernier calcul comporte encore une chaîne linéaire de dépendances de bout en bout. Vous pouvez améliorer votre en combinant des termes parallélisme par paires:

 = x*(1-x^2/3) + x^3*(1/5-x^2/7) + x^5*(1/9 ... 
     = x*((1-x^2/3) + x^2*((1/5-x^2/7) + x^2*(1/9 ... 
     = [yet more recursive computation...] 

Cependant, ce gain de vitesse est pas aussi simple que vous pourriez penser, depuis le temps pris par chaque calcul dépend de la précision nécessaire pour le maintenir. En concevant votre algorithme, vous devez en tenir compte; aussi, votre algèbre est intimement impliquée; c'est-à-dire, pour le cas ci-dessus, vous obtiendrez des fractions qui se répètent indéfiniment si vous faites des divisions régulières par vos nombres constants, donc vous devez trouver un moyen de faire face à cela, d'une manière ou d'une autre.