Oui, il y a encore à trouver en informatique
Par Celui le mercredi 28 novembre 2007, 22:43 - It works, bitches ! - Lien permanent
J'en ai marre qu'on me demande s'il y a encore quelque chose à trouver en informatique. Les âmes plus prudentes me demande s'il y a encore quelque chose de fondamental à trouver.
Je pourrais parler de P et d'NP, mais à quoi bon rentrer dans la théorie alors qu'il y a un exemple que tout le monde comprend : la multiplication. Parce que, accrochez-vous, on ne connaît pas l'algorithme le plus rapide[1] pour faire une multiplication.[2], ça va, c'est assez fondamental ?
Le meilleur algorithme connu, celui de Martin Fürer, date de février 2007. Il améliore l'algorithme de Schönage et Strassen de 1971. C'est vous dire si c'est compliqué. Puisqu'on y est, c'est pareil pour la division : on ne connaît pas non plus l'algorithme le plus rapide (mais sait comment le fabriquer à partir de celui de la multiplication).
Commentaires
Question d'un ignare total : c'est quoi "rapide"? (j'imagine que le temps que tourne un ordi n'est pas très rigoureux, surtout "asymptotiquement" donc cele ne doit pas être ça).
Ce n'est pas très rigoureux, mais c'est tout de même l'idée. On prend comme unité le nombre d'opérations élémentaires : additions de bits et multiplications de bits. L'algorithme naïf (algorithme CE2) est en O(n²), celui de Schönage et Strassen en O(n log(n) log(log(n))) et celui de Fürer en O(n log n 2^(log* n)). La question ouverte est : existe-t-il un algorithme en O(n log(n)) ?
Ensuite, dans la pratique, les processeurs modernes traitent des paquets de 32 ou 64 bits, mais ça ne change pas grand chose, juste des constantes cachées dans les grands O.
J'aimerai savoir s'il existe un programme en c ou un autre langage de programmation de la multiplication de martin FÜrer.
@Hamet, je ne crois pas. De l'aveu même de Martin Fürer que j'ai écouté en conférence en novembre, c'est inutile de mettre cet algorithme dans une bibliothèque de calcul. J'imagine cependant qu'il doit bien y avoir un proof-of-concept quelque part, et encore, je n'en suis pas sûr.
Il faudrait demander à des arithméticiens, ils sont bien plus au courant que moi de ce genre de développements.
boaf, comme ça pour le plaisir, l'IA, ça fait maintenant pas loin de 50 ans qu'on se casse les dents dessus (le chiffre est arbitraire, je sens le troll venir...)