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.
Réponses
-
Si tu disposes d'une mémoire infinie, c'est bien entendu la seconde version qui est la plus rapide : disons que la vérification qui prenne le plus de temps parmi les entiers entre $M$ et $N$ soit celle pour l'entier $P$, alors dans la première méthode tu dois attendre que ta machine teste si $P$ est premier, mais à côté elle devra également tester tous les autres entiers entre $M$ et $N$, tandis que dans la seconde méthode, une fois que $P$ a été testé, tous les autres entiers entre $M$ et $N$ l'auront été également par définition et la procédure s'arrête là.
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. -
Poirot a tout à fait raison de parler de la taille du problème et de faire référence à la mémoire; j'y ajouterais la question du nombre de processeurs/cœurs:
- 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
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 ? -
Merci pour vos avis et les liens, je ne connaissais pas le test de primalité de Miller-Rabin, merci ! Je rejoins totalement Poirot.
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". -
Il y a sur le site alpertron pour tester de grand nombre premiers https://www.alpertron.com.ar/ECM.HTM
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. -
Pas mal alpertron, merci bien.
Effectivement, c'est relativement rapide par rapport au python, peut-être parce que python traite ligne par ligne, je ne sais pas. -
C++ est un langage compilé alors que Python est un langage interprété (il lit une ligne et l'exécute): le premier sera toujours plus rapide que le second. Avec Python et lorsqu'il y a des boucles, Numba compile le code dans la boucle à la première itération et itère avec le binaire, c'est une façon détournée de gagner en vitesse
-
Oui merci pour cette clarification
-
Lorsque $\dfrac{N-M}{N}$ est du même ordre de grandeur voire plus grand que $\dfrac{\ln(\ln(N))}{(\ln{N})^3}$ et si l'on dispose d'une grande quantité de mémoire accessible rapidement (de l'ordre de $N$ bits), il est sans doute plus efficace d'utiliser simplement un crible d'Ératosthène.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 21
+12 Invités