Site Web de Quadrature

Vous pouvez également consulter le site de la revue à l'adresse suivante :
http://www.quadrature.info/

mercredi 17 avril 2019

Complexité de la multiplication

Poser une multiplication de deux entiers de n chiffres selon la méthode babylonienne classique requiert n^2 (n au carré) multiplications élémentaires. En 1971 Schönhage et Strassen (aussi connu pour la multiplication rapide des matrices) en ont donné un algorithme plus rapide. Plus récemment, au mois de mars Joris van der Hoeven ( CNRS  École Polytechnique Computer Science Laboratory LIX) et David Harvey (University of New South Wales (Australia)) ont trouvé un algorithme qui effectue le produit d'entiers de taille n avec une complexité en O(n log n).
Leur travail est disponible ici

https://hal.archives-ouvertes.fr/hal-02070778

Aucun commentaire:

Publier un commentaire