Jak wybiera się pierścień wewnętrzny w algorytmie Schönhage – Strassen?

Próbowałem zaimplementować algorytm mnożenia liczb całkowitych Schönhage-Strassen, ale natknąłem się na przeszkodę w kroku rekurencyjnym.

I mają wartość o bitów i Aby obliczyć . Początkowo myślałem, że pomysł takiego, że , podziel na kawałki każdy za pomocą bitów, zastosuj splot SSA podczas pracy modulo , pierścień z bitami pojemności na wartość, a następnie złóż kawałki z powrotem. Jednak wyjście splotu ma nieco więcej niż bitów (tj.$x$$n$$x^2 \pmod {2^n+1}$$k$$4^k \geq 2n$$x$$2^k$$2^{k-1}$$2^{2^k}+1$$2^k$$2n$$>2^k$bitów na wartość wyjściową, która jest większa niż pojemność pierścienia, ponieważ każda wartość wyjściowa jest sumą kilku produktów), więc to nie działa. Musiałem dodać dodatkowy współczynnik 2 wypełnień.

Ten dodatkowy współczynnik 2 w wypełnieniu psuje złożoność. To sprawia, że ​​mój krok rekurencyjny jest zbyt drogi. Zamiast algorytmu kończę z algorytmem F (n) = n \ lg n + \ sqrt {n} F (4 \ sqrt {n}) = \ Theta (n \ lg ^ 2 n) .$F(n) = n \lg n + \sqrt{n} F(2 \sqrt{n}) = \Theta(n \; \lg n \; \lg \lg n)$$F(n) = n \lg n + \sqrt{n} F(4 \sqrt{n}) = \Theta(n \lg^2 n)$

Przeczytałem kilka odnośników z wikipedii, ale wszystkie wydają się rozmyślać o szczegółach rozwiązania tego problemu. Na przykład, mógłbym uniknąć dodatkowego narzutu, pracując modulo $2^{p 2^k} + 1$ dla $p$ który nie jest potęgą 2 ... ale potem wszystko się psuje później, kiedy mam tylko brak mocy z 2 pozostałych czynników i nie można zastosować Cooleya-Tukeya bez podwojenia liczby elementów. Ponadto $p$ może nie mieć multiplikatywnego odwrotnego modułu $2^p+1$ . Wciąż wprowadzane są czynniki wymuszone 2.

Jak wybrać pierścień do użycia podczas etapu rekurencyjnego, nie powodując asymptotycznej złożoności?

Lub w formie pseudokodu:

multiply_in_ring(a, b, n):
  ...
  // vvv                          vvv //
  // vvv HOW DOES THIS PART WORK? vvv //
  // vvv                          vvv //
  let inner_ring = convolution_ring_for_values_of_size(n);
  // ^^^                          ^^^ //
  // ^^^ HOW DOES THIS PART WORK? ^^^ //
  // ^^^                          ^^^ //

  let input_bits_per_piece = ceil(n / inner_ring.order);
  let piecesA = a.splitIntoNPiecesOfSize(inner_ring.order, input_bits_per_piece);
  let piecesB = b.splitIntoNPiecesOfSize(inner_ring.order, input_bits_per_piece);

  let piecesC = inner_ring.negacyclic_convolution(piecesA, piecesB);
  ...

Ta odpowiedź pochodzi z artykułu „Asymptotycznie szybkie algorytmy mnożenia i dzielenia liczbowego wielomianów o złożonych współczynnikach”, które Markus połączył w komentarzach.

---

Chcesz wyrównać $n$-bit liczba, modulo $2^n + 1$. Oto co robisz:

• Odnaleźć $p$ i $s$ które spełniają $n = (p-1) 2^s$ i $s \leq p \leq 2s$.

• Wybierz liczbę sztuk $2^m$ podzielić $n$ bitów w i odpowiednie parametry dla rozmiarów sztuk:

  $$\begin{align} m &= \lfloor s/2 \rfloor + 1 \\s_2 &= \lceil s/2 \rceil + 1 \\ p_2 &= \lceil p/2 \rceil + 1 \end{align}$$

  Zauważ, że $s_2$ i $p_2$ nadal spełnia $s_2 \leq p_2 \leq 2 s_2$niezmienny. Zauważ też, że$2^m 2^{s_2} p_2 \geq 2n + m + 1$ jest spełniony, więc dane wejściowe pasują do miejsca do przenoszenia.

• Wykonaj negacykliczny splot oparty na FFT na kawałkach, a resztę, jak zwykle.

Oto nadrzędny pomysł: logarytmiczny współczynnik wypełnienia $p$. Teraz do analizy złożoności. FFT zajmie$n m$ pracować do zrobienia, a my się powtarzamy $2^m$ kawałki wielkości $(p_2-1) 2^{s_2}$, więc teraz możemy zrobić wyjątkowo szorstką matematykę z wrt Relation Relt $s$:

$$\begin{align} F(s) &(\leq)\; (p-1)2^sm + 2^m F(\lceil s/2\rceil+1) \\ &(\leq)\; 2s2^s (\lfloor s/2\rfloor+1) + 2^{\lfloor s/2\rfloor+1} F(\lceil s/2\rceil+1) \\ &(\leq)\; s^2 2^s + 2 \cdot 2^{s/2} F(s/2+1) \\ &(\leq)\; s^2 2^s + 4 (s/2)^2 2^s + 16(s/4)^2 2^s + ... \\ &(\leq)\; 2^s s^2 \lg(s) \\ &(\leq)\; \frac{n}{\lg n} \left(\lg \frac{n}{\lg n}\right)^2 \lg \lg \frac{n}{\lg n} \\ &(\leq)\; \frac{n}{\lg n} (\lg^2 n) \lg \lg n \\ &(\leq)\; n \;(\lg n) \lg \lg n \end{align}$$

Co wydaje się słuszne, chociaż na tych etapach sporo zdradzałem.

„Sztuczka” wydaje się polegać na tym, że na tym kończymy $s^2$ zamiast $s$w koszcie podstawowym. Wciąż są dwa pomnożenia przez dwa na poziom rekurencyjny, tak jak narzekałem w pytaniu, ale teraz o połowę$s$płaci podwójne dywidendy, więc wszystko się udaje. Następnie na koniec anulujemy dodatkowy czynnik$s$ (co w rzeczywistości jest czynnikiem $\log n$) dzięki tworzeniu $p$ logarytmicznie duży w stosunku do $s$ początkowo.