Można to zrobić w O(n log n) czasie arbitralnego P i Q stopnia n. Dokładniej można to zrobić w M(n), gdzie M(n) jest złożonością multiplikacji wielomianowej, która sama może być wykonana w O(n log n).
Po pierwsze, pierwsze rozszerzenia serii można zobaczyć po prostu jako wielomian stopnia n-1.
Załóżmy, że interesują Cię pierwsze warunki rozszerzenia serii n o rozszerzenie serii o P(x)/Q(x). Istnieje algorytm, który obliczy odwrotność czasu Q w M(n), jak zdefiniowano powyżej.
Odwrócony T(x) z Q(x) spełnia T(x) * Q(x) = 1 + O(x^N). To znaczy. T(x) * Q(x) to dokładnie 1 oraz pewne pojęcie błędu, którego współczynniki występują po pierwszych terminach n, którymi jesteśmy zainteresowani, więc możemy je po prostu upuścić.
Teraz P(x)/Q(x) jest po prostu P(x) * T(x) co jest kolejnym mnożnikiem wielomianu.
Możesz znaleźć implementację, która oblicza wspomnianą odwrotność w mojej bibliotece open source Altruct. Zobacz plik series.h. Zakładając, że masz już metodę, która oblicza iloczyn dwóch polinomials, kod, który oblicza odwrotność, ma długość około 10 linii (wariant dziel i rządź).
Rzeczywisty algorytm wygląda następująco: Załóżmy Q(x) = 1 + a1*x + a2*x^2 + .... Jeśli a0 nie jest 1, można po prostu podzielić Q(x), a później jego odwrotną T(x) z a0. Załóżmy, że na każdym etapie masz warunki odwrotne, aby Q(x) * T_L(x) = 1 + x^L * E_L(x) dla niektórych błędów E_L(x). Początkowo T_1(X) = 1. Jeśli podłączysz to w powyższym, otrzymasz Q(x) * T_1(x) = Q(x) = 1 + x^1 * E_1(x) dla niektórych E_1(x), co oznacza, że dotyczy to L=1. Teraz podwójmy L w każdym kroku. Możesz uzyskać E_L(x) z poprzedniego kroku jako E_L(x) = (Q(x) * T_L(x) - 1)/x^L, lub pod względem implementacji, po prostu upuść pierwsze współczynniki L produktu. Następnie można obliczyć T_2L(x) z poprzedniego kroku jako T_2L(x) = T_L(x) - x^L * E_L(x) * T_L(x). Błąd będzie następujący: E_2L(x) = - E_L(x)^2.Sprawdźmy teraz, czy krok indukcyjny się utrzymuje.
Q(x) * T_2L(x)
= Q(x) * (T_L(x) - x^L * E_L(x) * T_L(x))
= Q(x) * T_L(x) * (1 - x^L * E_L(x))
= (1 + x^L * E_L(x)) * (1 - x^L * E_L(x))
= 1^2 - (x^L * E_L(x))^2
= 1 + x^2L * E_2L(x)
Q.E.D.
jestem pewien, że nie jest możliwe, aby obliczyć wielomian podział bardziej wydajny niż mnożenia, a jak widać w poniższej tabeli, ten algorytm jest tylko 3 razy wolniej niż jednym mnożenia:
n mul inv factor
10^4 24 ms 80 ms 3,33x
10^5 318 ms 950 ms 2,99x
10^6 4.162 ms 12.258 ms 2,95x
10^7 101.119 ms 294.894 ms 2,92x
@ DavidEisenstat Dzięki, to upraszcza zadanie. Ale jak mogę znaleźć '1/Q (x)' z długim podziałem? Myślałem, że z podziałem znajduję tylko iloraz i pozostałość. – Somnium
@DavidEisenstat Dzięki! Unikanie separacji przyspieszy również rzeczy, ponieważ mnożenie będzie wynosiło * O (n * m) *, gdzie n - liczba terminów, m - stopień. Nawiasem mówiąc, nie rozumiem, dlaczego moja odpowiedź jest oznaczona jako zbyt szeroka, że wymaga jednego określonego algorytmu. – Somnium
@DavidEisenstat Idź tam :) Może powinniśmy rozpocząć temat o stanie [algorytmu] na meta. Jest zdecydowanie kilka ogólnych decyzji, które należy podjąć, aby przesłać te pytania do CS –