Discussion :

[Tatsumasaf]

Bonjour,
j'ai découvert un nouvel algorithme dans un domaine que je ne tient pas à révéler avant d'avoir publié l'algorithme de façon légale qui est plus efficace que ceux indiqués sur wikipédia sur le sujet. (Certes il peut y en avoir d'autres qui ont été découvert depuis)

Je suis en train de coder le programme pour vérifier par l'expérience que mes calculs de complexité ne sont pas erroné et je souhaiterais connaître les possibilités légales pour publier un nouvel algorithme.

Merci à ceux qui répondront.

[Biribibi]

Bonjour,

pourrait-on savoir quel est le problème au quel tu t'es intéressé et quelles sont les bornes de complexité que tu estimes à avoir trouvé ?

Dans tous les cas, Wikipédia n'est pas du tout une référence si tu veux être au courant des dernières avancées sur un domaine.

[Tatsumasaf]

Trouver tous les nombres premiers inférieurs à N.
J'ai un algorithme de complexité en O(N) alors que si j'ai bien compris ce qui est dit sur wikipedia l'algo utilisé au moment de l'article était en N*O(exp[(64/9 log n)^(1/3)) * (log log n)^2/3].

à noter que la complexité de mon algorithme en espace est aussi en O(N).

Bon je n'ai pas encore fini de coder l'algorithme pour faire des tests et vérifier sa complexité, et la complexité annoncé est en considérant que les opérations connues se font en temps fixe alors que même pour une simple multiplication il faut tenir compte de la propagation de la retenue si on travaille sur des très grands nombres.

[Biribibi]

Il semble qu'un algorithme en temps O(N) soit connu depuis 1983:
Fast compact prime number sieves (among others), Paul Pritchard,
Journal of Algorithms Volume 4, Issue 4, December 1983, Pages 332-344
http://www.sciencedirect.com/science...378c3e447576d6

Depuis, il a été trouvé des algorithmes de complexité inférieure
Prime sieves using binary quadratic forms, A. O. L. ATKIN AND D. J. BERNSTEIN, Mathematics of Computation 73 (2004), pp. 1023–1030
http://www.ams.org/mcom/2004-73-246/...03-01501-1.pdf

[Tatsumasaf]

Merci de la réponse, je suis en train de lire les articles et d'essayer de les comprendre. (faire à la fois la traduction et comprendre le sens n'est pas simple)