Multiplication en

10

Je cherchais ici , et j'ai remarqué que le meilleur temps d'exécution pour la multiplication de deux nombres à bits est , mais je peux facilement remarquer un algorithme qui s'exécute dans . $n$ $O(n\cdot \log n \cdot 2^{O(\log^* n)}$ $O(n\cdot \log n)$

Après tout, nous savons comment multiplier deux polynômes à partir du degré dans l' exécution . Mais multiplier des polynômes revient à multiplier deux nombres à bits. Nous avons donc un algorithme pour multiplier deux nombres à bits dans . Maintenant, le seul problème qui pourrait se produire est le report, mais dans chaque phase, nous pouvons résoudre ce problème en temps , en déplaçant simplement le bit le plus à droite et son voisin gauche, jusqu'à la fin. Autrement dit, notre runtime doit rester . $n$ $O(n \log n)$ $n$ $n$ $O(n \log n )$ $O(n)$ $O(n \cdot \log n)$

Alors ai-je fait une nouvelle découverte (et assez évidente)? Ou la page wikipedia est-elle obsolète? Ou peut-être que j'ai une erreur?

runtime-analysis TheEmeritus
la source

Quelle est la façon dont "nous savons" "de multiplier deux polynômes à partir du degré dans l' exécution "?

n

$n$

O (n \log n)

$O(n \log n)$

$\hspace{.46 in}$

8

Comme le souligne déjà @DavidRicherby, la confusion vient du fait que différentes mesures de complexité se mélangent. Mais laissez-moi développer un peu.

Habituellement, lorsque l'on étudie les algorithmes de multiplication polynomiale sur des anneaux arbitraires, on s'intéresse au nombre d'opérations arithmétiques dans l'anneau qu'un algorithme utilise. En particulier, étant donné un anneau (commutatif, unitaire) et deux polynômes de degré inférieur à , l'algorithme de Schönhage-Strassen a besoin de multiplications et additions dans afin de calculer en, grosso modo, en attachant -èmes racines primitives d'unité à pour obtenir un anneau plus grand et ensuite, en utilisant le Fast Transformation de Fourier sur $R$ $f,g \in R[X]$ $n$ $O(n \log{n} \log{\log{n}})$ $R$ $fg \in R[X]$ $n$ $R$ $D \supset R$ $D$ , Le calcul du produit . $D$

Si votre bague contient une racine -ième de l' unité, cela peut être accéléré jusqu'à opérations dans en utilisant la transformée de Fourier rapide directement sur . Plus spécifiquement, sur , vous pouvez le faire en utilisant les opérations d'anneau (en ignorant le fait que cela nécessiterait une arithmétique exacte sur les nombres complexes). $n$ $O(n \log n)$ $R$ $R$ $\mathbb{Z} \subset \mathbb{C}$ $O(n \log n)$

L'autre mesure qui peut être prise en compte est la complexité en bits d'une opération. Et c'est ce qui nous intéresse en multipliant deux entiers de longueur de bit . Ici, les opérations primitives se multiplient et ajoutent deux chiffres (avec report). Ainsi, lorsque vous multipliez deux polynômes sur , vous devez réellement prendre en compte le fait que les nombres qui surviennent pendant le calcul ne peuvent pas être multipliés à l'aide d'un nombre constant d'opérations primitives. Ceci et le fait que ne possède pas de -ième racine primitive d'unité pour vous empêche d'appliquer l'algorithme . Vous surmontez cela en considérant $n$ $\mathbb{Z}$ $\mathbb{Z}$ $n$ $n > 2$ $O(n \log n)$ $f,g$ avec des coefficients de l'anneau , car les coefficients du polynôme produit ne dépasseront pas cette limite. Là (quand est une puissance de deux), vous avez (la classe de congruence de) comme -ième racine d'unité, et en appelant récursivement l'algorithme pour les multiplications de coefficient, vous pouvez obtenir un total de primitives (c'est-à-dire bit). Cela se transforme ensuite en multiplication entière. $\mathbb{Z}/\langle 2^n + 1 \rangle$ $n$ $2$ $n$ $O(n \log n \log \log n)$

Pour un exemple qui met bien en évidence l'importance de la différence entre les opérations en anneau et les opérations primitives, considérons deux méthodes pour évaluer les polynômes: la méthode de Horner et la méthode d'Estrin. La méthode de Horner évalue un polynôme à un certain en exploitant l'identité tandis que la méthode d'Estrin divise en deux parties et c'est-à-dire que contient les termes de degré et les termes de degré $f = \sum_{i=0}^n f_i X^i$ $x \in \mathbb{Z}$

f (x) = (\dots (f_{n} x + f_{n - 1}) x + \dots + \dots) + f_{0}

$f(x) = (\ldots (f_n x + f_{n-1})x + \ldots + \ldots) + f_0$

f

$f$

H = \sum_{i = 1}^{n / 2} f_{n / 2 + i} X^{i}

$H = \sum_{i=1}^{n/2} f_{n/2+i} X^i$

L = \sum_{i = 0}^{n / 2} f_{i} X^{i}

$L = \sum_{i=0}^{n/2} f_{i} X^i$

H

$H$

> n / 2

$>n/2$

L

$L$

\leq n / 2

$\leq n/2$ (supposons que est une puissance de deux, pour plus de simplicité).

n

$n$

Ensuite, nous pouvons calculer utilisant et en appliquant l'algorithme de manière récursive. $f(x)$

f (x) = H (x) x^{n / 2} + L (x)

$f(x) = H(x)x^{n/2} + L(x)$

Le premier, utilisant additions et multiplications, s'est avéré être optimal par rapport au nombre d'additions et de multiplications (c'est-à-dire les opérations en anneau), le second a besoin de plus (au moins ). $n$ $n + \log n$

Mais, au niveau des opérations sur les bits, on peut (assez facilement) montrer que dans le pire des cas, la méthode de Horner effectue multiplications de nombres de taille au moins , conduisant à plusieurs bits opérations (cela vaut même si nous supposons que deux nombres à bits peuvent être multipliés dans le temps ), alors que le schéma d'Estrin utilise pour certains , ce qui est de loin asymptotiquement plus rapide. $n/2$ $n/2$ $\Omega(n^2)$ $n$ $O(n)$ $O(n \log^c n) = \tilde{O}(n)$ $c > 0$

Marque Cornelius
la source

9

Dire que vous pouvez multiplier deux polynômes de degré dans le temps implique que, en particulier, vous pouvez multiplier des polynômes de degré zéro, c'est-à-dire des constantes, en temps constant. Il est donc clair que les affirmations "multiplier les nombres à bits prend du temps " et "multiplier les polynômes degré- prend du temps " sont relatives à différents modèles de calcul ne sont donc pas directement comparables. $n$ $O(n\log n)$ $n$ $O(2^{\log^*n}n\log n)$ $n$ $O(n\log n)$

David Richerby
la source

5

Je ne pense pas que ce soit le problème. Si nous considérons les nombres comme des polynômes dont le "x" est la base, par exemple 2, alors nous pouvons généralement multiplier les polynômes de degré zéro (nombres plus petits que la base) en temps constant. Je suppose que le problème est que l'algorithme O (n * log n) utilise la FFT et des nombres asymptotiquement plus grands peuvent émerger à l'intérieur de l'algorithme FFT.

jkff

Multiplication en

Réponses: