Vitesse d'exécution
Bonjour, j'ai une question, (c'est sûrement différent selon les langages de programmation, je parle plutôt ici de programmes en langage python).
Pour déterminer tous les premiers entre deux entiers M et N, est-il plus rapide de construire un programme qui teste si les entiers compris entre M et N sont premiers, ou bien de faire (N - M + 1) programmes séparés (que l'on lance en même temps) qui effectuent chacun le même teste pour un et un seul des entiers entre M et N. Un programme P0 qui teste si M est premier, un programme P1 qui teste si M+1 l'est... En lançant les (N - M +1) programmes en même temps.
En gros, soit un programme effectue les taches a puis b puis c..., soit on a un nombre X de programmes, que l'on lance en même temps, qui effectuent chacun une seule et unique tâche.
Pour déterminer tous les premiers entre deux entiers M et N, est-il plus rapide de construire un programme qui teste si les entiers compris entre M et N sont premiers, ou bien de faire (N - M + 1) programmes séparés (que l'on lance en même temps) qui effectuent chacun le même teste pour un et un seul des entiers entre M et N. Un programme P0 qui teste si M est premier, un programme P1 qui teste si M+1 l'est... En lançant les (N - M +1) programmes en même temps.
En gros, soit un programme effectue les taches a puis b puis c..., soit on a un nombre X de programmes, que l'on lance en même temps, qui effectuent chacun une seule et unique tâche.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
En pratique bien sûr c'est une autre histoire. Je ne suis absolument pas informaticien mais il faudrait savoir comment implémenter efficacement un certain nombre de calculs en parallèle, j'imagine que c'est un thème très classique.
- si tu disposes de plusieurs dizaines voire centaines de cœurs, alors la parallélisation est certainement plus rapide (des pistes ici)
- si tu n'as qu'un seul CPU avec quelques cœurs, il faudra très certainement composer (pour des questions de mémoire et de temps de calculs)
- dans tous les cas définir une taille critique en "découpant" le problème risque d'être nécessaire, à moins qu'une formule applicable telle quelle existe
Sur mon vieux portable avec 6 Go de mémoire, je peux facilement et rapidement travailler avec des vecteurs de quelques milliard de lignes.Je ne suis pas familier avec ce genre de calculs des nombres premiers, et une rapide recherche sur la toile montre qu'il existe différentes stratégies (exemple).
Quels sont les ordres de grandeurs de M et N ?
En réalité, je ne rencontre pas ce problème technique paul18. N'ayant pas testé pour de grandes valeurs moi-même, je ne sais pas à partir de quelle largeur d'intervalle ça devient très "long".
Ensuite il y a des programmes qui te donneront le nombre de nombres premiers entre m et n
tout dépend de la limite de m < n.
Par exemple entre n et 2n ou de n à +10000 ... etc.
Le programme que j'utilise en C++ , il prend : n = 7 500 000 000 000 et donc 2n = 15 000 000 000 000.
Voici un exemple en 58 secondes : il y a 2 875 934 292 nombre premiers famille 30k + 1 de 7 à 600 000 000 000.
Effectivement, c'est relativement rapide par rapport au python, peut-être parce que python traite ligne par ligne, je ne sais pas.