Bonjour à tous !
 
Je vous soumets une petite question de programmation/logique/algorithmique/mathématique ne visant pas un langage en particulier.
J'aimerais accélérer le calcul des éléments d'une suite, dont chaque élément dépend des précédents, par une parallélisation (multi-thread, multi-processeur, peu importe la technologie employée). Est-ce possible ?    
 
 
Pour mieux vous expliquer le problème, je vais exposer quelques idées sur un exemple, dont je doute toutefois de l'intérêt pratique.
 
ENONCE : soit une suite Un = F(Un-1, Un-2, Un-3) où F est une fonction dont le temps de calcul est long mais permet d'aboutir à un résultat précis.
 
QUESTION : Calculer 1000 éléments (par exemple) de la suite Un avec une précision donnée (disons 1%) rapidement.
 
IDEE : J'utilise une fonction G, approximativement égale à la fonction F, mais dont le calcul est bien plus rapide.

EN DETAIL :
J'utilise la fonction G pour calculer une valeur estimée de Un, notée Ûn.
J'ai donc Ûn = G(Un-1, Un-2, Un-3).
J'obtiens donc un calcul bien plus rapide de la suite mais avec une précision moindre.
 
En parallèle, je mène le calcul exact de Un = F(Un-1, Un-2, Un-3).
 
Je fais un test sur la validité de mon approximation : Ûn est-il égal à Un à plus ou moins 1% ?
Si la précision est bonne, je continue les calculs.
Si l'erreur commise est trop grande, je reprend les calculs avec la valeur exacte de Un.
 
 
CONCLUSION :
Une solution pareille pourrait-elle réduire mon temps de calcul de la suite ?
Sinon, avez vous d'autres idées ?
 
 
Merci à tous de m'avoir lu !  

... Si tu calcule une valeur a = F(x, y, z) pour chaque b = G(x, y, z) et qu'à chaque fois tu teste si abs((a-b)/a) < 1% laisse-moi te dire que ton calcul sera toujours plus lent qu'un calcul seul de F(x, y, z) (même en parallélisant) ...
Je crois que présenté comme ça ton pb mène à une impasse ...
Une solution serait d'être mathématiquement sûr que la précision soit toujours inférieure à 1% et tu ne dois jamais tester la différence avec F(x, y, z).
Une autre solution, mais que doit être rarement applicable, serait d'avoir une 3e fonction H(x, y, z) qui te donne directement la précision et d'être sûr que globalement le temps de calcul de H et G cumulé soit inférieur au temps de calcul seul de F (ce qui est mathématiquement peu probable pour une fonction donnée).
Sinon, une autre solution serait d'avoir une fonction H' borne supérieure de cette précision (ce qui est mathématique beaucoup plus réalisable) et qui respecte les même conditions que l'exemple précédent concernant le temps de calcul.
 
EDIT : Enfin sache aussi que tout dépends de la fonction F ...
PS : Le problème est intéressant mais c'est purement un pb de mathématique (i.e. pas d'informatique)
PS2 : j'utilise abs(x) pour 'la valeur absolue de x'

Merci Superbob, je comprends ce que tu veux dire.
 
A propos de tes suggestions, je n'ai aucun moyen de calculer (ou de majorer) la précision de manière non expérimentale (je suis obligé de faire la différence entre Ûn et Un).
 
Bien, ça signifie que le calcul d'une telle suite est impossible à accélérer.
Pour optimiser, il faudra donc que je me penche sur autre chose, comme les entrées/sorties...
 
(Au fait, c'est un projet sous Matlab, mais ça n'a pas beaucoup d'importance. Je l'ai mis dans cette section à défaut d'une autre plus appropriée).
 
Merci encore !

Je déplace dans Algorithme, c'est la section qui se rapproche le plus de tes besoins.

Dans le cas général tu ne peux pas vraiment paralléliser le calcul des différents Un puisque ta suite est définie de manière réursive. Chaque étape a besoin du résultat de l'étape précédente.
 
Par contre, puisque le terme de rang n dépend des 3 rangs précédent, il n'est pas impossible, suivant comment F est définie, que tu puisse paralléliser le calcul du rand n et une partie du calcul du rand n+1. En effet :
 
Un = F(Un-1, Un-2, Un-3)
Un+1 = F(Un, Un-1, Un-2)
 
Si ta fonction F peux être décomposée en deux fonctions G et H, de cette manière :
 
Un = H(Un-1, G(Un-2, Un-3))
Un+1 = H(Un, G(Un-1, Un-2))
 
Alors tu vois que tu peux calculer Un et G(Un-1, Un-2) en parallèle.
 
Evidemment dans le cas d'un calcul parallèle, la synchronisation de tes threads a un coup... Ce n'est donc intéressant que si la fonction H est beaucoup plus rapide de que la fonction G. Bref, ce n'est utilisable que ta fonction F fait des trucs très compliqués avec les rangs n-2 et n-3, puis fait un truc tout simple avec le rang n-1.

Merci Elmoricq, je suis désolé d'avoir troublé le café d'un godo pour ça    

Merci beaucoup pour ton idée !    
Je vais étudier la possibilité de dissocier les opérations sur les différents termes et voir s'il est possible/intéressant de paralléliser ainsi.
 
Bonne nuit !