Cet algorithme est-il performant ?

Discutez d'informatique ici !
joel71
Messages: 6
Enregistré le: 25 Juil 2022, 16:56

Cet algorithme est-il performant ?

par joel71 » 25 Juil 2022, 17:25

Bonjour à tous
Je souhaiterais avoir votre avis.
J’ai codé un algorithme qui permet de savoir si un nombre est premier.
Il permet de déterminer un nombre de 10^19 en 1,8 seconde, de 10^20 en 39 secondes, 10^21 en 1 minute et 22 s et de 10^22 en 9 minutes.
J’aimerais savoir si cet algorithme est performant, si il a un intérêt quelconque.
Je le fais tourner sur un ordinateur de bureau avec Intel core i7 CPU 860 à 8,80 GHz x 4 et 8 Go de mémoire vive. Je l’ai programmé en Python avec Linux Mind sur Thonny.
Il a pour base le petit théorème de Fermat a^p congrue a modulo p. Les temps sont donnés pour a = 2.
Par exemple,pour un nombre de 10^20 il met pour a = 3 : 39 s, pour a = 325 : pour a = un nombre de 9 chiffres : 5 mn 45 s.
Merci d’avance pour votre réponse ou pour m’aiguiller vers une source qui serai en mesure de me répondre.



Saiga
Membre Naturel
Messages: 17
Enregistré le: 16 Juil 2021, 17:27

Re: Cet algorithme est-il performant ?

par Saiga » 03 Aoû 2022, 14:28

Salut,

c'est difficile d'évaluer l'efficacité d'un algorithme en se basant seulement sur quelques mesures.
- Tu ne décris pas précisément ton protocole : quand tu parles de déterminer un nombre de 10^19 en 1.8s, de quoi parles-tu exactement ? De déterminer si le premier nombre premier plus grand que 10^19 est effectivement premier ?
- Tu ne fournis que quelques mesures, dont certaines sont douteuses. Par exemple pour passer de 10^20 à 10^21 (complexité multipliée a priori par 10) ton temps d'exécution n'est multiplié que par 2. Quelque chose n'est pas correct. Tu faisais autre chose en même temps sur ton PC ? (Tu regardais des vidéos ?)
- Tu as implémenté ton algorithme en Python, qui est un langage interprété, probablement moins rapide que si tu l'avais implémenté dans un langage compilé. En plus il est (malheureusement) très facile de faire des erreurs de programmation qui péjorent nettement les performance. Une mauvaise gestion de la mémoire et la Ferrari se transforme en 2CV.
- Etc.

Tout ce que je peux dire :
- L'efficacité d'un algorithme se mesure généralement en complexité en temps (https://fr.wikipedia.org/wiki/Complexit%C3%A9_en_temps), laquelle est déterminée en analysant l'algorithme. Donc indépendamment de toute implémentation. Détermine la complexité en temps de ton algorithme et tu sauras s'il est efficace.
- Certains tests de primalité se basent effectivement sur le théorème de Fermat (https://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9). Donc l'idée de base semble intéressante.

joel71
Messages: 6
Enregistré le: 25 Juil 2022, 16:56

Re: Cet algorithme est-il performant ?

par joel71 » 05 Aoû 2022, 12:48

Bonjour Saiga,
Je te remercie pour ta réponse, en venant sur ce forum, c'est avec quelqu'un comme toi que je souhaitais entrer en contact, tu sais de quoi tu parles.
Je ne suis ni mathématicien ni informaticien mais cela fait un an que je m'intéresse aux nombres premiers et j'ai eu quelques idées que je n'ai pas vu sur internet (je sais bien que ce n'est pas pour ça qu'elles ne ont pas connues).
J'ai voulu les exploiter et j'ai pensé que le langage Python serait le meilleur moyen pour moi donc depuis environ 3 mois, j'ai appris le minimum nécessaire pour arriver à mon but.
Pour répondre à tes questions :
1) Je cherche à savoir si 10000000000000000001 et premier, cela se fait en 1,8s s'il ne l'est pas je passe à 100...03 puis 07 etc. Ainsi 10000000000000000019 est premier (ou pseudo-premier). Je peux aussi rechercher tous les nombres premiers entre 10^19 et 10^19+5000 (par exemple) soit 132 nombres premiers (ou pseudo) en 40mn ou entre 10^20 et 10^20+5000 soit 115 nombres premiers (ou pseudo) en 14h. Et 10^18 114 nombres premiers en 24 mn et 10^17 133 nombres premiers en 12 mn.
2) De passer de 10^20 à 10^21 en multipliant le temps que par moins que 10, je crois que c'est justement la force de mon algorithme. Je ne fais rien d'autre sur mon pc pendant le calcul et les temps sont totalement répétitifs.
3) Je vais me renseigner sur ce qu'est un langage interprété, je suis totalement ignorant en programmation!
Je serai content d'avoir transformé mon pc en 2CV, c'est que j'ai encore de la réserve...
Je veux bien poster mon algorithme mais ne suivant aucune règle du langage Python, j'ai peur que ceux qui vont le voir aient bien du mal à le comprendre.

joel71
Messages: 6
Enregistré le: 25 Juil 2022, 16:56

Re: Cet algorithme est-il performant ?

par joel71 » 11 Aoû 2022, 21:23

Bonjour,
Je désire réécrire mon algorithme en C mais ce langage est plus compliqué que le Python quand on part de zéro !
Je dois élever 2 à la puissance 10 000 ou plus et cela ne me posait pas de problème en Python.
Mais en C même si je met long long, ce n’est pas assez. J’ai regardé sur internet, j’ai vu qu’il fallait installer une bibliothèque pour utiliser des nombres sans limites. Je rame un peu (beaucoup) sur Linux. Ai-je d’autres solution ou dois-je m’y résoudre ? Je suis sur Linux Mind et j’utilise Code Blocks.
Merci de votre indulgence pour un débutant qui désire faire des choses hors de son domaine.

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 3 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite