salut
je cherche à trouver un algorithme qui permet de décomposer un entier en facteurs premiers, mais j'arrive pas, pourriez vous m'aider a faire svp...
Algo : entiers
14 messages
- Page 1 sur 1
par c pi » 16 Nov 2006, 23:21
Bonsoir
Vaste problème déjà beaucoup étudié et ce n'est pas fini...
Tu trouveras quelques indications générales ici par exemple.
Des algorithmes à l'ouvrage sont utilisables en ligne, comme celui-ci et celui-là dont tu peux même télécharger le code source. :zen:
En lui mettant les mots "decomposition facteurs premiers algorithme" sous le nez, n'importe quel Yahoogle te reniflera mille pistes...
Vaste problème déjà beaucoup étudié et ce n'est pas fini...
Tu trouveras quelques indications générales ici par exemple.
Des algorithmes à l'ouvrage sont utilisables en ligne, comme celui-ci et celui-là dont tu peux même télécharger le code source. :zen:
En lui mettant les mots "decomposition facteurs premiers algorithme" sous le nez, n'importe quel Yahoogle te reniflera mille pistes...
par Arth » 16 Nov 2006, 23:25
En imaginant que tu ai défini racine carré et modulo ...
J'éspère que ça te seras utile
C'est la première fois que j'écris en langage algorithmique "impératif" ..... puisse ma prof être contente :ptdr:
- Code: Tout sélectionner
algorithme factorisation
variables
entier nombre
entier compteur
debut
compteur <- 2
lire(nombre)
tant que (compteur <= (racine carré(nombre)) faire
si ((nombre modulo compteur) = 0 ) alors
ecrire compteur
compteur <- compteur + 1
sinon
compteur <- compteur + 1
fin si
fin tant que
fin algorithme factorisation
J'éspère que ça te seras utile
C'est la première fois que j'écris en langage algorithmique "impératif" ..... puisse ma prof être contente :ptdr:
par anima » 17 Nov 2006, 21:43
Mohamed a écrit:merci bcp les amis
Je n'aime pas du tout le code de mon ami l'autre...Donc je vais tenter d'en faire un en PHP
par Arth » 18 Nov 2006, 00:11
Patastronch a écrit:Heuresement que les chercheurs font des algos moins naifs :p
tu l'aimes pas mon algo ?
par Patastronch » 18 Nov 2006, 03:22
ben il est faux surtout.
Ton algo ne factorise pas, il trouve les diviseurs. C'est pas la meme chose.
Mais admettons que ce soit une erreur d'inatention, si je te demande de me décomposer un nombre de l'ordre de 2^n ou n est relativement grand, ton algo n'arrivera jamais au bout (et cela que le nombre soit premier ou pas).
Donc au lieu de parcourir tous les nombre jusqu'a la racine, ne parcourir que les nombre premiers jusqu'a la racine fait deja gagner un temps considérable (mais suppose avoir une liste de nombre premier assez grande qui s'augmente grace a ce genre d'algorithme).
Ensuite la racine du nombre qui te sert de limite il faut le rabaisser des qu'un facteur est trouvé ainsi on réduit le temps d'execution pour les nombres non premier.
Il existe un tas de technique qui rendent possible la factorisation d'un nombre premier de grande taille, et cet algorithme que tu nous propose (en supposant qu'il soit corrigé pour qu'il soit juste) ne peut servir que pour des "petits" nombres.
Ton algo ne factorise pas, il trouve les diviseurs. C'est pas la meme chose.
Mais admettons que ce soit une erreur d'inatention, si je te demande de me décomposer un nombre de l'ordre de 2^n ou n est relativement grand, ton algo n'arrivera jamais au bout (et cela que le nombre soit premier ou pas).
Donc au lieu de parcourir tous les nombre jusqu'a la racine, ne parcourir que les nombre premiers jusqu'a la racine fait deja gagner un temps considérable (mais suppose avoir une liste de nombre premier assez grande qui s'augmente grace a ce genre d'algorithme).
Ensuite la racine du nombre qui te sert de limite il faut le rabaisser des qu'un facteur est trouvé ainsi on réduit le temps d'execution pour les nombres non premier.
Il existe un tas de technique qui rendent possible la factorisation d'un nombre premier de grande taille, et cet algorithme que tu nous propose (en supposant qu'il soit corrigé pour qu'il soit juste) ne peut servir que pour des "petits" nombres.
par Dominique Lefebvre » 18 Nov 2006, 12:13
Bonjour,
Il faut être indulgent (après tout cela semble être un lago de débutant)...
Les premiers algos. de factorisation sont assez anciens. Fermat en en a produit un, qui fonctionne par différence de deux carrés en 1643... Il a été souvent modifié, dernièrement par Lerman en 1974. Sur Google, tu devrais trouver tout ça.
Il y a aussi la méthode des résidus quadratiques de Gauss en 1801. Plus compliqué mais plus efficace.
Et aussi, la méthode de Legendre par les fractions continues ( 1798).
Si tu vas plus loin dans l'étude des algos disponibles, tu vas tomber sur les équations diophantiennes et l'équation de Pell-Fermat...
Bref, en cherchant dans Google sur ces bases, tu devrais trouver ton bonheur. Mais je te préviens: la factorisation d'un entier (sous-entendu en facteurs premiers) relève de la haute mathématique! Le théorème de Fermat, ça te rappelle quelque chose?
Il faut être indulgent (après tout cela semble être un lago de débutant)...
Les premiers algos. de factorisation sont assez anciens. Fermat en en a produit un, qui fonctionne par différence de deux carrés en 1643... Il a été souvent modifié, dernièrement par Lerman en 1974. Sur Google, tu devrais trouver tout ça.
Il y a aussi la méthode des résidus quadratiques de Gauss en 1801. Plus compliqué mais plus efficace.
Et aussi, la méthode de Legendre par les fractions continues ( 1798).
Si tu vas plus loin dans l'étude des algos disponibles, tu vas tomber sur les équations diophantiennes et l'équation de Pell-Fermat...
Bref, en cherchant dans Google sur ces bases, tu devrais trouver ton bonheur. Mais je te préviens: la factorisation d'un entier (sous-entendu en facteurs premiers) relève de la haute mathématique! Le théorème de Fermat, ça te rappelle quelque chose?
par Dominique Lefebvre » 18 Nov 2006, 12:15
Patastronch a écrit:Il existe un tas de technique qui rendent possible la factorisation d'un nombre premier de grande taille, et cet algorithme que tu nous propose (en supposant qu'il soit corrigé pour qu'il soit juste) ne peut servir que pour des "petits" nombres.
Bonjour,
On peut peut être aborder la notion de complexité algorithmique, tu ne crois pas? Sur cet exemple assez typique...
par Patastronch » 18 Nov 2006, 13:22
En effet la complexité algorithmique etant la motivation de la recherche pour ce probleme, il est tout a fait adéquat d'en parler ici. Je vous ferais un bref topo sur le sujet un peu plus tard (manque de temps la) a moins que Dominique (ou quelqu'un d'autre) ne s'y soit attelé.
Pour résumer Arth, ton algo est juste (si tu fais les modifs nécessaires) mais inutilisable pour cause de trop grand nombre de calculs, c'est en ce sens la qu'il est naif.
Pour résumer Arth, ton algo est juste (si tu fais les modifs nécessaires) mais inutilisable pour cause de trop grand nombre de calculs, c'est en ce sens la qu'il est naif.
par Dominique Lefebvre » 18 Nov 2006, 13:32
Patastronch a écrit:En effet la complexité algorithmique etant la motivation de la recherche pour ce probleme, il est tout a fait adéquat d'en parler ici. Je vous ferais un bref topo sur le sujet un peu plus tard (manque de temps la) a moins que Dominique (ou quelqu'un d'autre) ne s'y soit attelé.
Pour résumer Arth, ton algo est juste (si tu fais les modifs nécessaires) mais inutilisable pour cause de trop grand nombre de calculs, c'est en ce sens la qu'il est naif.
Dès que j'ai un moment ce WE, j'essais de présenter ça simplement...
par Arth » 18 Nov 2006, 16:19
Merci pour vos réponses.
Pour ma défense: je suis quelqu'un de très naïf :D
Bref, je suis asser interré par votre complexité algorithmique, j'ai hâte de pouvoir lire vos présentations.
Pour ma défense: je suis quelqu'un de très naïf :D
Bref, je suis asser interré par votre complexité algorithmique, j'ai hâte de pouvoir lire vos présentations.
par Dominique Lefebvre » 18 Nov 2006, 18:18
Bon, je vais essayer d'éclairer, du moins commencer à éclairer la notion de complexité.
Tout d'abord, il faut bien distinguer la complexité d'un algorithme de celle d'un problème (que je n'aborderai pas ici). La complexité d'un problème est la complexité du meilleur algorithme connu pour résoudre ce problème. Et donc, la complexité d'un problème est susceptible d'évoluer avec nos connaissances en algorithmique...
Il faut se rappeller qu'un algorithme présente deux caractéristiques fondamentales:
- le temps de calcul nécessaire pour le dérouler. Ce temps dépend du nombre d'opérations à effectuer et de la nature des opérations. Une addition est beaucoup plus rapidement exécutée qu'une multiplication... (rapport de 1 à 3 ou 4 au moins!). La limite tient donc dans le temps disponible! Et donc, pour un ordianteur, aussi de sa rapidité (fréquence CPU, architecture parallèle, bus inter-CPU, mémoire, etc.)
- la quantité de données à manipuler par l'algorithme. Cette quantité est limitée par la mémoire de travail de l'ordinateur, si on déroule l'algo. sur un ordinateur.
Donc, pour évaluer la complexité d'un algorithme, on cherche à mettre en évidence:
- le nombre d'opérations fondamentales (+, x) dans l'algo,
- une évaluation de la taille des données.
Il s'agit bien d'établir un ordre de grandeur de ces informations, dans le cas le plus défavorable du déroulement.
Il faut noter que la complexité d'un algo n'est pas lié au langage, au compilateur ou à la machine sur laquelle on l'exécute. C'est une caractéristique de l'algo.
Pour décrire la complexité, on utilise la notation O(), qui se lit "grand O".
On l'exprime en fonction de n, le nombre de données traitées par l'algorithme. En simplifiant à l'extrème, c'est une fonction qui donne un ordre de grandeur asymptotique de la complexité d'un algo.
Par exemple, on dira qu'un algo est de complexité O(n^2) lorsque on peut majorer le nombre d'opérations à n^2, dans le pire des cas.
Il existe des algos de complexité O(n), O(nlogn), O(2^n) et les pires O(n^n). Il est évident qu'un algo O(nlogn) vaut bien mieux qu'un algo de 2^n.
Exemple célèbre de réduction de complexité par la recherche: l'algo de calcul d'une transformée de Fourier. le calcul classique donne une complexité de O(n^2). Le calcul par l'algo de FFT donne une complexité de O(nlogn) où log est le log de base 2. C'est considérable!! Pour un PC qui travaille à 1 MFlop (10^6 opérations en virgule flottante par seconde), et pour n = 1 024 (c'est peu...), la différence va de 1 seconde pour O(nlogn) à plusieurs heures pour O(n^2)....
Une dernière chose: chercher la complexité d'un algo. sert surtout à comparer l'efficacité de plusieurs algos et choisir le meilleur...
Tout d'abord, il faut bien distinguer la complexité d'un algorithme de celle d'un problème (que je n'aborderai pas ici). La complexité d'un problème est la complexité du meilleur algorithme connu pour résoudre ce problème. Et donc, la complexité d'un problème est susceptible d'évoluer avec nos connaissances en algorithmique...
Il faut se rappeller qu'un algorithme présente deux caractéristiques fondamentales:
- le temps de calcul nécessaire pour le dérouler. Ce temps dépend du nombre d'opérations à effectuer et de la nature des opérations. Une addition est beaucoup plus rapidement exécutée qu'une multiplication... (rapport de 1 à 3 ou 4 au moins!). La limite tient donc dans le temps disponible! Et donc, pour un ordianteur, aussi de sa rapidité (fréquence CPU, architecture parallèle, bus inter-CPU, mémoire, etc.)
- la quantité de données à manipuler par l'algorithme. Cette quantité est limitée par la mémoire de travail de l'ordinateur, si on déroule l'algo. sur un ordinateur.
Donc, pour évaluer la complexité d'un algorithme, on cherche à mettre en évidence:
- le nombre d'opérations fondamentales (+, x) dans l'algo,
- une évaluation de la taille des données.
Il s'agit bien d'établir un ordre de grandeur de ces informations, dans le cas le plus défavorable du déroulement.
Il faut noter que la complexité d'un algo n'est pas lié au langage, au compilateur ou à la machine sur laquelle on l'exécute. C'est une caractéristique de l'algo.
Pour décrire la complexité, on utilise la notation O(), qui se lit "grand O".
On l'exprime en fonction de n, le nombre de données traitées par l'algorithme. En simplifiant à l'extrème, c'est une fonction qui donne un ordre de grandeur asymptotique de la complexité d'un algo.
Par exemple, on dira qu'un algo est de complexité O(n^2) lorsque on peut majorer le nombre d'opérations à n^2, dans le pire des cas.
Il existe des algos de complexité O(n), O(nlogn), O(2^n) et les pires O(n^n). Il est évident qu'un algo O(nlogn) vaut bien mieux qu'un algo de 2^n.
Exemple célèbre de réduction de complexité par la recherche: l'algo de calcul d'une transformée de Fourier. le calcul classique donne une complexité de O(n^2). Le calcul par l'algo de FFT donne une complexité de O(nlogn) où log est le log de base 2. C'est considérable!! Pour un PC qui travaille à 1 MFlop (10^6 opérations en virgule flottante par seconde), et pour n = 1 024 (c'est peu...), la différence va de 1 seconde pour O(nlogn) à plusieurs heures pour O(n^2)....
Une dernière chose: chercher la complexité d'un algo. sert surtout à comparer l'efficacité de plusieurs algos et choisir le meilleur...
14 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 11 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 ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :