Multiplikation in

Ich habe hier nachgesehen und festgestellt, dass die beste Laufzeit für die Multiplikation von zwei Bit-Zahlen O ( n ⋅ log n ⋅ 2 O ( log ∗ n ) ist , aber ich kann leicht einen Algorithmus feststellen, der in O ( n ⋅) ausgeführt wird log n ) .$n$$O(n\cdot \log n \cdot 2^{O(\log^* n)}$$O(n\cdot \log n)$

Schließlich wissen wir, wie man zwei Polynome vom Grad in der Laufzeit O ( n log n ) multipliziert . Das Multiplizieren von Polynomen ist jedoch dasselbe wie das Multiplizieren von zwei n- Bit-Zahlen. Wir haben also einen Algorithmus, um zwei n- Bit-Zahlen in O ( n log n ) zu multiplizieren . Das einzige Problem, das auftreten kann, ist der Übertrag, aber in jeder Phase können wir das in O ( n ) -Zeit beheben, indem wir einfach das am weitesten rechts stehende Bit und seinen linken Nachbarn bis zum Ende bewegen. Das heißt, unsere Laufzeit soll O bleiben ( n ⋅ log $n$$O(n \log n)$$n$$n$$O(n \log n )$$O(n)$ .$O(n \cdot \log n)$

Habe ich eine neue (und ziemlich offensichtliche) Entdeckung gemacht? Oder ist die Wikipedia-Seite veraltet? Oder habe ich vielleicht einen Fehler?

Wie @DavidRicherby bereits betont, entsteht die Verwirrung, weil verschiedene Komplexitätsmaße verwechselt werden. Aber lassen Sie mich etwas näher darauf eingehen.

Wenn man Algorithmen zur Polynommultiplikation über beliebige Ringe untersucht, interessiert man sich normalerweise für die Anzahl der arithmetischen Operationen in dem Ring, die ein Algorithmus verwendet. Insbesondere benötigt der Schönhage-Strassen-Algorithmus bei einigen (kommutativen, einheitlichen) Ringen und zwei Polynomen f , g ∈ R [ X ] mit einem Grad kleiner als n O ( n log n log log n ) Multiplikationen und Additionen in R. um f g ∈ R [ X ] zu berechnen$R$$f,g \in R[X]$$n$$O(n \log{n} \log{\log{n}})$$R$$fg \in R[X]$indem man ungefähr te primitive Wurzeln der Einheit an R anschließt , um einen größeren Ring D ⊃ R zu erhalten, und dann unter Verwendung der schnellen Fourier-Transformation über D das Produkt in D berechnet .$n$$R$$D \supset R$$D$$D$

Wenn Ihr Ring eine te Wurzel der Einheit enthält, kann dies mithilfe der schnellen Fourier-Transformation direkt über R auf O ( n log n ) -Operationen in R beschleunigt werden . Genauer gesagt, über Z ⊂ C können Sie dies mit O ( n log n ) -Ringoperationen tun (ohne die Tatsache zu berücksichtigen, dass dies eine genaue Arithmetik über die komplexen Zahlen erfordern würde).$n$$O(n \log n)$$R$$R$$\mathbb{Z} \subset \mathbb{C}$$O(n \log n)$

Die andere Maßnahme, die berücksichtigt werden kann, ist die Bitkomplexität einer Operation. Und das interessiert uns, wenn wir zwei ganze Zahlen der Bitlänge multiplizieren . Hier multiplizieren und addieren die primitiven Operationen zwei Ziffern (mit Übertrag). Wenn Sie also zwei Polynome mit Z multiplizieren , müssen Sie tatsächlich berücksichtigen, dass die während der Berechnung auftretenden Zahlen nicht mit einer konstanten Anzahl primitiver Operationen multipliziert werden können. Dies und die Tatsache, dass Z keine n- te primitive Einheitswurzel für n > 2 hat, hindert Sie daran, das O ( n log n ) anzuwenden.$n$$\mathbb{Z}$$\mathbb{Z}$$n$$n > 2$$O(n \log n)$Algorithmus. Sie dies überwinden durch Betrachtung mit den Koeffizienten aus dem Ring Z / ⟨ 2 n + 1 ⟩ , da die Koeffizienten des Polynoms Produkt wird das nicht gebundene überschreiten. Dort (wenn n eine Zweierpotenz ist) haben Sie (die Kongruenzklasse von) 2 als n- te Wurzel der Einheit, und indem Sie den Algorithmus für Koeffizientenmultiplikationen rekursiv aufrufen, können Sie insgesamt O ( n log n) erreichen log log n ) primitive (dh Bit-) Operationen. Dies überträgt sich dann auf die ganzzahlige Multiplikation.$f,g$$\mathbb{Z}/\langle 2^n + 1 \rangle$$n$$2$$n$$O(n \log n \log \log n)$

$f = \sum_{i=0}^n f_i X^i$$x \in \mathbb{Z}$

$f(x)$

$n$$n + \log n$

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

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