Bonjour à tous et toutes, Puisqu'il n'y a pas de catégorie algorithmique sur ce forum, j'ai pensé poster dans la catégorie mathématique. J'ai un programme qui liste tous les diviseurs d'un nombre avec la méthode de décomposition en facteurs premiers. J'obtiens donc une suite de paires (facteur, exposant). Pour retrouver les diviseurs, j'utilise le principe du "compteur kilométrique" pour les obtenir. Cependant, ils ne sont pas trié en ordre ascendant. Quand il y a peu de diviseurs, n'importe quel algorithme de tri peut suffire. Mais si je traite de grands nombres de l'ordre de 10^12 par exemple, et que j'en traite beaucoup, ça peut devenir assez long à trier. Par exemple: 2^9 * 3^5 * 5^5 * 7^4 = 933508800000 qi possède 1800 diviseurs. Je remarque qu'il y a des sous-séquences ascendantes et je me demande s'il n'y aurait pas un tri plus rapide que le quicksort pour ce cas particulier. Je donne un exemple simple avec 60 = 2^2 * 3 * 5 : 1, 2, 4, 3, 6, 12, 5, 10, 20, 15, 30, 60 Ou bien un algorithme qui les liste tous en ordre ascendant sans passer par le compteur kilométrique. Merci pour toute idée ou suggestion.
edit: Si j'accepte de créer un tableau supplémentaire de la même longueur que celui qui n'est pas trié. Je peux savoir sa longueur en faisant le produit des "exposants+1" Je pourrais faire une fusion de ces sous-séquences ascendantes. On peut le faire avec un arbre binaire dont le niveau serait le log2 du nombre de sous-séquences. Pour optimiser, je pourrais trier en ordre descendant suivant l'exposant mes paires (facteur, exposant)
- Edité par PierrotLeFou 5 mars 2023 à 18:52:12
Le Tout est souvent plus grand que la somme de ses parties.
Bonjour Pierrot ! Tu es sûr que trier 1800 diviseurs est plus long que les obtenir ? Obtenir les facteurs premiers de 933 milliards et quelques me semble bien plus long, sans parler de les combiner ! (Mais je n'ai pas vérifié.)
Salut robun, Merci pour ta réponse. Pour la factorisation, je ne crois pas que cela soit très long. C'est surtout long pour le produit de grands nombres premiers. Ensuite, le nombre de facteurs premiers différents n'est pas si grand. C'en est même surprenant. Pour un entier non signé de 64 bits, on a au plus 15 facteurs premiers, et c'est 11 pour 10^12 et 9 pour un entier non signé de 32 bits. Puisque 10^12 vaut environ 2^39, je devrai au "maximum" faire 39 divisions pour obtenir tous les exposants. Dans mon exemple, j'en fait 9+5+5+4 = 23. Pour l'obtention des diviseurs, il y a bien sûr le parcours du "compteur kilométrique", mais il y a moyen d'optimiser. Au lieu d'évaluer par exemple 2^i * 3^j * 5^k * 7^l pour chaque "click" du compteur kilométrique, je ne fais qu'une multiplication, et une division par la puissance maximum à chaque retour à 0 de chaque exposant.
(j'évalue et je sauve cette puissance maximum dans la phase de factorisation) C'est proportionel au nombre de diviseurs, mais je n'ai pas testé le temps d'exécution. Est-ce que le facteur de proportionalité est élevé? Je ne sais pas.
- Edité par PierrotLeFou 6 mars 2023 à 2:12:06
Le Tout est souvent plus grand que la somme de ses parties.
Je me suis essayé avec de très grands nombres, par exemple: 12345678901234567 J'obtiens 2 facteurs et 4 diviseurs: 1 7 1763668414462081 12345678901234567 Inutile de dire que de trouver le second facteur prend beaucoup de temps. Cela m'a permis d'améliorer ma fonction de décomposition en facteurs premiers. Finalement, comme l'a mentionné robun, le temps de tri n'est pas si long par rapport au reste. Mon idée de fusionner les sous-séquences aurait une complexité temporelle en O(n log n) mais le temps pourrait être assez long. Et ça prend un autre tableau de la même longueur que le premier, en plus d'un tableau de longueur égale au nombre de sous-séquences pour implémenter un arbre binaire balancé pour les comparaisons. Il y a aussi le radix sort que je pourrais implémenter avec une base de 256 pour remplacer les divisions et les modulo par des décalages et des masques. J'aurais encore besoin d'un tableau de longueur 256 et d'un tableau de la même longueur que celui des diviseurs. Pour un nombre de l'ordre de 2^40, j'aurais besoin de 5 passages. Ce tri a une complexité temporelle de O(n) mais peut-être avec un coefficient élevé. Il y a des variantes qui utilisent la mémoire dynamique et qui sont plus rapides que d'autres. Je ferai peut-être des tests si possible pour ces alternatives, mais je crois que le quicksort est tout à fait satisfaisant.
Le Tout est souvent plus grand que la somme de ses parties.
J'obtiens 2 facteurs et 4 diviseurs: 1 7 1763668414462081 12345678901234567 Inutile de dire que de trouver le second facteur prend beaucoup de temps.
Pour trouver le second, il y a juste besoin d'une division, non (12345678901234567 / 7) ? Normalement, on ne cherche que les facteurs premiers inférieurs ou égaux à la racine carrée du nombre, ce n'est pas ce que tu as fait ?
Bien évidemment, je m'arrête à la racine carrée du nombre. Ici, le second facteur est de l'ordre de 10^16 et donc sa racine est de l'ordre de 10^8 Même en testant 8 nombres sur 30, ça fait tout de même plus de 10 millions (26.6M) de nombres à tester. Quand on fait la décomposition en facteurs premiers, on ne parle pas de la racine carrée du nombre d'origine mais de la racine du nombre résiduel après avoir éliminé un facteur. Et c'est ça entre autres que je traitais mal.
Je l'ai fait en C++ et j'avais des indices au début pour mon cycle d'incrémentation de 8 sur 30.
J'ai remplacé ça par des itérateurs.
Mon cycle à partir de 7 est : 4, 2, 4, 2, 4, 6, 2, 6
7 + 4 = 11, etc.
Les facteurs 2, 3, 5 sont testés au début.
- Edité par PierrotLeFou 8 mars 2023 à 18:26:24
Le Tout est souvent plus grand que la somme de ses parties.
Algorithme de tri particulier?
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.