Fast Fourier -transformasjonen (FFT) er en sentral byggestein i mange algoritmer, inkludert multiplikasjon av store tall og multiplikasjon av polynom. Fourier -transformasjoner har også viktige applikasjoner innen signalbehandling, kvantemekanikk og andre områder, og bidrar til å få betydelige deler av den globale økonomien til å skje. Vi skal snakke om to forskjellige operasjoner: flerpunkts polynomevaluering (evaluering av en grad) og dens inverse, polynomiske interpolasjon (gitt evalueringene av en grad

Utløservarsel: spesialisert matematisk emne

Spesiell takk til Karl Floersch for tilbakemelding

En av de mer interessante algoritmene i tallteori er Fast Fourier -transformasjonen (FFT). FFT er en sentral byggestein i mange algoritmer, inkludert ekstremt rask multiplikasjon av store tall, multiplikasjon av polynomer, og ekstremt rask generering og gjenoppretting av slettingskoder.

Sletningskoder er spesielt allsidige; i tillegg til deres grunnleggende brukstilfeller i feiltolerant datalagring og gjenoppretting, har slettingskoder også mer avanserte brukstilfeller som f.eks. sikre datatilgjengelighet i skalerbare blokker og STARKER. Denne artikkelen vil gå inn på hva raske Fourier -transformasjoner er, og hvordan noen av de enklere algoritmene for å beregne dem fungerer.

Bakgrunn

Ok, Fourier -transformasjoner har også veldig viktige applikasjoner innen signalbehandling, kvantemekanikk og andre områder, og bidrar til å få betydelige deler av den globale økonomien til å skje. Men kom igjen, elefanter er kulere.

Den opprinnelige Fourier transformasjon er en matematisk operasjon som ofte beskrives som å konvertere data mellom "frekvensdomenet" og "tidsdomenet". Hva dette betyr mer presist er at hvis du har et stykke data, vil kjøring av algoritmen komme opp med en samling av sinusbølger med forskjellige frekvenser og amplituder som, hvis du la dem sammen, ville tilnærmet de opprinnelige dataene. Fourier -transformasjoner kan brukes til slike fantastiske ting som uttrykker firkantede baner gjennom epicycles og utlede et sett med ligninger som kan tegne en elefant:

Den typen Fourier -transformasjon vi skal snakke om i dette innlegget er en lignende algoritme, bortsett fra i stedet for å være en kontinuerlig Fourier transformere over reelle eller komplekse tall, det er en diskret Fourier-transform enn endelige felt (se delen "A Modular Math Interlude" her. for en oppfriskning på hva endelige felt er).

I stedet for å snakke om å konvertere mellom "frekvensdomene" og "tidsdomene", vil vi her snakke om to forskjellige operasjoner: flerpunktspolynomevaluering (vurdere en grad <N polynom kl N forskjellige punkter) og dens inverse, polynom interpolasjon (gitt vurderingene av en grad <N polynom kl N forskjellige punkter, gjenopprette polynomet). For eksempel, hvis vi opererer i primfeltet med modul 5, så er polynomet y = x²+3 (for enkelhets skyld kan vi skrive koeffisientene i økende rekkefølge: [3,0,1]) evaluert på punktene [0,1,2] gir verdiene [3,4,2] (ikke [3,4,7] fordi vi opererer i et begrenset felt der tallene vikles rundt 5), og vi kan faktisk ta evalueringene [3,4,2] og koordinatene de ble evaluert til ([0,1,2]) for å gjenopprette det opprinnelige polynomet [3,0,1].

Det er algoritmer for både flerpunktsevaluering og interpolasjon som kan utføre begge operasjoner i O (N²) tid. Evaluering av flere punkter er enkel: Bare evaluer polynomet separat på hvert punkt. Her er python -koden for å gjøre det:

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

Algoritmen kjører en løkke som går gjennom hver koeffisient og gjør én ting for hver koeffisient, så den går inn PÅ) tid. Flerpunktsevaluering innebærer å gjøre denne evalueringen kl N forskjellige poeng, så den totale kjøretiden er O (N²).

Lagrange interpolasjon er mer komplisert (søk etter "Lagrange interpolation" her. for en mer detaljert forklaring). Den viktigste byggesteinen i den grunnleggende strategien er den for ethvert domene D og pek x, kan vi konstruere et polynom som returnerer 1 forum x og 0 for enhver verdi i D unntatt x. For eksempel, hvis D=[1,2,3,4] og x=1, polynomet er:

Du kan mentalt koble til 1, 2, 3 og 4 til uttrykket ovenfor og bekreft at det returnerer 1 forum x=1 og 0 i de tre andre sakene.

Vi kan gjenopprette polynomet som gir et ønsket sett med utganger på det gitte domenet ved å multiplisere og legge til disse polynomene. Hvis vi kaller ovennevnte polynom P1og tilsvarende for x = 2, x = 3, x = 4, P2, P3 og P4, deretter polynomet som returnerer [3,1,4,1] på domenet [1,2,3,4] er rett og slett 3⋅P1+P2+4⋅P3+P4. Det tar å beregne Pi -polynomene PŲ) tid (du konstruerer først polynomet som går tilbake til 0 på hele domenet, noe som tar O (N²) tid, deretter dele det separat med (x − xi) for hver xi), og å beregne den lineære kombinasjonen tar en annen O (N²) tid, så det er det O (N²) kjøretid totalt.

Raske Fourier -transformasjoner

Det er en pris du må betale for å bruke denne mye raskere algoritmen, som er at du ikke kan velge noe vilkårlig felt og vilkårlig domene. Mens med Lagrange -interpolasjon, kan du velge x -koordinater og y -koordinater du vil ha, og hvilket felt du vil (du kan til og med gjøre det over vanlige reelle tall), og du kan få et polynom som passerer gjennom dem., Med en FFT , du må bruke et begrenset felt, og domenet må være et multiplikativ undergruppe av feltet (det vil si en liste over krefter med en "generator" -verdi).

For eksempel kan du bruke det endelige feltet med heltall modulo 337, og for domenebruk [1,85,148,111,336,252,189,226] (det er kreftene til 85 i feltet, f.eks. 85^3 % 337 = 111; det stopper kl 226 fordi den neste kraften til 85 går tilbake til 1). Videre må den multiplikative undergruppen ha størrelse 2n (det er måter å få det til å fungere for tall i skjemaet 2^m⋅3^n og muligens litt høyere primakrefter, men da blir det mye mer komplisert og ineffektivt). Det endelige feltet for intergers modulo 59, for eksempel, ville ikke fungere, fordi det bare er multiplikative undergrupper av rekkefølge 2, 29 og 58; 2 er for liten til å være interessant, og faktoren 29 er altfor stor til å være FFT-vennlig. Symmetrien som kommer fra multiplikative størrelsesgrupper 2^n lar oss lage en rekursiv algoritme som ganske smart beregner resultatene vi trenger fra en mye mindre mengde arbeid.

For å forstå algoritmen og hvorfor den har lav kjøretid, er det viktig å forstå det generelle begrepet rekursjon. En rekursiv algoritme er en algoritme som har to tilfeller: en "basiskasse" der inngangen til algoritmen er liten nok til at du kan gi utgangen direkte, og den "rekursive saken" der den nødvendige beregningen består av noen "limberegninger" pluss en eller flere bruksområder av den samme algoritmen til mindre innganger. For eksempel har du kanskje sett rekursive algoritmer som ble brukt til å sortere lister. Hvis du har en liste (f. [1,8,7,4,5,6,3,2,9]), kan du sortere det ved å følge følgende prosedyre:

• Hvis inngangen har ett element, er den allerede "sortert", slik at du bare kan returnere inngangen.

• Hvis inngangen har mer enn ett element, må du sortere den første halvdelen av listen og den andre halvdelen av listen separat, og deretter slå sammen de to sorterte underlistene (kall dem A og B) følgende. Opprettholde to tellere, etter og bpos, begge starter på null, og opprettholder en utdataliste, som starter tom. Inntil heller etter or bpos er på slutten av den tilsvarende listen, sjekk om A[apos] or B[bpos] er mindre. Den som er mindre, legg til denne verdien på slutten av utdatalisten og øk telleren med 1. Når dette er gjort, legg til resten av listen som ikke er fullstendig behandlet til slutten av utdatalisten, og returner utdataene liste.

Vær oppmerksom på at "limet" i den andre prosedyren har kjøretid PÅ): hvis hver av de to dellistene har N elementer, så må du kjøre gjennom hvert element i hver liste en gang, så det er det PÅ) beregning totalt. Så algoritmen som helhet fungerer ved å ta et problem med størrelse N, og dele det opp i to størrelsesproblemer N2, Pluss PÅ) av "lim" -utførelse.

Det er et teorem som heter Mestersetning som lar oss beregne den totale kjøretiden til algoritmer som dette. Den har mange undersaker, men i tilfellet der du deler opp en utførelse av størrelse N i k undersaker av størrelse N/k med PÅ) lim (slik tilfellet er her), er resultatet at utførelsen tar tid O (N⋅log (N)).

En FFT fungerer på samme måte. Vi tar et problem med størrelsen N, del det opp i to problemer med størrelse N2, og gjør PÅ) limarbeid for å kombinere de mindre løsningene til en større løsning, så vi får O (N⋅log (N)) kjøretid totalt - mye raskere enn O (N2). Slik gjør vi det. Jeg skal først beskrive hvordan du bruker en FFT for flerpunktsevaluering (dvs. for et domene D og polynom P, regne ut P (x) for hver x in D), og det viser seg at du kan bruke den samme algoritmen for interpolasjon med en liten finjustering.

Anta at vi har en FFT der det gitte domenet er kreftene til x på et eller annet felt, hvor x^2^k = 1 (f.eks. i tilfellet vi introduserte ovenfor, er domenet makten til 85 modulo 337og 85^2^3 = 1). Vi har noe polynom, f.eks. y=6×7+2×6+9×5+5×4+x3+4×2+x+3 (vi skriver det som p = [3,1,4,1,5,9,2,6]). Vi ønsker å evaluere dette polynomet på hvert punkt i domenet, dvs. ved hver av de åtte kreftene til 85. Her er hva vi gjør.

Først deler vi polynomet i to deler, som vi kaller Evens og odds: jevnt =[3,4,5,2] og odds [1,1,9,6] (eller jevn =2×3+5×2+4x+3 og odds =6×3+9×2+x+1; ja, dette er bare å ta like gradskoeffisientene og oddegradskoeffisientene). Nå legger vi merke til en matematisk observasjon: p (x) = jevn (x2)+x⋅odds (x2) og p (−x) = jevn (x2) −x⋅odds (x2) (tenk på dette selv og sørg for at du forstår det før du går videre).

"Limet" er relativt enkelt (og PÅ) i kjøretid): vi mottar evalueringene av evens og odds som størrelse-N/2 lister, så vi gjør det rett og slett p [i] = evens_result [i]+domene [i] ⋅odds_result [i] og p [N2+i] = evens_result [i] −domain [i] ⋅odds_result [i] for hver indeks i.

Her er hele koden:

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

Vi kan prøve å kjøre den:

>>> 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]

Og vi kan sjekke resultatet; å evaluere polynomet på stillingen 85for eksempel faktisk gir resultatet 70. Vær oppmerksom på at dette bare fungerer hvis domenet er "riktig"; den må ha formen [x^i % modul for i i området (n)] hvor x^n = 1.

En omvendt FFT er overraskende enkel:

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]]

I utgangspunktet, kjør FFT igjen, men reverser resultatet (bortsett fra at det første elementet forblir på plass) og divider hver verdi med lengden på listen.

>>> 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]

Hva kan vi bruke dette til nå? Her er en morsom brukstilfelle: vi kan bruke FFT -er til å multiplisere tall veldig raskt. Anta at vi ønsket å multiplisere 1253 by 1895. Her er hva vi ville gjøre. Først ville vi konvertere problemet til et som viser seg å være litt lettere: multiplisere polynomer [3,5,2,1] by [5,9,8,1] (det er bare sifrene i de to tallene i økende rekkefølge), og konverter deretter svaret tilbake til et tall ved å gjøre en enkelt passering for å overføre titalls sifre.

Vi kan multiplisere polynom med FFT raskt, fordi det viser seg at hvis du konverterer et polynom til evalueringsskjema (dvs. f (x) for hver x på et eller annet domene D), så kan du multiplisere to polynom ved å multiplisere evalueringene deres. Så det vi skal gjøre er å ta polynomene som representerer våre to tall koeffisientform, bruk FFT -er for å konvertere dem til evalueringsskjema, multiplisere dem med punktvis og konvertere tilbake:

>>> 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]

Dette krever tre FFT -er (hver O (N⋅log (N)) tid) og en punktvis multiplikasjon (PÅ) tid), så det tar O (N⋅log (N)) tid totalt (teknisk sett litt mer enn O (N⋅log (N)), fordi du må bytte ut for veldig store tall 337 med en større modul, og det ville gjøre multiplikasjon vanskeligere, men nær nok). Dette er mye raskere enn skolebokmultiplikasjon, som tar O (N2) tid:

 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

Så nå tar vi bare resultatet og bærer titallsifrene over (dette er en "gå gjennom listen en gang og gjør en ting på hvert punkt" -algoritmen, så det tar PÅ) tid):

[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]

Og hvis vi leser sifrene fra topp til bunn, får vi 2374435. La oss sjekke svaret ....

>>> 1253 * 1895
2374435

Jippi! Det funket. I praksis, på slike små innganger, er forskjellen mellom O (N⋅log (N)) og O (N ^ 2) er ikke Det stor, så skolebokmultiplikasjon er raskere enn denne FFT-baserte multiplikasjonsprosessen bare fordi algoritmen er enklere, men på store innganger utgjør den en veldig stor forskjell.

Men FFT -er er nyttige ikke bare for å multiplisere tall; Som nevnt ovenfor er polynom multiplikasjon og flerpunktsevaluering avgjørende operasjoner for å implementere slettingskoding, som er en veldig viktig teknikk for å bygge mange typer redundante feiltolerante systemer. Hvis du liker feiltoleranse og liker effektivitet, er FFT -er din venn.

FFT og binære felt

Prime -felt er ikke den eneste typen endelige felt der ute. En annen type begrenset felt (virkelig et spesielt tilfelle av det mer generelle begrepet en utvidelsesfelt, som er omtrent som det endelige feltekvivalenten til komplekse tall) er binære felt. I et binært felt uttrykkes hvert element som et polynom der alle oppføringene er 0 or 1, f.eks. x^3+x+1.

Legge til polynom gjøres modulo 2, og subtraksjon er det samme som addisjon (som −1 = 1mod2). Vi velger et ureduserbart polynom som modul (f.eks. x^4+x+1; x^4+1 ville ikke fungere fordi x^4+1 kan tas inn i (x2+1) ⋅ (x2+1) så det er ikke "irreducible"); multiplikasjon gjøres modulo at modulus. For eksempel, i det binære feltet mod x^4+x+1, multipliserer x2+1 x3+1 ville gitt x5+x3+x2+1 hvis du bare gjør multiplikasjonen, men x^5+x^3+x^2+1=(x^4+x+1)⋅x+(x^3+x+1), så resultatet er resten x^3+x+1.

Vi kan uttrykke dette eksemplet som en multiplikasjonstabell. Først multiplisere [1,0,0,1] (dvs. x^3+1) av [1,0,1] (dvs. 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

Multiplikasjonsresultatet inneholder en x^5 sikt så vi kan trekke fra (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 

Og vi får resultatet, [1,1,0,1] (or x3+x+1).

Addisjon og multiplikasjonstabeller for binærfeltmod x^4+x+1. Feltelementer uttrykkes som heltall konvertert fra binært (f.eks. x^3+x^2 → 1100 → 12)

Binære felt er interessante av to grunner. Først av alt, hvis du vil slette-kode binære data, så er binære felt veldig praktiske fordi N byte med data kan kodes direkte som et binært feltelement, og eventuelle binære feltelementer du genererer ved å utføre beregninger på det vil også være N byte lang. Du kan ikke gjøre dette med primfelt fordi størrelsen på primfeltene ikke akkurat er en effekt på to; for eksempel kan du kode hver 2 byte som et tall fra 0 ... 65536 i hovedfeltmodulen 65537 (som er prime), men hvis du gjør en FFT på disse verdiene, kan utgangen inneholde 65536, som ikke kan uttrykkes i to byte.

For det andre det faktum at addisjon og subtraksjon blir den samme operasjonen, og 1 + = 1 0, skape en eller annen "struktur" som fører til noen veldig interessante konsekvenser. En spesielt interessant og nyttig odditet av binære felt er "nyårsdrøm"Setning: (x+y)^2 = x^2+y^2 (og det samme for eksponenter 4,8,16 ... i utgangspunktet hvilken som helst kraft på to).

Men hvis du vil bruke binære felt for slettingskoding, og gjøre det effektivt, må du kunne gjøre Fast Fourier -transformasjoner over binære felt. Men så er det et problem: i et binært felt, det er ingen (ikke -tradisjonelle) multiplikative grupper av ordener 2^n. Dette er fordi multiplikative grupper alle er orden 2^n-1. For eksempel i det binære feltet med modul x^4+x+1, hvis du begynner å beregne suksessive krefter på x + 1, sykler du tilbake til 1 etter 15 trinn - ikke 16. Årsaken er at det totale antallet elementer i feltet er 16, men en av dem er null, og du kommer aldri til å nå null ved å multiplisere en verdi uten null med seg selv i et felt, så kreftene til x + 1 gå gjennom hvert element, men null, så sykluslengden er 15, Ikke 16. Så hva gjør vi?

Grunnen til at vi trengte domenet for å ha "strukturen" til en multiplikativ gruppe med 2n elementer før, er at vi trengte å redusere størrelsen på domenet med en faktor to ved å kvadrere hvert tall i det: domenet [1,85,148,111,336,252,189,226] blir redusert til [1,148,336,189] fordi 1 er firkanten av begge 1 og 336, 148 er firkanten av begge 85 og 252, og så videre.

Men hva om det i et binært felt er en annen måte å halvere størrelsen på et domene på? Det viser seg at det er: gitt et domene som inneholder 2^k verdier, inkludert null (teknisk sett må domenet være a underrom), kan vi konstruere et halvt stort nytt domene D ′ ved å ta x⋅ (x+k) forum x in D bruker noen spesifikke k in D. Fordi det opprinnelige domenet er et underrom, siden k er i domenet, hvilken som helst x i domenet har en tilsvarende x+k også i domenet, og funksjonen f (x) = x⋅ (x+k) returnerer samme verdi for x og x+k så vi får den samme typen to-til-en-korrespondanse som kvadrering gir oss.

Så nå, hvordan gjør vi en FFT på toppen av dette? Vi bruker det samme trikset, og konverterer et problem med en N-størrelse polynom og N-størrelse domene i to problemer hver med en N / 2-størrelse polynom og N / 2-størrelse domene, men denne gangen ved hjelp av forskjellige ligninger. Vi konverterer et polynom p til to polynom Evens og odds slik at p (x) = jevne (x⋅ (k − x))+x⋅odds (x⋅ (k − x)). Vær oppmerksom på at for de evner og odds som vi finner, vil det gjøre det også vær sant det p (x+k) = jevn (x⋅ (k − x))+(x+k) ⋅odds (x⋅ (k − x)). Så vi kan deretter rekursivt gjøre en FFT for evner og odds på det reduserte domenet [x⋅ (k − x) for x i D], og så bruker vi disse to formlene for å få svarene på to "halvdeler" av domenet, den ene kompensert av k fra den andre.

Konverterer p til Evens og odds som beskrevet ovenfor viser seg i seg selv å være ikke -privat. Den "naive" algoritmen for å gjøre dette er seg selv O (N ^ 2), men det viser seg at vi i et binært felt kan bruke det faktum at (x2−kx)2=x4−k2⋅x2, og mer generelt (x2−kx)2i=x2i+1−k2i⋅x2i , for å lage enda en rekursiv algoritme for å gjøre dette i O (N⋅log (N)) tid.

Og hvis du vil gjøre en invers FFT, for å gjøre interpolasjon, så må du kjøre trinnene i algoritmen i motsatt rekkefølge. Du finner den komplette koden for å gjøre dette her: https://github.com/ethereum/research/tree/master/binary_fft, og et papir med detaljer om mer optimale algoritmer her: http://www.math.clemson.edu/~sgao/papers/GM10.pdf

Så hva får vi fra all denne kompleksiteten? Vel, vi kan prøve å kjøre implementeringen, som både har en "naiv" O (N ^ 2) flerpunktsevaluering og den optimaliserte FFT-baserte, og tid begge. Her er resultatene mine:

>>> 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

Og etter hvert som størrelsen på polynomet blir større, blir den naive implementeringen (_simple_ft) blir tregere mye raskere enn 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

Og voila, vi har en effektiv, skalerbar måte å evaluere og interpolere polynom på flere punkter. Hvis vi vil bruke FFT-er til å gjenopprette slettingskodede data der vi er mangler noen stykker, deretter algoritmer for dette finnes også, selv om de er noe mindre effektive enn bare å gjøre en enkelt FFT. Nyt!

Denne artikkelen ble opprinnelig publisert som "Raske Fourier -transformasjoner"

PlatonAi. Web3 Reimagined. Data Intelligence Amplified.
Klikk her for å få tilgang.

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