Modul standard de înmulțire a două numere (sau polinoame) ia O (n 2) timp. Mai jos, vom descrie modul de reducere a timpului de multiplicare la O (n log n) folosind Fourier Jean Baptiste Joseph.
Trebuie remarcat faptul că în continuare luăm în considerare multiplicarea polinomilor, deoarece orice număr întreg poate fi reprezentat ca valoare a unui anumit polinom la un anumit punct. Pentru majoritatea sistemelor de numere, este convenabil să se ia baza sistemului ca acest punct (de exemplu, pentru un sistem zecimal acest punct va fi de 10). Apoi numărul lung va fi concatenarea coeficienților polinomului dorit, iar valoarea fiecărui coeficient va fi ne-negativă și mai mică decât baza sistemului. În același timp, numărul de coeficienți non-zero nu va depăși numărul de caractere din numărul inițial.
Reprezentarea polinomilor
Pentru început, definim noțiunea unei chei polinomiale pentru raționamente suplimentare. Polinomul A (x) al variabilei x pe câmpul F are forma:
A (x) = a 0 x 0 + a 1 x 1 + ... + a n -1 x n -1
Valorile aparțin câmpului F. Aceste valori se numesc coeficienții polinomului. Cel mai mare exponent în ceea ce privește coeficienții non-zero este numit gradul polinomului. Suma a două polinoame se va numi un polinom, fiecare coeficient al cărui coeficient este egal cu suma coeficienților corespondenți ai polinoamelor originale. Asta este, dacă
Rezultatul multiplicării a două polinoame este produsul lor - C (x) = A (x) B (x). Multiplicarea se realizează după cum urmează: fiecare termen al polinomului A (x) este multiplicat cu fiecare termen al B polinomului (x), atunci acționarea se execută termeni similari cu puteri egale.
aprobare
Gradul de produs polinomial este egal cu suma gradelor factorilor:
gradul (C) = gradul (A) + gradul (B)
Specificarea unui polinom prin vectorul coeficienților
Să se dea un polinom
atunci vectorul de coeficient va fi a = (a 0. a 1. ..., an).
Specificarea unui polinom printr-un set de valori
Fixăm n puncte distincte x 0. x 1. ..., x n -1. Un polinom A (x) cu grad mai mic decât n este determinat în mod unic de valorile sale în aceste puncte, adică de un set de perechi de n-argument-valoare.
unde yk = A (xk), pentru k = 0, 1, ..., n-1.
Reprezentarea polinom folosind valorile de la punctele predeterminate convenabile pentru multe operații: în special pentru multiplicarea polinoamelor este suficientă pentru a multiplica valoarea în fiecare dintre punctele (valori ale polinoamele trebuie specificate în aceleași locații). Cu toate acestea, trebuie să ținem cont de faptul că multiplicarea polinoame de grad sunt adăugate, iar produsul a două polinoame de grad mai mic de n poate avea un grad de mare n. Mai mult, se știe că este mai mică de 2 n. astfel încât 2 n puncte sunt suficiente pentru a reconstrui produsul. Astfel, înmulțirea a două polinoame cu un grad mai mic decât n. Este util încă de la început ca valorile polinomilor să nu fie în n. dar la 2 n puncte. Apoi, aceste valori pot fi multiplicate în timp O (n) și obțineți reprezentarea produsului sub forma unui set de perechi de argument-valoare.
Teorema (unicitatea interpolării)
Pentru orice set 0. y 0), (x 1 y 1), ..., (x n -1. Yn -1)> perechi valoare argument (x i totul diferit) există un polinom A unic (x) de grad mai mic de n. pentru care yk = A (xk), pentru k = 0, 1, ..., n-1.
Dovada. Această teoremă poate fi dovedită prin introducerea ecuației yk = A (xk) în forma matriceală.
Apoi, trebuie să verificăm faptul că determinantul unei matrice date care conține toate rădăcinile unui polinom este nenul, cu condiția ca toate xi să fie distincte. Rezultă că această matrice nu este degenerată. Și aceasta înseamnă că matricea este reversibilă. Cu alte cuvinte, putem găsi o coloană de coeficienți în coloana valorilor.
remarcă
Nu se poate dovedi această teoremă, ci pur și simplu se face referire la adevărul formulării de interpolare Lagrange.
Înmulțirea polinomilor
Dacă învăța să se deplaseze rapid pe coeficienții la valorile și înapoi, apoi pentru a se multiplica polinoame poate multiplica valoarea lor în punctele de date (coeficienții du-te la valorile multiplice, muta înapoi).
În acest caz, puteți utiliza orice set de puncte n, dar le alegeți într-un mod convenabil, puteți scurta timpul de conversie în ambele direcții în O (n log n). După cum vom vedea mai târziu, este convenabil să se ia ca puncte de rădăcini complexe ale unității, în acest caz, atât tranziția va fi redusă la așa-numita transformata Fourier discretă și inversa ei transformare, care ia O (n log n) operațiuni.
Reprezentăm schema de multiplicare a polinomilor dată de un vector de coeficienți.
Aici simbolurile ω i 2 n denotă rădăcinile complexe ale unității de gradul 2 n. ridicată la puterea lui i. Atunci când înmulțim două polinoame cu un grad mai mic decât n, obținem un polinom de grad mai mic de 2 n. prin urmare, pentru a începe, vom completa factorii polinomali cu coeficienți zero ai puterilor mai mari. După aceasta avem de-a face cu polinoame de grad mai mic de 2 n. și deci folosim rădăcini complexe de gradul 2 n din unitate, notat cu ω i 2 n pentru i = 0, 1, ..., 2 n -1.
Algoritmul de multiplicare rapidă a două polinoame poate fi scris după cum urmează:
- Dublarea numărului de coeficienți. Completăm polinomii A (x) și B (x) cu zero coeficienți de conducere, astfel încât numărul elementelor din fiecare polinom este 2 n elemente.
- Calculul valorilor. Folosind transformarea Fourier rapidă, se calculează valorile polinomilor A (x) și B (x) în punctele care sunt rădăcini de gradul 2 n din unitate.
- Înmulțirea Pontochechenoe. Înmulțiți punctual valorile obținute ale polinomilor A (x) și B (x) unul cu celălalt. Ca urmare, se obțin valorile polinomului C (x) = A (x) B (x) în rădăcinile gradului 2 n din unitate.
- Interpolarea. Obțineți coeficienții polinomului C (x) prin transformarea Fourier inversă.
Rădăcini complexe din unitate
rădăcini complexe de gradul n al unei unități numit un număr complex w care ω n = 1. Este evident că există exact n rădăcini complexe pentru această ecuație. Aceste rădăcini sunt distribuite uniform pe un cerc cu o rază de unitate centrat la zero, după cum se arată în ilustrația de mai jos.
Soluțiile ecuației ω n = 1 au forma exp (2π ik / n), pentru k = 0, 1, ..., n -1. Valoarea ω = exp (2π i / n) se numește valoarea principală a rădăcinii gradului n din unitate.
Introducem câteva afirmații auxiliare.
Lemma 1 (pe reducere)
Pentru orice număr întreg k ≥ 0, n ≥ 0, d> 0 este adevărat
Trimiteți-le prietenilor: