Transformata Fourier rapidă (FFT) este un element cheie în mulți algoritmi, inclusiv multiplicarea numerelor mari și multiplicarea polinoamelor. Transformatele Fourier au, de asemenea, aplicații importante în procesarea semnalului, mecanica cuantică și alte domenii și ajută la realizarea unor părți semnificative ale economiei globale. Vom vorbi despre două operații diferite: evaluarea polinomială în mai multe puncte (evaluarea unui grad) și interpolare inversă, polinomială a acestuia (date fiind evaluările unui grad

Avertisment declanșator: subiect matematic specializat

Mulțumiri speciale lui Karl Floersch pentru feedback

Unul dintre algoritmii mai interesanți din teoria numerelor este transformata Fast Fourier (FFT). FFT-urile reprezintă un element cheie în mulți algoritmi, inclusiv multiplicarea extrem de rapidă a numerelor mari, multiplicarea polinoamelor și generarea și recuperarea extrem de rapidă a codurile de ștergere.

Codurile de ștergere în special sunt extrem de versatile; pe lângă cazurile lor de utilizare de bază în stocarea și recuperarea datelor care tolerează defecțiunile, codurile de ștergere au și cazuri de utilizare mai avansate, cum ar fi asigurarea disponibilității datelor în blockchain-uri scalabile și STARK-uri. Acest articol va analiza ce sunt transformatele Fourier rapide și cum funcționează unii dintre algoritmii mai simpli pentru calculul acestora.

Context

Bine, transformatele Fourier au, de asemenea, aplicații cu adevărat importante în procesarea semnalului, mecanica cuantică și alte domenii și ajută la realizarea unor părți semnificative ale economiei globale. Dar haide, elefanții sunt mai cool.

Originală Transformată Fourier este o operație matematică care este adesea descrisă ca convertind date între „domeniul frecvenței” și „domeniul timpului”. Ceea ce înseamnă asta mai precis este că, dacă aveți o bucată de date, atunci rularea algoritmului ar veni cu o colecție de unde sinusoidale cu frecvențe și amplitudini diferite care, dacă le-ați adăuga, ar aproxima datele originale. Transformatele Fourier pot fi utilizate pentru lucruri minunate precum exprimând orbite pătrate prin epicicluri și derivând un set de ecuații care pot desena un elefant:

Tipul de transformată Fourier despre care vom vorbi în acest post este un algoritm similar, cu excepția locului în loc să fie un continuu Transformarea Fourier peste numere reale sau complexe, e o transformată Fourier discretă peste câmpuri finite (vezi secțiunea „Un interludiu modular de matematică” aici pentru o reîmprospătare a ceea ce sunt câmpurile finite).

În loc să vorbim despre conversia între „domeniul frecvenței” și „domeniul timpului”, aici vom vorbi despre două operații diferite: evaluare polinomială în mai multe puncte (evaluarea unui grad <N polinom la N diferite puncte) și inversul său, interpolare polinomială (având în vedere evaluările unui grad <N polinom la N puncte diferite, recuperând polinomul). De exemplu, dacă operăm în câmpul primar cu modulul 5, atunci polinomul y = x² + 3 (pentru comoditate, putem scrie coeficienții în ordine crescătoare: [3,0,1]) evaluat la puncte [0,1,2] dă valorile [3,4,2] (nu [3,4,7] deoarece operăm într-un câmp finit în care numerele se învârt la 5) și putem efectua evaluările [3,4,2] și coordonatele la care au fost evaluate ([0,1,2]) pentru a recupera polinomul original [3,0,1].

Există algoritmi atât pentru evaluarea în mai multe puncte, cât și pentru interpolare, care pot face oricare dintre operațiuni O (N²) timp. Evaluarea în mai multe puncte este simplă: evaluați separat polinomul în fiecare punct. Iată codul Python pentru a face acest lucru:

def eval_poly_at(self, poly, x, modulus): y = 0 power_of_x = 1 for coefficient in poly: y += power_of_x * coefficient power_of_x *= x return y % modulus

Algoritmul rulează o buclă care trece prin fiecare coeficient și face un lucru pentru fiecare coeficient, deci rulează în PE) timp. Evaluarea în mai multe puncte implică efectuarea acestei evaluări la N puncte diferite, deci timpul total de rulare este O (N²).

Interpolarea Lagrange este mai complicată (căutați „Interpolare Lagrange” aici pentru o explicație mai detaliată). Elementul cheie al strategiei de bază este acela pentru orice domeniu D și punct x, putem construi un polinom care revine 1 pentru x și 0 pentru orice valoare în D altele decât x. De exemplu, dacă D=[1,2,3,4] și x=1, polinomul este:

Vă puteți conecta mental 1, 2, 3 și 4 la expresia de mai sus și verificați dacă revine 1 pentru x=1 și 0 în celelalte trei cazuri.

Putem recupera polinomul care dă orice set dorit de ieșiri pe domeniul dat prin multiplicarea și adăugarea acestor polinoame. Dacă numim polinomul de mai sus P1, și cele echivalente pentru x = 2, x = 3, x = 4, P2, P3 și P4, apoi polinomul care revine [3,1,4,1] pe domeniu [1,2,3,4] este pur și simplu 3⋅P1+P2+4⋅P3+P4. Calculul polinoamelor Pi necesită PE²) time (construiți mai întâi polinomul care revine la 0 pe întregul domeniu, care necesită O (N²) timp, apoi îl împărțiți separat (x − xi) pentru fiecare xi), iar calculul combinației liniare durează altul O (N²) timpul, așa că este O (N²) timpul total de rulare.

Transformate Fourier rapide

Există un preț pe care trebuie să-l plătiți pentru utilizarea acestui algoritm mult mai rapid, și anume că nu puteți alege niciun câmp arbitrar și niciun domeniu arbitrar. În timp ce, cu interpolare Lagrange, puteți alege orice coordonate x și y coordonate doriți și orice câmp doriți (ați putea să o faceți chiar și peste numere reale vechi simple) și puteți obține un polinom care trece prin ele., Cu un FFT , trebuie să utilizați un câmp finit, iar domeniul trebuie să fie un subgrup multiplicativ a câmpului (adică o listă de puteri de o anumită valoare „generator”).

De exemplu, puteți utiliza câmpul finit al numărului întreg modulo 337, și pentru utilizarea domeniului [1,85,148,111,336,252,189,226] (aceasta este puterea 85 pe teren, de ex. 85 ^ 3% 337 = 111; se oprește la 226 pentru că următoarea putere a 85 revine la 1). Mai mult, subgrupul multiplicativ trebuie să aibă dimensiune 2n (există modalități de a-l face să funcționeze pentru numerele formularului 2 ^ m⋅3 ^ n și, eventual, puteri prime puțin mai mari, dar apoi devine mult mai complicat și ineficient). Câmpul finit al intergerelor modulo 59, de exemplu, nu ar funcționa, deoarece există doar subgrupuri multiplicative de ordine 2, 29 și 58; 2 este prea mic pentru a fi interesant, iar factorul 29 este mult prea mare pentru a fi compatibil cu FFT. Simetria care provine din grupuri multiplicative de mărime 2 ^ n ne permite să creăm un algoritm recursiv care să calculeze destul de inteligent rezultatele de care avem nevoie dintr-o cantitate mult mai mică de muncă.

Pentru a înțelege algoritmul și de ce are un timp de rulare redus, este important să înțelegem conceptul general de recursivitate. Un algoritm recursiv este un algoritm care are două cazuri: un „caz de bază” în care intrarea în algoritm este suficient de mică încât să puteți da ieșirea în mod direct și „caz recursiv” în care calculul necesar constă dintr-un „calcul adeziv” plus una sau mai multe utilizări ale aceluiași algoritm la intrări mai mici. De exemplu, este posibil să fi văzut algoritmi recursivi folosind pentru sortarea listelor. Dacă aveți o listă (de ex. [1,8,7,4,5,6,3,2,9]), apoi îl puteți sorta folosind următoarea procedură:

• Dacă intrarea are un element, atunci este deja „sortată”, astfel încât să puteți returna intrarea.

• Dacă intrarea are mai mult de un element, atunci sortați separat prima jumătate a listei și a doua jumătate a listei, apoi îmbinați cele două sub-liste sortate (numiți-le A și B) după cum urmează. Păstrați două ghișee, după și bpos, ambele începând de la zero și mențin o listă de ieșire, care începe goală. Până la oricare după or bpos este la sfârșitul listei corespunzătoare, verificați dacă A[apos] or B[bpos] este mai mic. Orice dintre acestea este mai mic, adăugați acea valoare la sfârșitul listei de ieșire și măriți contorul cu 1. Odată ce ați făcut acest lucru, adăugați restul oricărei liste care nu a fost complet procesată la sfârșitul listei de ieșire și returnați ieșirea listă.

Rețineți că „lipiciul” din a doua procedură are timp de rulare PE): dacă fiecare dintre cele două sub-liste are N elemente, atunci trebuie să parcurgeți fiecare articol din fiecare listă o dată, așa este PE) calcul total. Deci algoritmul ca întreg funcționează luând o problemă de dimensiune N, și împărțirea în două probleme de dimensiune N2, Plus PE) de execuție „lipici”.

Există o teoremă numită Teorema Maestrului care ne permite să calculăm timpul total de rulare al algoritmilor ca acesta. Are multe sub-cazuri, dar în cazul în care împărțiți o execuție de dimensiunea N în k sub-cazuri de dimensiune N / k cu PE) lipici (așa cum este cazul aici), rezultatul este că executarea durează O (N⋅log (N)).

Un FFT funcționează în același mod. Luăm o problemă de mărime N, împărțiți-l în două probleme de dimensiune N2, si fa PE) lucrul cu lipici pentru a combina soluțiile mai mici într-o soluție mai mare, așa că obținem O (N⋅log (N)) timpul total de rulare - mult mai repede decât O (N2). Iată cum o facem. Voi descrie mai întâi cum se folosește un FFT pentru evaluarea în mai multe puncte (adică pentru un anumit domeniu D și polinom P, calculati P (x) pentru fiecare x in D), și se dovedește că puteți utiliza același algoritm pentru interpolare cu o modificare mică.

Să presupunem că avem un FFT în care domeniul dat este puterile lui x în vreun domeniu, unde x ^ 2 ^ k = 1 (de exemplu, în cazul pe care l-am introdus mai sus, domeniul este puterile 85 formă 337, și 85 ^ 2 ^ 3 = 1). Avem ceva polinom, de ex. y=6×7+2×6+9×5+5×4+x3+4×2+x+3 (o vom scrie ca p = [3,1,4,1,5,9,2,6]). Vrem să evaluăm acest polinom în fiecare punct al domeniului, adică. la fiecare dintre cele opt puteri ale 85. Iată ce facem.

În primul rând, împărțim polinomul în două părți, pe care le vom numi Evens și cote: even =[3,4,5,2] și cote [1,1,9,6] (Sau even =2×3+5×2+4x+3 și cote =6×3+9×2+x+1; da, acest lucru ia doar coeficienții de grad par și coeficienții de grad impar). Acum, observăm o observație matematică: p (x) = even (x2) + x⋅odds (x2) și p (−x) = even (x2) −x⋅odds (x2) (gândiți-vă la acest lucru pentru dvs. și asigurați-vă că îl înțelegeți înainte de a merge mai departe).

„Lipiciul” este relativ ușor (și PE) în timp de execuție): primim evaluări ale egalității și cotelor ca mărime-N / 2 liste, așa că o facem pur și simplu p [i] = evens_result [i] + domain [i] ⋅odds_result [i] și p [N2 + i] = evens_result [i] −domain [i] ⋅odds_result [i] pentru fiecare index i.

Iată codul complet:

def fft(vals, modulus, domain): if len(vals) == 1: return vals L = fft(vals[::2], modulus, domain[::2]) R = fft(vals[1::2], modulus, domain[::2]) o = [0 for i in vals] for i, (x, y) in enumerate(zip(L, R)): y_times_root = y*domain[i] o[i] = (x+y_times_root) % modulus o[i+len(L)] = (x-y_times_root) % modulus return o

Putem încerca să-l rulăm:

>>> fft([3,1,4,1,5,9,2,6], 337, [1, 85, 148, 111, 336, 252, 189, 226])
[31, 70, 109, 74, 334, 181, 232, 4]

Și putem verifica rezultatul; evaluarea polinomului la poziție 85, de exemplu, de fapt dă rezultatul 70. Rețineți că acest lucru funcționează numai dacă domeniul este „corect”; trebuie să aibă forma [x ^ i% modul pentru i în intervalul (n)] Unde x ^ n = 1.

Un FFT invers este surprinzător de simplu:

def inverse_fft(vals, modulus, domain): vals = fft(vals, modulus, domain) return [x * modular_inverse(len(vals), modulus) % modulus for x in [vals[0]] + vals[1:][::-1]]

Practic, rulați FFT din nou, dar inversați rezultatul (cu excepția faptului că primul element rămâne la locul său) și împărțiți fiecare valoare la lungimea listei.

>>> domain = [1, 85, 148, 111, 336, 252, 189, 226]
>>> def modular_inverse(x, n): return pow(x, n - 2, n)
>>> values = fft([3,1,4,1,5,9,2,6], 337, domain)
>>> values
[31, 70, 109, 74, 334, 181, 232, 4]
>>> inverse_fft(values, 337, domain)
[3, 1, 4, 1, 5, 9, 2, 6]

Acum, pentru ce putem folosi acest lucru? Iată un caz de utilizare distractiv: putem folosi FFT-uri pentru a multiplica numerele foarte repede. Să presupunem că am vrut să ne înmulțim 1253 by 1895. Iată ce am face. În primul rând, am converti problema într-una care se dovedește a fi ușor: înmulțiți polinomiale [3,5,2,1] by [5,9,8,1] (aceasta este doar cifrele celor două numere în ordine crescătoare), apoi convertiți răspunsul înapoi într-un număr făcând o singură trecere pentru a transporta zeci de cifre.

Putem înmulți polinoamele cu FFT-uri rapid, deoarece se dovedește că dacă convertiți un polinom în formular de evaluare (adică. f (x) pentru fiecare x în unele domenii D), atunci puteți înmulți două polinoame pur și simplu prin multiplicarea evaluărilor lor. Deci, ceea ce vom face este să luăm polinoamele care reprezintă cele două numere ale noastre forma coeficientului, utilizați FFT-uri pentru a le converti în formular de evaluare, pentru a le înmulți în sens punct și pentru a converti înapoi:

>>> p1 = [3,5,2,1,0,0,0,0]
>>> p2 = [5,9,8,1,0,0,0,0]
>>> x1 = fft(p1, 337, domain)
>>> x1
[11, 161, 256, 10, 336, 100, 83, 78]
>>> x2 = fft(p2, 337, domain)
>>> x2
[23, 43, 170, 242, 3, 313, 161, 96]
>>> x3 = [(v1 * v2) % 337 for v1, v2 in zip(x1, x2)]
>>> x3
[253, 183, 47, 61, 334, 296, 220, 74]
>>> inverse_fft(x3, 337, domain)
[15, 52, 79, 66, 30, 10, 1, 0]

Acest lucru necesită trei FFT (fiecare O (N⋅log (N)) timp) și o multiplicare punctuală (PE) timp), deci este nevoie O (N⋅log (N)) timpul cu totul (din punct de vedere tehnic puțin mai mult decât O (N⋅log (N)), deoarece pentru numere foarte mari ar trebui să înlocuiți 337 cu un modul mai mare și care ar face multiplicarea mai dificilă, dar suficient de apropiată). Aceasta este mult mai repede decât multiplicarea manualelor școlare, care necesită O (N2) timp:

 3 5 2 1 ------------
5 | 15 25 10 5
9 | 27 45 18 9
8 | 24 40 16 8
1 | 3 5 2 1 --------------------- 15 52 79 66 30 10 1

Deci, acum luăm doar rezultatul și transportăm zecile cifre (acesta este un algoritm „parcurgeți lista o dată și faceți un lucru la fiecare punct”, așa că este nevoie PE) timp):

[15, 52, 79, 66, 30, 10, 1, 0]
[ 5, 53, 79, 66, 30, 10, 1, 0]
[ 5, 3, 84, 66, 30, 10, 1, 0]
[ 5, 3, 4, 74, 30, 10, 1, 0]
[ 5, 3, 4, 4, 37, 10, 1, 0]
[ 5, 3, 4, 4, 7, 13, 1, 0]
[ 5, 3, 4, 4, 7, 3, 2, 0]

Și dacă citim cifrele de sus în jos, obținem 2374435. Să verificăm răspunsul ...

>>> 1253 * 1895
2374435

Yay! A mers. În practică, la intrări atât de mici, diferența dintre O (N⋅log (N)) și O (N ^ 2) nu este acea mare, deci multiplicarea manualelor școlare este mai rapidă decât acest proces de multiplicare bazat pe FFT doar pentru că algoritmul este mai simplu, dar pe intrări mari face o diferență cu adevărat mare.

Dar FFT-urile sunt utile nu doar pentru multiplicarea numerelor; așa cum s-a menționat mai sus, multiplicarea polinomială și evaluarea în mai multe puncte sunt operațiuni de importanță crucială în implementarea codificării ștergerii, care este o tehnică foarte importantă pentru construirea multor tipuri de sisteme redundante tolerante la defecte. Dacă îți place toleranța la erori și îți place eficiența, FFT-urile sunt prietenul tău.

FFT-uri și câmpuri binare

Câmpurile prime nu sunt singurul tip de câmp finit de acolo. Un alt tip de câmp finit (într-adevăr un caz special al conceptului mai general al unui câmp de extensie, care sunt cam ca echivalentul câmpului finit al numerelor complexe) sunt câmpuri binare. Într-un câmp binar, fiecare element este exprimat ca un polinom în care sunt toate intrările 0 or 1, de exemplu. x ^ 3 + x + 1.

Adăugarea polinoamelor se face modulo 2, iar scăderea este aceeași cu adunarea (ca −1 = 1mod2). Selectăm un polinom ireductibil ca modul (de ex. x ^ 4 + x + 1; x ^ 4 + 1 nu ar funcționa pentru că x ^ 4 + 1 poate fi luat în considerare (x2 + 1) ⋅ (x2 + 1) deci nu este „ireductibil”); multiplicarea se face modulul care modulul. De exemplu, în câmpul binar mod x ^ 4 + x + 1, multiplicându-se x2 + 1 cu x3 + 1 ar da x5 + x3 + x2 + 1 dacă doar faci multiplicarea, dar x^5+x^3+x^2+1=(x^4+x+1)⋅x+(x^3+x+1), deci rezultatul este restul x ^ 3 + x + 1.

Putem exprima acest exemplu ca un tabel de înmulțire. Mai întâi înmulțiți [1,0,0,1] (adică. x ^ 3 + 1) de [1,0,1] (adică. x ^ 2 + 1):

 1 0 0 1 --------
1 | 1 0 0 1
0 | 0 0 0 0
1 | 1 0 0 1 ------------ 1 0 1 1 0 1

Rezultatul multiplicării conține un x ^ 5 termen pentru a putea scădea (x4 + x + 1) ⋅x:

 1 0 1 1 0 1 - 1 1 0 0 1 [(x⁴ + x + 1) shifted right by one to reflect being multipled by x] ------------ 1 1 0 1 0 0 

Și obținem rezultatul, [1,1,0,1] (or x3 + x + 1).

Tabelele de adunare și multiplicare pentru câmpul binar mod x ^ 4 + x + 1. Elementele de câmp sunt exprimate ca numere întregi convertite din binar (de ex. x ^ 3 + x ^ 2 → 1100 → 12)

Câmpurile binare sunt interesante din două motive. În primul rând, dacă doriți să ștergeți codul de date binare, atunci câmpurile binare sunt foarte convenabile, deoarece N octeții de date pot fi codați direct ca element de câmp binar și orice elemente de câmp binar pe care le generați efectuând calcule pe acesta vor fi, de asemenea, N octeți lung. Nu puteți face acest lucru cu câmpurile prime, deoarece dimensiunea câmpurilor prime nu este exact o putere de două; de exemplu, ai putea codifica fiecare 2 octeți ca număr de la 0 ... 65536 în modulul câmpului prim 65537 (care este prim), dar dacă faceți un FFT pe aceste valori, atunci ieșirea ar putea conține 65536, care nu poate fi exprimat în doi octeți.

În al doilea rând, faptul că adunarea și scăderea devin aceeași operație și 1 + = 1 0, creați o „structură” care duce la unele consecințe foarte interesante. O ciudățenie deosebit de interesantă și utilă a câmpurilor binare este „visul bobocilor”Teorema: (x + y) ^ 2 = x ^ 2 + y ^ 2 (și același lucru pentru exponenți 4,8,16 ... practic orice putere a două).

Dar dacă doriți să utilizați câmpuri binare pentru ștergerea codificării și faceți acest lucru eficient, atunci trebuie să puteți face transformări rapide Fourier peste câmpuri binare. Dar apoi există o problemă: într-un câmp binar, nu există grupuri de ordine multiplicative (netiviale) 2 ^ n. Acest lucru se datorează faptului că grupurile multiplicative sunt toate de ordine 2 ^ n-1. De exemplu, în câmpul binar cu modul x ^ 4 + x + 1, dacă începeți să calculați puterile succesive ale x + 1, te duci înapoi la 1 după 15 pași - nu 16. Motivul este că numărul total de elemente din câmp este 16, dar una dintre ele este zero și nu veți ajunge niciodată la zero prin multiplicarea oricărei valori diferite de zero într-un câmp, deci puterile x + 1 ciclul prin fiecare element, dar zero, deci lungimea ciclului este 15, Nu 16. Deci ce facem?

Motivul pentru care am avut nevoie ca domeniul să aibă „structura” unui grup multiplicativ cu 2n elemente înainte este acela că trebuie să reducem dimensiunea domeniului cu un factor de doi prin pătratul fiecărui număr din acesta: domeniul [1,85,148,111,336,252,189,226] se reduce la [1,148,336,189] deoarece 1 este pătratul ambelor 1 și 336, 148 este pătratul ambelor 85 și 252, si asa mai departe.

Dar dacă într-un câmp binar există un mod diferit de a înjumătăți dimensiunea unui domeniu? Se pare că există: dat un domeniu care conține 2 ^ k valori, inclusiv zero (din punct de vedere tehnic, domeniul trebuie să fie un subspațiu), putem construi un nou domeniu pe jumătate D ′ luând x⋅ (x + k) pentru x in D folosind unele specifice k in D. Deoarece domeniul original este un subspatiu, din moment ce k este în domeniu, oricare x în domeniu are un corespunzător x + k de asemenea, în domeniu și funcție f (x) = x⋅ (x + k) returnează aceeași valoare pentru x și x + k deci obținem același tip de corespondență doi la unu pe care ni-l oferă pătratul.

Acum, cum facem un FFT pe deasupra? Vom folosi același truc, convertind o problemă cu un N-polinom de dimensiuni și N-dimensiunea domeniului în două probleme fiecare cu un N / 2-polinom de dimensiuni și N / 2-dimensiunea domeniului, dar de data aceasta folosind diferite ecuații. Vom converti un polinom p în două polinoame Evens și cote astfel încât p (x) = even (x⋅ (k − x)) + x⋅odds (x⋅ (k − x)). Rețineți că pentru egalitatea și șansele pe care le găsim, va fi de asemenea fii adevărat că p (x + k) = even (x⋅ (k − x)) + (x + k) ⋅odds (x⋅ (k − x)). Deci, putem face apoi recursiv un FFT pentru echivalențe și cote pe domeniul redus [x⋅ (k − x) pentru x în D], și apoi folosim aceste două formule pentru a obține răspunsurile pentru două „jumătăți” ale domeniului, una compensată cu k de cealaltă.

Conversia p în Evens și cote așa cum este descris mai sus, se dovedește a fi netivial. Algoritmul „naiv” pentru a face acest lucru este el însuși O (N ^ 2), dar se pare că într-un câmp binar, putem folosi faptul că (x2−kx)2=x4−k2⋅x2, și mai general (x2−kx)2i=x2i+1−k2i⋅x2i , pentru a crea încă un alt algoritm recursiv pentru a face acest lucru O (N⋅log (N)) timp.

Și dacă vrei să faci un invers FFT, pentru a face interpolare, atunci trebuie să rulați pașii din algoritm în ordine inversă. Puteți găsi codul complet pentru a face acest lucru aici: https://github.com/ethereum/research/tree/master/binary_fftși o lucrare cu detalii despre algoritmi mai optimi aici: http://www.math.clemson.edu/~sgao/papers/GM10.pdf

Deci, ce obținem din toată această complexitate? Ei bine, putem încerca să rulăm implementarea, care prezintă atât un „naiv” O (N ^ 2) evaluarea în mai multe puncte și cea optimizată bazată pe FFT și timpul ambelor. Iată rezultatele mele:

>>> import binary_fft as b
>>> import time, random
>>> f = b.BinaryField(1033)
>>> poly = [random.randrange(1024) for i in range(1024)]
>>> a = time.time(); x1 = b._simple_ft(f, poly); time.time() - a
0.5752472877502441
>>> a = time.time(); x2 = b.fft(f, poly, list(range(1024))); time.time() - a
0.03820443153381348

Și pe măsură ce dimensiunea polinomului devine mai mare, implementarea naivă (_simple_ft) devine mai lent mai rapid decât FFT:

>>> f = b.BinaryField(2053)
>>> poly = [random.randrange(2048) for i in range(2048)]
>>> a = time.time(); x1 = b._simple_ft(f, poly); time.time() - a
2.2243144512176514
>>> a = time.time(); x2 = b.fft(f, poly, list(range(2048))); time.time() - a
0.07896280288696289

Și voilă, avem un mod eficient, scalabil de a evalua și interpola polinomii în mai multe puncte. Dacă dorim să folosim FFT-uri pentru a recupera datele codate prin ștergere acolo unde ne aflăm dispărut unele piese, apoi algoritmi pentru aceasta există, de asemenea, deși sunt oarecum mai puțin eficiente decât simpla realizare a unui singur FFT. Bucurați-vă!

Acest articol a fost publicat inițial ca „Transformate Fourier rapide

PlatoAi. Web3 Reimaginat. Inteligența datelor amplificată.
Faceți clic aici pentru a accesa.

Sursă: https://hackernoon.com/fast-fourier-transform-scaling-multi-point-evaluation?source=rss