De Fast Fourier-transformatie (FFT) is een belangrijke bouwsteen in veel algoritmen, waaronder vermenigvuldiging van grote getallen en vermenigvuldiging van polynomen. Fourier-transformaties hebben ook belangrijke toepassingen in signaalverwerking, kwantummechanica en andere gebieden, en helpen belangrijke delen van de wereldeconomie mogelijk te maken. We zullen het hebben over twee verschillende bewerkingen: multi-point polynoomevaluatie (beoordelen van een graad) en de inverse, polynoominterpolatie (gezien de evaluaties van een graad)

Triggerwaarschuwing: gespecialiseerd wiskundig onderwerp

Speciale dank aan Karl Floersch voor feedback

Een van de interessantere algoritmen in de getaltheorie is de Fast Fourier-transformatie (FFT). FFT's zijn een belangrijke bouwsteen in veel algoritmen, waaronder: extreem snelle vermenigvuldiging van grote getallen, vermenigvuldiging van polynomen en extreem snelle generatie en herstel van wiscodes.

Met name wiscodes zijn zeer veelzijdig; naast hun basisgebruikscasussen in fouttolerante gegevensopslag en -herstel, hebben wiscodes ook meer geavanceerde gebruikscasussen zoals de beschikbaarheid van gegevens beveiligen in schaalbare blockchains en STARK's. Dit artikel gaat in op wat snelle Fourier-transformaties zijn en hoe enkele van de eenvoudigere algoritmen om ze te berekenen werken.

Achtergrond

Oké prima, Fourier-transformaties hebben ook echt belangrijke toepassingen in signaalverwerking, kwantummechanica en andere gebieden, en helpen belangrijke delen van de wereldeconomie mogelijk te maken. Maar kom op, olifanten zijn cooler.

De oorspronkelijke Fourier-transformatie is een wiskundige bewerking die vaak wordt beschreven als het converteren van gegevens tussen het "frequentiedomein" en het "tijddomein". Wat dit meer precies betekent, is dat als je een stukje gegevens hebt, het uitvoeren van het algoritme een verzameling sinusgolven zou opleveren met verschillende frequenties en amplituden die, als je ze bij elkaar optelde, de originele gegevens zouden benaderen. Fourier-transformaties kunnen worden gebruikt voor zulke prachtige dingen als: het uitdrukken van vierkante banen door epicykels en een reeks vergelijkingen afleiden die een olifant kunnen tekenen:

Het soort Fourier-transformatie waar we het in dit bericht over zullen hebben, is een soortgelijk algoritme, behalve in plaats van a doorlopend Fourier-transformatie over reële of complexe getallen, het is een discrete Fourier-transformatie over eindige velden (zie het gedeelte "Een modulair wiskunde-intermezzo" hier voor een opfriscursus over wat eindige velden zijn).

In plaats van te praten over het converteren tussen "frequentiedomein" en "tijddomein", zullen we het hier hebben over twee verschillende bewerkingen: multi-point polynoom evaluatie (een diploma beoordelen) <N polynoom bij N verschillende punten) en zijn inverse, polynomiale interpolatie (gezien de waarderingen van een diploma) <N polynoom bij N verschillende punten, waarbij de polynoom wordt hersteld). Als we bijvoorbeeld in het priemgetal werken met modulus 5, dan is de polynoom y=x²+3 (voor het gemak kunnen we de coëfficiënten in oplopende volgorde schrijven: [3,0,1]) geëvalueerd op de punten [0,1,2] geeft de waarden [3,4,2] (Niet [3,4,7] omdat we in een eindig veld werken waar de getallen rond 5 lopen), en we de evaluaties daadwerkelijk kunnen nemen [3,4,2] en de coördinaten waarop ze werden geëvalueerd ([0,1,2]) om de oorspronkelijke polynoom te herstellen [3,0,1].

Er zijn algoritmen voor zowel multi-point evaluatie als interpolatie die beide bewerkingen kunnen uitvoeren in O(N²) tijd. Multi-point evaluatie is eenvoudig: evalueer de polynoom op elk punt afzonderlijk. Hier is python-code om dat te doen:

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

Het algoritme voert een lus uit die door elke coëfficiënt gaat en doet één ding voor elke coëfficiënt, dus het loopt in AAN) tijd. Multi-point evaluatie houdt in dat je deze evaluatie doet op: N verschillende punten, dus de totale looptijd is O(N²).

Lagrange-interpolatie is ingewikkelder (zoek naar "Lagrange-interpolatie" hier voor een uitgebreidere uitleg). De belangrijkste bouwsteen van de basisstrategie is dat voor elk domein D en wijs x, kunnen we een polynoom construeren dat terugkeert 1 For x en 0 voor elke waarde in D dan x. Als bijvoorbeeld D=[1,2,3,4] en x=1, het polynoom is:

Je kunt mentaal inpluggen 1, 2, 3 en 4 naar de bovenstaande uitdrukking en controleer of deze terugkeert 1 For x=1 en 0 in de andere drie gevallen.

We kunnen de polynoom herstellen die elke gewenste reeks outputs op het gegeven domein geeft door deze polynomen te vermenigvuldigen en op te tellen. Als we de bovenstaande polynoom noemen P1, en de equivalenten voor x = 2, x = 3, x = 4, P2, P3 en P4, dan de polynoom die terugkeert [3,1,4,1] op het domein [1,2,3,4] gewoon 3⋅P1+P2+4⋅P3+P4. Het berekenen van de Pi-polynomen duurt AAN²) tijd (je construeert eerst de polynoom die terugkeert naar 0 op het hele domein, wat duurt O(N²) tijd, deel het dan afzonderlijk door (x−xi) voor elk xi), en het berekenen van de lineaire combinatie kost een andere O(N²) tijd, dus het is O(N²) looptijd totaal.

Snelle Fourier-transformaties

Er is een prijs die u moet betalen voor het gebruik van dit veel snellere algoritme, namelijk dat u geen willekeurig veld en een willekeurig domein kunt kiezen. Terwijl je met Lagrange-interpolatie de x-coördinaten en y-coördinaten kunt kiezen die je wilt, en welk veld je ook wilt (je zou het zelfs kunnen doen over gewone oude reële getallen), en je zou een polynoom kunnen krijgen die er doorheen gaat., met een FFT , je moet een eindig veld gebruiken en het domein moet a . zijn multiplicatieve subgroep van het veld (dat wil zeggen, een lijst met bevoegdheden van een of andere "generator" -waarde).

U kunt bijvoorbeeld het eindige veld van gehele getallen modulo 337, en voor het domeingebruik [1,85,148,111,336,252,189,226] (dat is de kracht van) 85 in het veld, bijv. 85^3% 337=111; het stopt bij 226 omdat de volgende kracht van 85 keert terug naar 1). Verder moet de multiplicatieve subgroep grootte hebben 2n (er zijn manieren om het te laten werken voor getallen van het formulier) 2^m⋅3^n en mogelijk iets hogere priemgetallen, maar dan wordt het veel gecompliceerder en inefficiënter). Het eindige veld van intergers modulo 59, zou bijvoorbeeld niet werken, omdat er alleen multiplicatieve subgroepen van orde zijn 2, 29 en 58; 2 is te klein om interessant te zijn, en de factor 29 is veel te groot om FFT-vriendelijk te zijn. De symmetrie die voortkomt uit multiplicatieve groepen van grootte 2^n laten we een recursief algoritme maken dat heel slim de resultaten berekent die we nodig hebben uit een veel kleinere hoeveelheid werk.

Om het algoritme te begrijpen en waarom het een lage runtime heeft, is het belangrijk om het algemene concept van recursie te begrijpen. Een recursief algoritme is een algoritme met twee gevallen: een "basisgeval" waarbij de invoer voor het algoritme klein genoeg is om de uitvoer direct te kunnen geven, en het "recursieve geval" waarbij de vereiste berekening bestaat uit een "lijmberekening" plus een of meer toepassingen van hetzelfde algoritme voor kleinere invoer. U hebt bijvoorbeeld gezien dat recursieve algoritmen worden gebruikt voor het sorteren van lijsten. Als je een lijst hebt (bijv. [1,8,7,4,5,6,3,2,9]), dan kunt u het sorteren met de volgende procedure:

• Als de invoer één element heeft, dan is deze al "gesorteerd", dus u kunt de invoer gewoon retourneren.

• Als de invoer meer dan één element heeft, sorteer dan afzonderlijk de eerste helft van de lijst en de tweede helft van de lijst, en voeg vervolgens de twee gesorteerde sublijsten samen (noem ze A en B) als volgt. Houd twee tellers bij, apos en bpos, beide beginnend bij nul, en houden een uitvoerlijst bij, die leeg begint. Tot een van beide apos or bpos staat aan het einde van de bijbehorende lijst, controleer of A[apos] or B[bpo's] is kleiner. Welke kleiner is, voeg die waarde toe aan het einde van de uitvoerlijst en verhoog die teller met 1. Zodra dit is gebeurd, voegt u de rest van de lijst die niet volledig is verwerkt toe aan het einde van de uitvoerlijst en retourneert u de uitvoer lijst.

Merk op dat de "lijm" in de tweede procedure runtime heeft AAN): als elk van de twee sublijsten heeft N elementen, dan moet je elk item in elke lijst één keer doorlopen, dus het is AAN) berekening totaal. Dus het algoritme als geheel werkt door een probleem van grootte te nemen N, en het opsplitsen in twee problemen van grootte N2Plus AAN) van "lijm" uitvoering.

Er is een stelling genaamd de Master Theorema waarmee we de totale looptijd van algoritmen als deze kunnen berekenen. Het heeft veel sub-gevallen, maar in het geval dat u een uitvoering van maat N opdeelt in k sub-gevallen van grootte N/k Met AAN) lijm (zoals hier het geval is), het resultaat is dat de uitvoering tijd kost O(N⋅log(N)).

Een FFT werkt op dezelfde manier. We nemen een probleem van de grootte: N, verdeel het in twee problemen van grootte N2, en doe AAN) lijmwerk om de kleinere oplossingen te combineren tot een grotere oplossing, dus we krijgen O(N⋅log(N)) looptijd totaal - veel sneller neem contact  O(N2). Hier is hoe we het doen. Ik zal eerst beschrijven hoe je een FFT gebruikt voor multi-point evaluatie (dat wil zeggen voor een bepaald domein) D en polynoom P, berekenen P (x) voor iedere x in D), en het blijkt dat je hetzelfde algoritme kunt gebruiken voor interpolatie met een kleine aanpassing.

Stel dat we een FFT hebben waarbij het gegeven domein de machten is van x in een veld, waar x^2^k=1 (bijv. in het geval dat we hierboven hebben geïntroduceerd, is het domein de bevoegdheden van 85 formulier 337 en 85^2^3=1). We hebben een aantal polynoom, bijv. y=6×7+2×6+9×5+5×4+x3+4×2+x+3 (we schrijven het als p=[3,1,4,1,5,9,2,6]). We willen deze polynoom evalueren op elk punt in het domein, dwz. bij elk van de acht machten van 85. Dit is wat we doen.

Eerst splitsen we de polynoom in twee delen, die we zullen noemen egaliseert en kansen: even =[3,4,5,2] en kansen [1,1,9,6] (of even=2×3+5×2+4x+3 en kansen=6×3+9×2+x+1; ja, dit is gewoon het nemen van de even-graden coëfficiënten en de oneven-graden coëfficiënten). Nu merken we een wiskundige observatie op: p(x)=evens(x2)+x-oneven(x2) en p(−x)=evens(x2)−x⋅oneven(x2) (denk hier zelf over na en zorg ervoor dat u het begrijpt voordat u verder gaat).

De "lijm" is relatief eenvoudig (en AAN) in runtime): we ontvangen de evaluaties van evens en odds als maat-N/2 lijsten, dus dat doen we gewoon p[i]=evens_result[i]+domain[i]⋅odds_result[i] en p[N2+i]=evens_result[i]−domain[i]⋅odds_result[i] voor elke index i.

Hier is de volledige code:

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

We kunnen proberen het uit te voeren:

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

En we kunnen het resultaat controleren; het evalueren van de polynoom op de positie 85, bijvoorbeeld, geeft daadwerkelijk het resultaat 70. Merk op dat dit alleen werkt als het domein "correct" is; het moet van de vorm zijn [x^i % modulus voor i in bereik(n)] WAAR x^n=1.

Een inverse FFT is verrassend eenvoudig:

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

Voer in principe de FFT opnieuw uit, maar keer het resultaat om (behalve dat het eerste item op zijn plaats blijft) en deel elke waarde door de lengte van de lijst.

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

Waar kunnen we dit nu voor gebruiken? Hier is een leuke use-case: we kunnen FFT's gebruiken om getallen heel snel te vermenigvuldigen. Stel dat we willen vermenigvuldigen 1253 by 1895. Hier is wat we zouden doen. Eerst zouden we het probleem omzetten in een probleem dat iets eenvoudiger blijkt te zijn: vermenigvuldig de veeltermen [3,5,2,1] by [5,9,8,1] (dat zijn alleen de cijfers van de twee getallen in oplopende volgorde), en zet het antwoord vervolgens terug in een getal door een enkele pas uit te voeren om meer dan tientallen cijfers over te dragen.

We kunnen veeltermen snel vermenigvuldigen met FFT's, want het blijkt dat als je een veelterm omzet in evaluatie formulier (d.w.z. f (x) voor iedere x in een bepaald domein D), dan kun je twee polynomen vermenigvuldigen door simpelweg hun evaluaties te vermenigvuldigen. Dus wat we zullen doen is de polynomen die onze twee getallen vertegenwoordigen in . nemen coëfficiëntvorm, gebruik FFT's om ze om te zetten in een evaluatievorm, vermenigvuldig ze puntsgewijs en converteer ze terug:

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

Dit vereist drie FFT's (elk O(N⋅log(N)) tijd) en een puntsgewijze vermenigvuldiging (AAN) tijd), dus het duurt O(N⋅log(N)) tijd in totaal (technisch een beetje meer dan .) O(N⋅log(N)), omdat u voor zeer grote aantallen moet worden vervangen 337 met een grotere modulus en dat zou vermenigvuldigen moeilijker maken, maar dichtbij genoeg). Dit is veel sneller dan schoolboekvermenigvuldiging, waarvoor O(N2) tijd:

 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

Dus nu nemen we gewoon het resultaat en dragen de tientallen cijfers over (dit is een "één keer door de lijst lopen en op elk punt één ding doen" algoritme, dus het duurt AAN) tijd):

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

En als we de cijfers van boven naar beneden lezen, krijgen we 2374435. Laten we het antwoord controleren….

>>> 1253 * 1895
2374435

Hoera! Het werkte. In de praktijk is bij zulke kleine inputs het verschil tussen O(N⋅log(N)) en O (N ^ 2) is niet dat groot, dus schoolboekvermenigvuldiging is sneller dan dit op FFT gebaseerde vermenigvuldigingsproces, alleen omdat het algoritme eenvoudiger is, maar bij grote invoer maakt het echt een groot verschil.

Maar FFT's zijn niet alleen handig voor het vermenigvuldigen van getallen; zoals hierboven vermeld, zijn polynoomvermenigvuldiging en meerpuntsevaluatie van cruciaal belang bij het implementeren van wiscodering, wat een zeer belangrijke techniek is voor het bouwen van vele soorten redundante fouttolerante systemen. Als u van fouttolerantie houdt en van efficiëntie houdt, zijn FFT's uw vriend.

FFT's en binaire velden

Priemvelden zijn niet het enige soort eindig veld dat er is. Een ander soort eindig veld (echt een speciaal geval van het meer algemene concept van an extensie veld, die een beetje lijken op het eindige-veldequivalent van complexe getallen) zijn binaire velden. In een binair veld wordt elk element uitgedrukt als een polynoom waarbij alle ingangen zijn 0 or 1, bijv. x^3+x+1.

Het toevoegen van polynomen gebeurt modulo 2, en aftrekken is hetzelfde als optellen (as −1=1mod2). We selecteren een onherleidbare polynoom als een modulus (bijv. x^4+x+1; x^4+1 zou niet werken omdat x^4+1 kan worden meegewogen (x2+1)⋅(x2+1) dus het is niet "onherleidbaar"); vermenigvuldiging gebeurt modulo die modulus. Bijvoorbeeld in het binaire veld mod x^4+x+1, vermenigvuldigen x2+1 door x3+1 zou geven x5+x3+x2+1 als je gewoon de vermenigvuldiging doet, maar x^5+x^3+x^2+1=(x^4+x+1)⋅x+(x^3+x+1), dus het resultaat is de rest x^3+x+1.

We kunnen dit voorbeeld uitdrukken als een vermenigvuldigingstabel. Eerst vermenigvuldigen [1,0,0,1] (d.w.z. x^3+1) door [1,0,1] (d.w.z. 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

Het resultaat van de vermenigvuldiging bevat een x ^ 5 term zodat we kunnen aftrekken (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 

En we krijgen het resultaat, [1,1,0,1] (or x3+x+1).

Optel- en vermenigvuldigtabellen voor de binaire veldmod x^4+x+1. Veldelementen worden uitgedrukt als gehele getallen geconverteerd vanuit binair (bijv. x^3+x^2→1100→12)

Binaire velden zijn om twee redenen interessant. Allereerst, als u binaire gegevens wilt wissen, dan zijn binaire velden erg handig omdat: N bytes aan gegevens kunnen direct worden gecodeerd als een binair veldelement, en alle binaire veldelementen die u genereert door er berekeningen op uit te voeren, worden ook N bytes lang. Je kunt dit niet doen met priemvelden omdat de grootte van priemvelden niet precies een macht van twee is; je zou bijvoorbeeld elke . kunnen coderen 2 bytes als een getal van 0 ... 65536 in het priemveld modulo 65537 (wat priem is), maar als je een FFT doet op deze waarden, dan kan de uitvoer bevatten: 65536, die niet kan worden uitgedrukt in twee bytes.

Ten tweede, het feit dat optellen en aftrekken dezelfde bewerking worden, en 1 + = 1 0, creëer wat "structuur" die tot een aantal zeer interessante gevolgen leidt. Een bijzonder interessante en nuttige eigenaardigheid van binaire velden is de "eerstejaars droomstelling: (x+y)^2=x^2+y^2 (en hetzelfde voor exponenten 4,8,16 ... eigenlijk elke macht van twee).

Maar als u binaire velden wilt gebruiken voor het wissen van codering, en dit efficiënt wilt doen, dan moet u Fast Fourier-transformaties over binaire velden kunnen doen. Maar dan is er een probleem: in een binair veld, er zijn geen (niet-triviale) multiplicatieve groepen van orde 2^n. Dit komt omdat de multiplicatieve groepen allemaal orde zijn 2^n-1. Bijvoorbeeld in het binaire veld met modulus x^4+x+1, als je begint met het berekenen van opeenvolgende machten van x + 1, fiets je terug naar 1 na 15 stappen - niet 16. De reden is dat het totale aantal elementen in het veld is 16, maar een ervan is nul, en je zult nooit nul bereiken door een waarde die niet nul is met zichzelf te vermenigvuldigen in een veld, dus de machten van x + 1 cyclus door elk element behalve nul, dus de cycluslengte is 15, Niet 16. Dus wat doen we?

De reden dat we het domein nodig hadden om de "structuur" te hebben van een multiplicatieve groep met eerder 2n elementen, is dat we de grootte van het domein met een factor twee moesten verkleinen door elk nummer erin te kwadrateren: het domein [1,85,148,111,336,252,189,226] wordt gereduceerd tot [1,148,336,189] omdat 1 is het kwadraat van beide 1 en 336, 148 is het kwadraat van beide 85 en 252, enzovoorts.

Maar wat als er in een binair veld een andere manier is om de grootte van een domein te halveren? Het blijkt dat er: gegeven een domein met 2 ^ k waarden, inclusief nul (technisch gezien moet het domein a subspace), kunnen we een nieuw domein D′ van halve grootte construeren door te nemen x⋅(x+k) For x in D met behulp van een aantal specifieke k in D. Omdat het oorspronkelijke domein een deelruimte is, aangezien k is in het domein, any x in het domein heeft een overeenkomstige x+k ook in het domein, en de functie f(x)=x⋅(x+k) geeft dezelfde waarde terug voor x en x+k dus we krijgen dezelfde soort twee-op-een-correspondentie die kwadrateren ons geeft.

Dus nu, hoe doen we hier een FFT bovenop? We gebruiken dezelfde truc, een probleem omzetten met een N-grote polynoom en N-sized domein in twee problemen elk met een N / 2-grote polynoom en N / 2-sized domein, maar deze keer met andere vergelijkingen. We zetten een polynoom p om in twee polynomen egaliseert en kansen zoals dat p(x)=evens(x⋅(k−x))+x⋅oneven(x⋅(k−x)). Merk op dat voor de even en oneven die we vinden, het zal ook wees waar dat p(x+k)=evens(x⋅(k−x))+(x+k)⋅oneven(x⋅(k−x)). Dus we kunnen dan recursief een FFT doen naar even en oneven op het gereduceerde domein [x⋅(k−x) voor x in D], en dan gebruiken we deze twee formules om de antwoorden te krijgen voor twee "helften" van het domein, de ene verschoven door k van de andere.

p omzetten in egaliseert en kansen zoals hierboven beschreven blijkt op zichzelf niet triviaal te zijn. Het "naïeve" algoritme om dit te doen is zichzelf O (N ^ 2), maar het blijkt dat we in een binair veld het feit kunnen gebruiken dat (x2−kx)2=x4−k2⋅x2, en meer in het algemeen (x2−kx)2i=x2i+1−k2i⋅x2i , om nog een ander recursief algoritme te maken om dit te doen in O(N⋅log(N)) tijd.

En als je een wilt doen omgekeerde FFT, om interpolatie uit te voeren, moet u de stappen in het algoritme in omgekeerde volgorde uitvoeren. De volledige code om dit te doen vind je hier: https://github.com/ethereum/research/tree/master/binary_fft, en een paper met details over meer optimale algoritmen hier: http://www.math.clemson.edu/~sgao/papers/GM10.pdf

Dus wat halen we uit al deze complexiteit? Welnu, we kunnen proberen de implementatie uit te voeren, die zowel een "naïeve" O (N ^ 2) evaluatie op meerdere punten en de geoptimaliseerde op FFT gebaseerde evaluatie, en beide tijd. Hier zijn mijn resultaten:

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

En naarmate de polynoom groter wordt, wordt de naïeve implementatie (_eenvoudig_ft) wordt veel sneller langzamer dan de 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

En voila, we hebben een efficiënte, schaalbare manier om polynomen op meerdere punten te evalueren en te interpoleren. Als we FFT's willen gebruiken om gecodeerde gegevens te herstellen waar we zijn vermist sommige stukken, dan algoritmen hiervoor bestaan ​​ook, hoewel ze iets minder efficiënt zijn dan gewoon een enkele FFT doen. Genieten van!

Dit artikel is oorspronkelijk gepubliceerd als "Snelle Fourier-transformaties"

PlatoAi. Web3 opnieuw uitgevonden. Gegevensintelligentie versterkt.
Klik hier om toegang te krijgen.

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