Cet algorithme est-il performant ?

[joel71]

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]

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]

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]

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.

[Saiga]

Bonjour,

Je sais de quoi je parle, mais ça fait longtemps que je n'ai pas pratiqué le calcul de complexité et l'optimisation d'algorithmes

Concernant la différence entre langages compilés et interprétés :
- Dans le cas d'un langage compilé, tu écris du code (selon une certaine grammaire en général compréhensible par les humains), puis tu compiles c'est à dire qu'un compilateur va transformer ton code en binaire (compréhensible pour ton processeur), puis tu exécutes c'est à dire que le binaire est directement chargé en mémoire et le processeur exécute la première instruction, puis les suivantes jusqu'à l'arrêt du programme.
- Dans le cas d'un langage interprété, tu écris du code (toujours selon une certaine grammaire en général compréhensible par les humains), puis tu lances un interpréteur qui va prendre la première instruction, l'interpréter, c'est à dire demander au processeur d'effectuer un certain nombre d'opérations, puis l'interpréteur va prendre l'instruction suivante, et ainsi de suite.

Évidemment c'est une vue simplifiée, toujours est-il que les langages interprétés sont généralement plus souples (ça dépend de l'interpréteur), les langages compilés plus performants (si le compilateur a bien fait son boulot).

Le Python est un bon langage, souvent utilisé pour les maths ou l'intelligence artificielle. Avec le C tu entres de plein pied dans les langages compilés et les compilateurs sont très stricts sur la grammaire. Pas droit à l'erreur de codage sinon ça ne compile pas. En plus un caractère mal placé et le programme fait facilement n'importe quoi.

Apprendre les bases de la programmation c'est un cursus de 3 années. Donc il va te falloir pas mal de temps pour les acquérir par toi même.

Je ne connais Code::Blocks que de réputation (et ça fait longtemps que je n'ai pas fait de C). Ce que je peux dire c'est qu'effectivement 2^10 000 dépasse largement la limite de types prédéfinis (même ullong). Donc tu va devoir utiliser des bibliothèques (packages) spécifiques. Il faut les importer dans ton code avant de pouvoir les utiliser.

Attention : les opérations sur les grands entiers sont plus lentes que sur les types prédéfinis. Mais bon, s'il n'y a pas le choix, alors il n'y a pas le choix.

[joel71]

Bonjour,

Merci Saiga pour tes explications très claires.

J’ai pratiqué un peu le C, pour programmer des platines Arduino (je suis électronicien de formation), mais c’est du C simplifié à l’extrême.
je pense également qu’il va me falloir pas mal de temps pour réécrire mon algorithme en C.

Pour mon algorithme, j’utilise comme point de départ le petit théorème de Fermat mais pour aller jusqu’à de grands nombres, j’ai divisé certaines instructions en « étapes ».
Par exemple pour 10^22, il y a 10^9 étapes, j’utilise la boucle while qui « tourne » 10^9 fois mais avec des nombres proportionnellement plus petits.

Si j’ai bien compris, avec un langage interprété il va réinterpréter à chaque fois les quelques instructions qui sont dans la boucle, donc 10^9 fois.
Tandis qu’en langage compilé, il compile une bonne fois au début (si j’ose dire) et il exécute les instructions.
Donc dans ce cas le langage compilé ira beaucoup plus vite mais si je met peu d’instructions avec de gros nombres, ce sera à peu prêt pareil pour les 2 langages.
Est-ce bien cela ? Dis mois si je me trompe.

Joël

[Saiga]

Salut,

les interpréteurs sont en général truffés d'optimisations. Donc quand ils détectent plusieurs fois la même instruction, il ne vont pas nécessairement réinterpréter à chaque fois.
Il n'empêche que l'interpréteur consomme des ressources (CPU, RAM, etc.) donc un même algorithme, quelle que soit sa complexité, aura (normalement) un temps d'exécution plus court s'il est compilé que s'il est interprété.

Après, en fonction de l'algorithme (et de son implémentation), la différence est parfois négligeable, d'autres fois considérable. Plus que la taille des nombres, je pense que la taille des boucles (nombre d'instructions dans chaque boucle) joue un rôle important. Mais dans tous les cas, c'est difficile à prévoir.