Кіріспе
Радер алгоритмі (1968), MIT Линкольн зертханасының Чарльз М. Радерінің есімімен аталатын, дискретті Фурье түрлендіруін (DFT) жай сандардың мөлшері үшін есептейтін жылдам Фурье түрлендіруі (FFT) алгоритмі. Бұл DFT-ді циклдық конволюция ретінде қайта жазу арқылы жасалады (басқа FFT алгоритмі, Блустейн алгоритмі, жай сандардың мөлшері үшін DFT-ді де конволюция ретінде қайта жазу арқылы жұмыс істейді). Радер алгоритмі DFT ядросының периодтығына ғана байланысты болғандықтан, сандық теориялық түрлендіру немесе дискретті Хартли түрлендіруі сияқты ұқсас қасиеттері бар кез келген басқа түрлендіруге (жақын реттік) тікелей қолданылады. Алгоритмді нақты деректердің DFT үшін екі есе үнемділікке жету үшін өзгертуге болады, нақты деректердің екі жартылай циклдық конволюциясын алу үшін сәл өзгертілген қайта индекстеу/пермутация қолдану арқылы; нақты деректердің DFT үшін баламалы бейімдеу дискретті Хартли түрлендіруін пайдаланады. Винноград Радер алгоритмін жақын сандардың күші DFT мөлшерлерін қосу үшін кеңейтті, ал бүгінде Радер алгоритмі кейде Винноградтың FFT алгоритмінің ерекше жағдайы ретінде сипатталады, сонымен қатар көбейтуші Фурье түрлендіру алгоритмі деп те аталады (Толимиэри және басқалар, 1997), ол тіпті үлкен мөлшерлер класына қолданылады. Дегенмен, жақын сандардың күштері сияқты күрделі мөлшерлер үшін Кули-Туки FFT алгоритмі әлдеқайда қарапайым және практикалық болып табылады, сондықтан Радер алгоритмі әдетте Кули-Туки DFT рекурсивті декомпозициясының үлкен жақын негіздік жағдайлары үшін ғана қолданылады.). Бұл генератор – кез келген нөлдік емес индекс n үшін және бірегей (q-дан нөлдік емес n-ге дейін биекция құратын) g бүтін саны. Сол сияқты, кез келген нөлдік емес k индексі үшін және бірегей , мұндағы теріс дәреже – көбейтудің кері шамасын білдіреді. Бұл DFT-ді осы жаңа индекстер p және q арқылы қайта жазуға мүмкіндік береді: (xn және Xk N бойынша периодты екенін және сонымен қатар (Эйлер теңдігі) екенін еске түсіріңіз. Осылайша, барлық индекстер мен дәрежелер топтық арифметика талап ететіндей N модулі бойынша алынады.) Жоғарыдағы соңғы қосынды екі тізбектің – aq және bq (ұзындығы N–1, себебі ) циклдық конволюциясы болып табылады, ол былай анықталады:
Rader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution). Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a number theoretic transform or the discrete Hartley transform. The algorithm can be modified to gain a factor of two savings for the case of DFTs of real data, using a slightly modified re indexing/permutation to obtain two half size cyclic convolutions of real data; an alternative adaptation for DFTs of real data uses the discrete Hartley transform. Winograd extended Rader's algorithm to include prime power DFT sizes , and today Rader's algorithm is sometimes described as a special case of Winograd's FFT algorithm, also called the multiplicative Fourier transform algorithm (Tolimieri et al., 1997), which applies to an even larger class of sizes. However, for composite sizes such as prime powers, the Cooley–Tukey FFT algorithm is much simpler and more practical to implement, so Rader's algorithm is typically only used for large prime base cases of Cooley–Tukey's recursive decomposition of the DFT.). This generator is an integer g such that for any non zero index n and for a unique (forming a bijection from q to non zero n). Similarly, for any non zero index k and for a unique , where the negative exponent denotes the multiplicative inverse of That means that we can rewrite the DFT using these new indices p and q as:
(Recall that xn and Xk are implicitly periodic in N, and also that (Euler's identity). Thus, all indices and exponents are taken modulo N as required by the group arithmetic.) The final summation, above, is precisely a cyclic convolution of the two sequences aq and bq (of length N–1, because ) defined by:
Қиылысуды бағалау
N–1 құрама сан болғандықтан, бұл конволюцияны конволюция теоремасы және дәстүрлі FFT алгоритмдері арқылы тікелей орындауға болады. Дегенмен, егер N–1 өзі үлкен жай сандарға ие болса, бұл тиімді болмауы мүмкін, сонда Радер алгоритмін рекурсивті қолдану қажет болады. Оның орнына, ұзындығы (N–1) циклдық конволюцияны кем дегенде 2(N–1)–1 ұзындығына нөлдермен толтыру арқылы дәл есептеуге болады, мысалы, екінің дәрежесіне дейін, содан кейін оны Радер алгоритмін рекурсивті қолданбай O(N log N) уақытында бағалауға болады. Осы алгоритмге O(N) қосылым және конволюция үшін O(N log N) уақыт қажет. Іс жүзінде, O(N) қосылымдарды көбінесе конволюцияға сіңіру арқылы орындауға болады: егер конволюция FFT жұбы арқылы орындалса, онда xn қосындысы aq + x0 FFT-нің DC (0-шы) шығысымен беріледі, ал x0 кері FFT-ден бұрын конволюцияның DC мүшесіне қосылып, барлық шығыстарға қосылуы мүмкін. Дегенмен, бұл алгоритм жақын орналасқан құрама өлшемдердегі FFT-ге қарағанда көбірек операцияларды қажет етеді және әдетте практикада 3–10 есе ұзаққа созылады. Егер Радер алгоритмі жоғарыда айтылғандай нөлдермен толтыру арқылы емес, конволюцияны есептеу үшін N–1 өлшемді FFT-терді пайдалану арқылы орындалса, тиімділік N және Радер алгоритмін рекурсивті қолдану қажеттілігіне күшті түрде байланысты. Ең нашар жағдай – егер N–1 = 2N2 болса, мұнда N2 жай сан, ал N2–1 = 2N3, мұнда N3 жай сан, және т.б. Мұндай жағдайларда, егер жай сандар тізбегі белгілі бір шекті мәнге дейін созылса, Радер алгоритмін рекурсивті қолдану үшін шын мәнінде O(N2) уақыт қажет болады. Мұндай Nj сандары Софи Жермен жай сандары деп аталады, ал олардың мұндай тізбегі бірінші түріндегі Каннингем тізбегі деп аталады. Алайда, Каннингем тізбегінің ұзындығы log2(N) қарағанда баяу өседі, сондықтан осылай қолданылатын Радер алгоритмі, мүмкін, O(N2 емес, бірақ ең нашар жағдайларда O(N log N) қарағанда нашар болуы мүмкін. Бақытымызға орай, нөлдермен толтыру арқылы O(N log N) күрделілігіне кепілдік беруге болады.