Nombre premiers
Re: Nombre premiers
C'était une blague -.-compol a écrit :Ah bon? J'aimerai bien avoir une démo si possible astucieuse ! (sans passer par l'ordi)
(Enfin une démo astucieuse serait d'utiliser Google pour avoir la liste des nombres premiers connus à ce jour, et de voir que les nombres en question de Dadin sont bien dans la liste, et en montrant que ces deux nombres sont biens distincts hein).
Re: Nombre premiers
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Nombre premiers
Par contre une vraie question d'algo et de complexité intéressante qui me travaille depuis tout à l'heure est : "peut-on faire mieux que l'algorithme d'Euclide" pour trouver le PGCD de deux nombres ?
Ce dernier travaille en temps linéaire en la taille de l'entrée (cas le pire avec les nombres de Fibonacci). Donc on ne risque pas de trouver mieux en puissance polynomiale (faut bien lire l'entrée, mais preuve rigoureuse ?), mais améliorer de façon conséquente la constante par un autre algo ?
Ce dernier travaille en temps linéaire en la taille de l'entrée (cas le pire avec les nombres de Fibonacci). Donc on ne risque pas de trouver mieux en puissance polynomiale (faut bien lire l'entrée, mais preuve rigoureuse ?), mais améliorer de façon conséquente la constante par un autre algo ?
Re: Nombre premiers
Apparemment y'a des trucs cools en base 2...
http://perso.ens-lyon.fr/damien.stehle/ ... slides.pdf
Pas forcément très compréhensible comme ça en le lisant vu que c'est un diaporama, mais ça doit donner quelques pistes et quelques références.
http://perso.ens-lyon.fr/damien.stehle/ ... slides.pdf
Pas forcément très compréhensible comme ça en le lisant vu que c'est un diaporama, mais ça doit donner quelques pistes et quelques références.
On peut dire que les fonctions convexes en dimension infinie et les fonctions continues en dimension finie sont d’une complexité similaire - Gilles Godefroy
http://perso.eleves.bretagne.ens-cachan.fr/~ldiet783/
http://perso.eleves.bretagne.ens-cachan.fr/~ldiet783/
Re: Nombre premiers
Dans l'absolu, La reponse est NON, on ne sait pas faire mieux depuis 2500 ans.Dadin a écrit :... "peut-on faire mieux que l'algorithme d'Euclide" pour trouver le PGCD de deux nombres ?
...?
La seule source fiable restera "Donald Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms".
Et c'est là que j'avais decouvert (il y a +sieurs années), la seule amélioration d'Euclide "pratique", proposée par un certain J. Stein: Computational problems associated with Racah algebra. Journal of Computational Physics, Vol. 1, No. 3, pp. 397–405, 1967.
Pour en savoir un peu plus : http://en.wikipedia.org/wiki/Binary_GCD_algorithm
Quand à:
C'est une plaisanterie... ... Trop de verbiage pour pas grand chose. Un algorithme pour être efficace, doit être facilement implémentable en pratique. S'il requiert une machine spécialisée, il perdra son interêt, à moins de ne s'interesser uniquement à l'evaluation théorique de la complexité.LB a écrit :Apparemment y'a des trucs cools en base 2...
http://perso.ens-lyon.fr/damien.stehle/ ... slides.pdf
Pour en dire un peu plus, L'algo peut être modifié pour le calcul des inverses modulaires.
A noter cependant une variante interessante est dans "B.S.Kaliski Jr. The Montgomery inverse and its applications".
Bonne lecture à tous ceux que la théorie et la pratique des nombres interesse.
Re: Nombre premiers
Ca date un peu comme référence. Volume 2, Seminumerical Algorithms (troisième édition 1997).
A l'époque le test de primalité n'était pas P.
Dans mathematica, ils font ça:
"GCD interleaves the HGCD algorithm, the Jebelean\[Dash]Sorenson\[Dash]Weber accelerated GCD algorithm, and a combination of Euclid's algorithm and an algorithm based on iterative removal of powers of 2."
A l'époque le test de primalité n'était pas P.
Dans mathematica, ils font ça:
"GCD interleaves the HGCD algorithm, the Jebelean\[Dash]Sorenson\[Dash]Weber accelerated GCD algorithm, and a combination of Euclid's algorithm and an algorithm based on iterative removal of powers of 2."
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Nombre premiers
Bien sur que ça date, n'empeche que ça reste la meilleure réference pour les applications pratiques. De toute les façons toutes les améliorations sont déduites de J. Stein, et la complexité théorique reste quadratique en le longueur des opérandes.fakbill a écrit :Ca date un peu comme référence. Volume 2, Seminumerical Algorithms (troisième édition 1997).
A l'époque le test de primalité n'était pas P.
Dans mathematica, ils font ça:
"GCD interleaves the HGCD algorithm, the Jebelean\[Dash]Sorenson\[Dash]Weber accelerated GCD algorithm, and a combination of Euclid's algorithm and an algorithm based on iterative removal of powers of 2."
Je ne connais pas la version de Jebelean, et je t'en dirai plus si j'arrive à me la procurer. De toute façon si tu as d'autres références, je suis preneur.
Le test de Primalité n'etait pas P, à l'epoque, mais dans la pratique, pour des raisons de performance on continue toujours avec les méthodes probabilistes qui fournissent un bon résultat tant que la conjecture de Riemman n'est pas infirmée. Mais sûr que le trio a fait avancer les choses dans ce domaine.
Re: Nombre premiers
Oui oui c'est la diférence entre la pratique et la théorie en algo.
En pratique, un facteur 2 c'est souvent la différence entre "acceptable" et "trop lent"....en théorie, on crie victoire quand on gagne une classe de complexité ou quand on réduit un peu un exposant...la constante est cachée dans le O
Même la multiplication rapide...je ne m'en sert jamais car je n'ai jamais besoin d'une précision infinie sur des entiers....mais c'est cool de savoir que ca existe.
En pratique, un facteur 2 c'est souvent la différence entre "acceptable" et "trop lent"....en théorie, on crie victoire quand on gagne une classe de complexité ou quand on réduit un peu un exposant...la constante est cachée dans le O
Même la multiplication rapide...je ne m'en sert jamais car je n'ai jamais besoin d'une précision infinie sur des entiers....mais c'est cool de savoir que ca existe.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Nombre premiers
L'algorithme en binaire est quand même un brin décevant, il s'agit du même algorithme que celui d'Euclide avec des astuces de calculs processeur. Mais merci quand même pour les différents liens !
nafpy : une autre conjecture (et, je trouve, la plus belle en théorie de la complexité) est que tout ce qui se fait en temps polynomial probabiliste ($ \mathbf{BPP} $) peut se faire en temps polynomial déterministe ($ \mathbf{P} $). Le fait que la primalité soit en fait $ \mathbf{P} $ n'était donc pas si surprenant !
fabkill : la multiplication rapide est quand même indispensable si l'on travail sur des grands entiers (à partir d'une vingtaine-trentaine de chiffres Karatsuba est vraiment mieux, et au delà d'une grosse cinquantaine FFT rulz). Après c'est sur que pour manipuler des entiers de 10 chiffres la multiplication naïve reste la plus efficace.
nafpy : une autre conjecture (et, je trouve, la plus belle en théorie de la complexité) est que tout ce qui se fait en temps polynomial probabiliste ($ \mathbf{BPP} $) peut se faire en temps polynomial déterministe ($ \mathbf{P} $). Le fait que la primalité soit en fait $ \mathbf{P} $ n'était donc pas si surprenant !
fabkill : la multiplication rapide est quand même indispensable si l'on travail sur des grands entiers (à partir d'une vingtaine-trentaine de chiffres Karatsuba est vraiment mieux, et au delà d'une grosse cinquantaine FFT rulz). Après c'est sur que pour manipuler des entiers de 10 chiffres la multiplication naïve reste la plus efficace.