Complexité de la multiplication dans $N$
Bonjour,
je prépare l’oral de l’option C de l’agrégation (algèbre effective).
Dans son Cours d’algèbre, Michel Demazure dit que la complexité de la multiplication de deux entiers $n$ et $n’$ est en $O(log(n)log(n’))$ opérations binaires.
À côté de ça je vois sur internet que les meilleurs algorithmes connus à ce jour pour la multiplication de deux entiers plus petits que $N$ sont en $O(Nlog(N))$ , ce qui est moins bien...
Quelqu’un peut-il m’expliquer s’il vous plaît ?
je prépare l’oral de l’option C de l’agrégation (algèbre effective).
Dans son Cours d’algèbre, Michel Demazure dit que la complexité de la multiplication de deux entiers $n$ et $n’$ est en $O(log(n)log(n’))$ opérations binaires.
À côté de ça je vois sur internet que les meilleurs algorithmes connus à ce jour pour la multiplication de deux entiers plus petits que $N$ sont en $O(Nlog(N))$ , ce qui est moins bien...
Quelqu’un peut-il m’expliquer s’il vous plaît ?
Réponses
-
Je n'y connais rien, mais $O\big(n \cdot \ln(n)\big)$ est complètement délirant.
Pour multiplier ensemble deux entiers $\le $ un milliard, faut-il un milliards d'opérations ?
La première m'a l'air plus vraisemblable : $\ln(n)$ est l'ordre de grandeur du nombre de chiffres. -
https://fr.m.wikipedia.org/wiki/Algorithme_de_Fürer
Un algorithme relativement récent et qui n’est même pas aussi bien que $Nlog(N)$ apparemment.
Édit : je n’arrive pas à faire fonctionner le lien.
Rechercher Algorithme de Fürer sur Wikipedia
[Correction du lien. AD] -
J'ai l'impression que les sources de Liedeberg ne mesurent pas la même chose : Demazure utilise la taille $n$ des nombres à multiplier, les autres appellent $N$ le nombre de chiffres des nombres que l'on multiplie.
-
!! En effet je crois que ça n’est que ça.
Merci beaucoup marsup et math coss ! -
Bonjour.
En appelant n le nombre et N =O(ln(n)) le nombre de chiffres, on voit que Demazure parle de l'algorithme naïf de multiplication (pour multiplier deux nombres à N et N' chiffres, on met un temps proportionnel à NN', puisqu'on multiplie chaque chiffre de l'un à tous les chiffres de l'autre. On connaît effectivement des algorithmes bien plus efficaces.
Cordialement -
Plus efficaces pour les grands nombres entiers bien sûr.Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
Bon j’en profite pour poser une autre question :
Je connais la complexité de l’algorithme d’Euclide étendu pour deux entiers ou deux polynômes.
Je voudrais savoir quelle est la complexité de l’algorithme d’Euclide étendu pour un nombre quelconque d’entiers ou de polynômes. Pour l’appliquer entre autre aux restes chinois.
Je ne trouve rien dans mes livres ou sur internet.
Merci par avance
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 2
2 Invités