Greitoji Fourier transformacija su dvejetainiu skaidymu
Kai N yra dvejeto laipsnis, suskirstykite daugianario koeficientus pagal lyginius ir nelyginius indeksus, rekursyviai transformuokite kiekvieną pusę ir sujunkite reikšmes pagal p(z)=p_even(z²)+zp_odd(z²).
Esminės žinios
Kai N yra dvejeto laipsnis, suskirstykite daugianario koeficientus pagal lyginius ir nelyginius indeksus, rekursyviai transformuokite kiekvieną pusę ir sujunkite reikšmes pagal p(z)=p_even(z²)+zp_odd(z²). Rekurentinis sąryšis T(N)=2T(N/2)+Θ(N) duoda Θ(N log N) aritmetinių operacijų su kompleksiniais skaičiais. Papildžius koeficientų sekas iki ilgio, viršijančio sandaugos laipsnį, daugianariai dauginami transformuojant, dauginant reikšmes ir atliekant atvirkštinę transformaciją.
Sąlygos ir taikymo ribos
- Įvertis skaičiuoja aritmetines operacijas su kompleksiniais skaičiais; bitų tikslumas ir apvalinimo paklaidos analizuojami atskirai.
- Papildymas neleidžia daugianarių sandaugos koeficientams cikliškai persidengti.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 5 FFT ir atvirkštinės transformacijos algoritmai, rekurentinis sąryšis ir FFT-MULTIPLY skyriuose 5.1.1–5.1.2; pasenusi išnaša apie sveikųjų skaičių daugybą neįtraukta.
2026-10-10 · Nepriklausoma AI redakcinė peržiūra: Perskaityti visi241 glausti teiginiai, prielaidos, pateiktos lygtys ir konvencijos bei visos596 iš šių įrašų išeinančios semantinės sąsajos; peržiūrėta visa autoriaus tikslių šaltinių patikros matrica, turinti241 įrašą, ir deklaruoti apribojimai. Siekiant aprėpti visą inventorių, perskaityti ankstesni105 faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tiksliniai nepriklausomai perskaityti pirminių šaltinių skyriai; tai NEREIŠKIA, kad nepriklausomai iš naujo perskaitytas kiekvienas cituotas šaltinio tekstas ar kiekvienas įrodymas. Tai AI atliekama informacinio turinio peržiūra, o ne žmogaus atliekamas dalykinis sertifikavimas, išsamus vadovėlio atkūrimas ar eksperimentų pakartojimas. Peržiūros dokumentas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-fast-fourier-transform
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra