Mnożenie w

10

Szukałem tutaj i zauważyłem, że najlepszym środowiskiem uruchomieniowym dla mnożenia dwóch liczb bitowych jest , ale łatwo mogę zauważyć algorytm działający w $n$ $O(n\cdot \log n \cdot 2^{O(\log^* n)}$ . $O(n\cdot \log n)$

W końcu wiemy, jak pomnożyć dwa wielomiany ze stopnia w środowisku wykonawczym . Ale pomnożenie wielomianów jest takie samo jak pomnożenie dwóch liczb bitowych. Mamy więc algorytm do pomnożenia dwóch liczb bitowych w . Teraz jedynym problemem, który może wystąpić, jest przeniesienie, ale w każdej fazie możemy to naprawić w czasie , po prostu przesuwając prawy bit i jego lewy sąsiad, aż do końca. Oznacza to, że nasze środowisko wykonawcze pozostanie $n$ $O(n \log n)$ $n$ $n$ $O(n \log n )$ $O(n)$ $O(n \cdot \log n)$ .

Czy zatem dokonałem nowego (i dość oczywistego) odkrycia? A może strona wikipedia jest nieaktualna? A może mam jakiś błąd?

runtime-analysis TheEmeritus
źródło

W jaki sposób „wiemy” „pomnożyć dwa wielomiany ze stopnia

w środowisku uruchomieniowym

”?

n

$n$

O (n \log n)

$O(n \log n)$

$\hspace{.46 in}$

8

Jak już wskazuje @DavidRicherby, zamieszanie powstaje, ponieważ różne pomiary złożoności ulegają pomieszaniu. Ale pozwól mi trochę rozwinąć.

Zwykle przy badaniu algorytmów mnożenia wielomianowego przez dowolne pierścienie interesuje nas liczba operacji arytmetycznych w pierścieniu, z których korzysta algorytm. W szczególności, biorąc pod uwagę pewien (przemienny, unitarny) pierścień i dwa wielomiany stopnia mniejszego niż , algorytm Schönhage-Strassen wymaga mnożenia i dodawania w w celu obliczenia $R$ $f,g \in R[X]$ $n$ $O(n \log{n} \log{\log{n}})$ $R$ $fg \in R[X]$ , z grubsza, sąsiednie - prymitywne korzenie jedności z $n$ trochę większy pierścień , a potem za pomocą szybkiej transformaty Fouriera na , obliczania artykuł . $R$ $D \supset R$ $D$ $D$

Jeśli pierścień zawiera -tego pierwiastka jedności, to można przyspieszyć do operacji w przy użyciu szybkiej transformacji Fouriera bezpośrednio na . Mówiąc dokładniej, powyżej można to zrobić za pomocą operacji pierścienia (ignorując fakt, że wymagałoby to dokładnej arytmetyki liczb zespolonych). $n$ $O(n \log n)$ $R$ $R$ $\mathbb{Z} \subset \mathbb{C}$ $O(n \log n)$

Inną miarą, którą można wziąć pod uwagę, jest złożoność operacji. I to nas interesuje, mnożąc dwie liczby całkowite o długości bitu . Tutaj podstawowe operacje mnożą się i dodają dwie cyfry (z przeniesieniem). Tak więc, mnożąc dwa wielomiany przez , należy wziąć pod uwagę fakt, że liczb powstających podczas obliczeń nie można pomnożyć za pomocą stałej liczby operacji pierwotnych. To i fakt, że nie ma prymitywnego pierwiastka jedności dla uniemożliwia zastosowanie $n$ $\mathbb{Z}$ $\mathbb{Z}$ $n$ $n > 2$ $O(n \log n)$ algorytmu . Przezwyciężyć przez rozważanie współczynnikach z pierścienia $f,g$ , Ponieważ współczynniki wielomianu produktu nie przekroczą tej granicy. Tam (gdy jest potęgą dwóch), masz (klasę zgodności) jako $\mathbb{Z}/\langle 2^n + 1 \rangle$ $n$ $2$ $n$ ty pierwiastek jedności, a rekurencyjnie wywołując algorytm mnożenia współczynników, możesz osiągnąć sumę pierwotne (czyli bit) operacje. To następnie przenosi się do mnożenia liczb całkowitych. $O(n \log n \log \log n)$

Na przykład, który ładnie podkreśla znaczenie różnicy między operacjami pierścieniowymi a operacjami pierwotnymi, rozważ dwie metody oceny wielomianów: metodę Hornera i metodę Estrina. Metoda Hornera ocenia wielomian przy pewnym poprzez wykorzystanie tożsamości $f = \sum_{i=0}^n f_i X^i$ $x \in \mathbb{Z}$ podczas gdy metoda Estrina dzieli na dwie części

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$

oraz

tj.

zawiera warunki stopnia

i

warunki stopnia

(zakładamy, że

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$

n

$n$ to potęga dwóch, dla uproszczenia).

Następnie możemy obliczyć za pomocą $f(x)$ i stosując algorytm rekurencyjnie.

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

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

Pierwszy z nich, wykorzystujący dodatków i mnożeń, okazał się optymalny pod względem liczby dodatków i mnożeń (czyli operacji pierścieniowych), drugi potrzebuje więcej (co najmniej ). $n$ $n + \log n$

$n/2$ $n/2$ $\Omega(n^2)$ $n$ $O(n)$ $O(n \log^c n) = \tilde{O}(n)$ $c > 0$

Marka Cornelius
źródło

9

$n$ $O(n\log n)$ $n$ $O(2^{\log^*n}n\log n)$ $n$ $O(n\log n)$

David Richerby
źródło

5

Nie sądzę, że to jest problem. Jeśli zastanowić numerami jak wielomianów których „X” jest podstawa, na przykład 2, wówczas Typowo można pomnożyć stopień zeruje wielomiany (cyfry mniejsze niż podstawa) w stałym czasie. Domyślam się, że problem polega na tym, że algorytm O (n * log n) używa FFT i asymptotycznie większe liczby mogą pojawiać się w algorytmie FFT.

jkff,

Mnożenie w

Odpowiedzi: