968:
607:
90:), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a
1056:/4) Cooley–Tukey steps, respectively. (The underlying idea is that the even-index subtransform of radix-2 has no multiplicative factor in front of it, so it should be left as-is, while the odd-index subtransform of radix-2 benefits by combining a second recursive subdivision.)
405:
The split-radix algorithm works by expressing this summation in terms of three smaller summations. (Here, we give the "decimation in time" version of the split-radix FFT; the dual decimation in frequency version is essentially just the reverse of these steps.)
2270:
2120:
1973:
1843:
963:{\displaystyle X_{k}=\sum _{n_{2}=0}^{N/2-1}x_{2n_{2}}\omega _{N/2}^{n_{2}k}+\omega _{N}^{k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+1}\omega _{N/4}^{n_{4}k}+\omega _{N}^{3k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+3}\omega _{N/4}^{n_{4}k}}
1399:
195:
1722:
1642:
359:
1038:
81:. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for
2485:
2753:
2696:
2643:
1264:
1151:
400:
1565:
1530:
534:
491:
2586:
1208:
291:
448:
1436:
1470:
69:
The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required
2126:
2535:
2512:
2441:
2374:
2300:
1979:
1291:
1178:
1095:
599:
565:
2407:
264:
2340:
2320:
238:
218:
94:, the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)
1849:
1733:
2379:
Notice that these expressions are arranged so that we need to combine the various DFT outputs by pairs of additions and subtractions, which are known as
1299:
2759:>1 a power of two. This count assumes that, for odd powers of 2, the leftover factor of 2 (after all the split-radix steps, which divide
2763:
by 4) is handled directly by the DFT definition (4 real additions and multiplications), or equivalently by a radix-2 Cooley–Tukey FFT step.
38:
and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors,
115:
1648:
1045:
47:
101:
is a multiple of 4, but since it breaks a DFT into smaller DFTs it can be combined with any other FFT algorithm as desired.
1577:
303:
976:
2537:
are ordinarily counted as free (all negations can be absorbed by converting additions into subtractions or vice versa).
2383:. In order to obtain the minimal operation count for this algorithm, one needs to take into account special cases for
2806:
J. B. Martens, "Recursive cyclotomic factorization—a new algorithm for calculating the discrete
Fourier transform,"
28:
88:
2873:
2446:
24:
43:
2704:
2648:
2595:
1217:
1104:
367:
1535:
2796:
M. Vetterli and H. J. Nussbaumer, "Simple FFT and DCT algorithms with reduced number of operations,"
1503:
410:
39:
496:
453:
2816:
P. Duhamel and M. Vetterli, "Fast
Fourier transforms: a tutorial review and a state of the art,"
2551:
269:
416:
86:
2265:{\displaystyle X_{k+3N/4}=U_{k+N/4}+i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),}
1407:
2380:
2115:{\displaystyle X_{k+N/4}=U_{k+N/4}-i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),}
1441:
32:
1183:
537:
2517:
2494:
2412:
2345:
2278:
1269:
1156:
1073:
570:
543:
2386:
1968:{\displaystyle X_{k+N/2}=U_{k}-\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),}
243:
2325:
2305:
1568:
223:
203:
2853:
H. V. Sorensen, M. T. Heideman, and C. S. Burrus, "On computing the split-radix FFT",
2867:
1838:{\displaystyle X_{k}=U_{k}+\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),}
294:
74:
2773:
70:
51:
31:(DFT), and was first described in an initially little-appreciated paper by
91:
36:
2841:
1394:{\displaystyle X_{k}=U_{k}+\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}.}
450:. Second, a summation over the odd indices broken into two pieces:
2827:
2774:
An economical method for calculating the discrete
Fourier transform
1067:/4, which can be performed recursively and then recombined.
190:{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk}}
2828:
A modified split-radix FFT with fewer arithmetic operations
2786:
P. Duhamel and H. Hollmann, "Split-radix FFT algorithm,"
2544:
is a power of two. The base cases of the recursion are
2487:
and can be multiplied more quickly); see, e.g. Sorensen
1717:{\displaystyle \omega _{N}^{3(k+N/4)}=i\omega _{N}^{3k}}
1404:
This, however, performs unnecessary calculations, since
1059:
These smaller summations are now exactly DFTs of length
1484:/4 DFTs are not changed (because they are periodic in
2707:
2651:
2598:
2554:
2520:
2497:
2449:
2415:
2389:
2348:
2328:
2308:
2281:
2129:
1982:
1852:
1736:
1651:
1637:{\displaystyle \omega _{N}^{k+N/4}=-i\omega _{N}^{k}}
1580:
1538:
1506:
1444:
1410:
1302:
1272:
1220:
1186:
1159:
1107:
1076:
979:
610:
573:
546:
499:
456:
419:
370:
354:{\displaystyle \omega _{N}=e^{-{\frac {2\pi i}{N}}},}
306:
272:
246:
226:
206:
118:
1033:{\displaystyle \omega _{N}^{mnk}=\omega _{N/m}^{nk}}
97:The split-radix algorithm can only be applied when
73:additions and multiplications) to compute a DFT of
46:.) In particular, split radix is a variant of the
2846:
2747:
2690:
2637:
2580:
2529:
2506:
2479:
2435:
2401:
2368:
2334:
2314:
2294:
2264:
2114:
1967:
1837:
1716:
1636:
1559:
1524:
1464:
1430:
1393:
1285:
1258:
1202:
1172:
1145:
1089:
1032:
962:
593:
559:
528:
485:
442:
394:
353:
285:
258:
232:
212:
189:
2540:This decomposition is performed recursively when
109:Recall that the DFT is defined by the formula:
2855:IEEE Trans. Acoust., Speech, Signal Processing
2808:IEEE Trans. Acoust., Speech, Signal Processing
2409:(where the twiddle factors are unity) and for
8:
536:, according to whether the index is 1 or 3
1500:. So, the only things that change are the
2718:
2706:
2682:
2669:
2656:
2650:
2629:
2616:
2603:
2597:
2572:
2559:
2553:
2519:
2496:
2470:
2465:
2448:
2425:
2414:
2388:
2352:
2347:
2327:
2307:
2286:
2280:
2245:
2232:
2227:
2214:
2204:
2199:
2174:
2164:
2147:
2134:
2128:
2095:
2082:
2077:
2064:
2054:
2049:
2024:
2014:
1997:
1987:
1981:
1948:
1935:
1930:
1917:
1907:
1902:
1884:
1867:
1857:
1851:
1818:
1805:
1800:
1787:
1777:
1772:
1754:
1741:
1735:
1705:
1700:
1677:
1661:
1656:
1650:
1628:
1623:
1600:
1590:
1585:
1579:
1548:
1543:
1537:
1516:
1511:
1505:
1454:
1443:
1438:turn out to share many calculations with
1420:
1409:
1379:
1366:
1361:
1348:
1338:
1333:
1320:
1307:
1301:
1277:
1271:
1242:
1219:
1210:denote the results of the DFTs of length
1191:
1185:
1164:
1158:
1129:
1106:
1081:
1075:
1021:
1012:
1008:
989:
984:
978:
949:
944:
935:
931:
913:
905:
885:
881:
868:
863:
850:
845:
827:
822:
813:
809:
791:
783:
763:
759:
746:
741:
731:
726:
708:
703:
694:
690:
678:
670:
650:
646:
633:
628:
615:
609:
577:
572:
551:
545:
512:
504:
498:
469:
461:
455:
432:
424:
418:
380:
375:
369:
328:
324:
311:
305:
277:
271:
245:
225:
205:
178:
173:
163:
147:
136:
123:
117:
50:that uses a blend of radices 2 and 4: it
2755:real additions and multiplications, for
2701:These considerations result in a count:
1097:denote the result of the DFT of length
601:. The resulting summations look like:
58:in terms of one smaller DFT of length
2778:Proc. AFIPS Fall Joint Computer Conf.
567:denotes an index that runs from 0 to
7:
2480:{\displaystyle (1\pm i)/{\sqrt {2}}}
1040:. These three sums correspond to
62:/2 and two smaller DFTs of length
27:(FFT) algorithm for computing the
14:
2748:{\displaystyle 4N\log _{2}N-6N+8}
2691:{\displaystyle X_{1}=x_{0}-x_{1}}
2638:{\displaystyle X_{0}=x_{0}+x_{1}}
2592:=2, where the DFT is an addition
2548:=1, where the DFT is just a copy
1259:{\displaystyle k=0,\ldots ,N/4-1}
1146:{\displaystyle k=0,\ldots ,N/2-1}
973:where we have used the fact that
395:{\displaystyle \omega _{N}^{N}=1}
1571:. Here, we use the identities:
1560:{\displaystyle \omega _{N}^{3k}}
16:Fast Fourier transform algorithm
2443:(where the twiddle factors are
2376:in the above four expressions.
2275:which gives all of the outputs
1525:{\displaystyle \omega _{N}^{k}}
2462:
2450:
1685:
1665:
1492:/2 DFT is unchanged if we add
1:
2826:S. G. Johnson and M. Frigo, "
2491:(1986). Multiplications by
1472:. In particular, if we add
529:{\displaystyle x_{4n_{4}+3}}
486:{\displaystyle x_{4n_{4}+1}}
409:First, a summation over the
2832:IEEE Trans. Signal Process.
2581:{\displaystyle X_{0}=x_{0}}
286:{\displaystyle \omega _{N}}
220:is an integer ranging from
2890:
2842:Split-radix FFT algorithms
443:{\displaystyle x_{2n_{2}}}
54:expresses a DFT of length
48:Cooley–Tukey FFT algorithm
29:discrete Fourier transform
1431:{\displaystyle k\geq N/4}
105:Split-radix decomposition
2850:web site (Nov. 2, 2006).
1465:{\displaystyle k<N/4}
1070:More specifically, let
2749:
2692:
2639:
2582:
2531:
2508:
2481:
2437:
2403:
2370:
2336:
2316:
2296:
2266:
2116:
1969:
1839:
1727:to finally arrive at:
1718:
1638:
1561:
1526:
1466:
1432:
1395:
1287:
1260:
1204:
1203:{\displaystyle Z'_{k}}
1174:
1147:
1091:
1052:/2) and radix-4 (size
1034:
964:
900:
778:
665:
595:
561:
530:
487:
444:
396:
355:
293:denotes the primitive
287:
260:
234:
214:
191:
158:
25:fast Fourier transform
2750:
2693:
2640:
2583:
2532:
2530:{\displaystyle \pm i}
2509:
2507:{\displaystyle \pm 1}
2482:
2438:
2436:{\displaystyle k=N/8}
2404:
2371:
2369:{\displaystyle N/4-1}
2337:
2317:
2297:
2295:{\displaystyle X_{k}}
2267:
2117:
1970:
1840:
1719:
1639:
1562:
1527:
1467:
1433:
1396:
1288:
1286:{\displaystyle X_{k}}
1261:
1205:
1175:
1173:{\displaystyle Z_{k}}
1148:
1092:
1090:{\displaystyle U_{k}}
1035:
965:
859:
737:
624:
596:
594:{\displaystyle N/m-1}
562:
560:{\displaystyle n_{m}}
531:
488:
445:
397:
356:
288:
261:
235:
215:
192:
132:
2860:(1), 152–156 (1986).
2837:(1), 111–119 (2007).
2813:(4), 750–761 (1984).
2803:(4), 267–278 (1984).
2705:
2649:
2596:
2552:
2518:
2495:
2447:
2413:
2387:
2346:
2326:
2306:
2279:
2127:
1980:
1850:
1734:
1649:
1578:
1536:
1504:
1488:/4), while the size-
1442:
1408:
1300:
1270:
1266:). Then the output
1218:
1184:
1157:
1105:
1074:
977:
608:
571:
544:
497:
454:
417:
368:
304:
270:
244:
224:
204:
116:
2840:Douglas L. Jones, "
2402:{\displaystyle k=0}
2253:
2240:
2209:
2103:
2090:
2059:
1956:
1943:
1912:
1826:
1813:
1782:
1713:
1689:
1633:
1609:
1556:
1521:
1387:
1374:
1343:
1199:
1029:
1000:
959:
858:
837:
736:
718:
385:
259:{\displaystyle N-1}
186:
2793:(1), 14–16 (1984).
2745:
2688:
2645:and a subtraction
2635:
2578:
2527:
2504:
2477:
2433:
2399:
2366:
2332:
2312:
2292:
2262:
2241:
2223:
2195:
2112:
2091:
2073:
2045:
1965:
1944:
1926:
1898:
1835:
1814:
1796:
1768:
1714:
1696:
1652:
1634:
1619:
1581:
1557:
1539:
1522:
1507:
1462:
1428:
1391:
1375:
1357:
1329:
1283:
1256:
1200:
1187:
1170:
1143:
1087:
1030:
1004:
980:
960:
927:
841:
805:
722:
686:
591:
557:
526:
483:
440:
392:
371:
351:
283:
256:
230:
210:
187:
169:
2823:, 259–299 (1990).
2818:Signal Processing
2798:Signal Processing
2783:, 115–125 (1968).
2475:
2335:{\displaystyle 0}
2315:{\displaystyle k}
344:
233:{\displaystyle 0}
213:{\displaystyle k}
2881:
2754:
2752:
2751:
2746:
2723:
2722:
2697:
2695:
2694:
2689:
2687:
2686:
2674:
2673:
2661:
2660:
2644:
2642:
2641:
2636:
2634:
2633:
2621:
2620:
2608:
2607:
2587:
2585:
2584:
2579:
2577:
2576:
2564:
2563:
2536:
2534:
2533:
2528:
2513:
2511:
2510:
2505:
2486:
2484:
2483:
2478:
2476:
2471:
2469:
2442:
2440:
2439:
2434:
2429:
2408:
2406:
2405:
2400:
2375:
2373:
2372:
2367:
2356:
2341:
2339:
2338:
2333:
2321:
2319:
2318:
2313:
2301:
2299:
2298:
2293:
2291:
2290:
2271:
2269:
2268:
2263:
2258:
2254:
2249:
2239:
2231:
2219:
2218:
2208:
2203:
2183:
2182:
2178:
2156:
2155:
2151:
2121:
2119:
2118:
2113:
2108:
2104:
2099:
2089:
2081:
2069:
2068:
2058:
2053:
2033:
2032:
2028:
2006:
2005:
2001:
1974:
1972:
1971:
1966:
1961:
1957:
1952:
1942:
1934:
1922:
1921:
1911:
1906:
1889:
1888:
1876:
1875:
1871:
1844:
1842:
1841:
1836:
1831:
1827:
1822:
1812:
1804:
1792:
1791:
1781:
1776:
1759:
1758:
1746:
1745:
1723:
1721:
1720:
1715:
1712:
1704:
1688:
1681:
1660:
1643:
1641:
1640:
1635:
1632:
1627:
1608:
1604:
1589:
1567:terms, known as
1566:
1564:
1563:
1558:
1555:
1547:
1531:
1529:
1528:
1523:
1520:
1515:
1471:
1469:
1468:
1463:
1458:
1437:
1435:
1434:
1429:
1424:
1400:
1398:
1397:
1392:
1383:
1373:
1365:
1353:
1352:
1342:
1337:
1325:
1324:
1312:
1311:
1292:
1290:
1289:
1284:
1282:
1281:
1265:
1263:
1262:
1257:
1246:
1209:
1207:
1206:
1201:
1195:
1179:
1177:
1176:
1171:
1169:
1168:
1152:
1150:
1149:
1144:
1133:
1096:
1094:
1093:
1088:
1086:
1085:
1039:
1037:
1036:
1031:
1028:
1020:
1016:
999:
988:
969:
967:
966:
961:
958:
954:
953:
943:
939:
926:
925:
918:
917:
899:
889:
880:
873:
872:
857:
849:
836:
832:
831:
821:
817:
804:
803:
796:
795:
777:
767:
758:
751:
750:
735:
730:
717:
713:
712:
702:
698:
685:
684:
683:
682:
664:
654:
645:
638:
637:
620:
619:
600:
598:
597:
592:
581:
566:
564:
563:
558:
556:
555:
535:
533:
532:
527:
525:
524:
517:
516:
492:
490:
489:
484:
482:
481:
474:
473:
449:
447:
446:
441:
439:
438:
437:
436:
401:
399:
398:
393:
384:
379:
360:
358:
357:
352:
347:
346:
345:
340:
329:
316:
315:
292:
290:
289:
284:
282:
281:
265:
263:
262:
257:
239:
237:
236:
231:
219:
217:
216:
211:
196:
194:
193:
188:
185:
177:
168:
167:
157:
146:
128:
127:
2889:
2888:
2884:
2883:
2882:
2880:
2879:
2878:
2864:
2863:
2788:Electron. Lett.
2769:
2714:
2703:
2702:
2678:
2665:
2652:
2647:
2646:
2625:
2612:
2599:
2594:
2593:
2568:
2555:
2550:
2549:
2516:
2515:
2493:
2492:
2445:
2444:
2411:
2410:
2385:
2384:
2344:
2343:
2324:
2323:
2304:
2303:
2282:
2277:
2276:
2210:
2194:
2190:
2160:
2130:
2125:
2124:
2060:
2044:
2040:
2010:
1983:
1978:
1977:
1913:
1897:
1893:
1880:
1853:
1848:
1847:
1783:
1767:
1763:
1750:
1737:
1732:
1731:
1647:
1646:
1576:
1575:
1569:twiddle factors
1534:
1533:
1502:
1501:
1440:
1439:
1406:
1405:
1344:
1316:
1303:
1298:
1297:
1273:
1268:
1267:
1216:
1215:
1182:
1181:
1160:
1155:
1154:
1103:
1102:
1077:
1072:
1071:
975:
974:
945:
909:
901:
864:
823:
787:
779:
742:
704:
674:
666:
629:
611:
606:
605:
569:
568:
547:
542:
541:
508:
500:
495:
494:
465:
457:
452:
451:
428:
420:
415:
414:
366:
365:
330:
320:
307:
302:
301:
273:
268:
267:
242:
241:
222:
221:
202:
201:
159:
119:
114:
113:
107:
21:split-radix FFT
17:
12:
11:
5:
2887:
2885:
2877:
2876:
2874:FFT algorithms
2866:
2865:
2862:
2861:
2851:
2838:
2824:
2814:
2804:
2794:
2784:
2768:
2765:
2744:
2741:
2738:
2735:
2732:
2729:
2726:
2721:
2717:
2713:
2710:
2685:
2681:
2677:
2672:
2668:
2664:
2659:
2655:
2632:
2628:
2624:
2619:
2615:
2611:
2606:
2602:
2575:
2571:
2567:
2562:
2558:
2526:
2523:
2503:
2500:
2474:
2468:
2464:
2461:
2458:
2455:
2452:
2432:
2428:
2424:
2421:
2418:
2398:
2395:
2392:
2365:
2362:
2359:
2355:
2351:
2331:
2311:
2289:
2285:
2273:
2272:
2261:
2257:
2252:
2248:
2244:
2238:
2235:
2230:
2226:
2222:
2217:
2213:
2207:
2202:
2198:
2193:
2189:
2186:
2181:
2177:
2173:
2170:
2167:
2163:
2159:
2154:
2150:
2146:
2143:
2140:
2137:
2133:
2122:
2111:
2107:
2102:
2098:
2094:
2088:
2085:
2080:
2076:
2072:
2067:
2063:
2057:
2052:
2048:
2043:
2039:
2036:
2031:
2027:
2023:
2020:
2017:
2013:
2009:
2004:
2000:
1996:
1993:
1990:
1986:
1975:
1964:
1960:
1955:
1951:
1947:
1941:
1938:
1933:
1929:
1925:
1920:
1916:
1910:
1905:
1901:
1896:
1892:
1887:
1883:
1879:
1874:
1870:
1866:
1863:
1860:
1856:
1845:
1834:
1830:
1825:
1821:
1817:
1811:
1808:
1803:
1799:
1795:
1790:
1786:
1780:
1775:
1771:
1766:
1762:
1757:
1753:
1749:
1744:
1740:
1725:
1724:
1711:
1708:
1703:
1699:
1695:
1692:
1687:
1684:
1680:
1676:
1673:
1670:
1667:
1664:
1659:
1655:
1644:
1631:
1626:
1622:
1618:
1615:
1612:
1607:
1603:
1599:
1596:
1593:
1588:
1584:
1554:
1551:
1546:
1542:
1519:
1514:
1510:
1461:
1457:
1453:
1450:
1447:
1427:
1423:
1419:
1416:
1413:
1402:
1401:
1390:
1386:
1382:
1378:
1372:
1369:
1364:
1360:
1356:
1351:
1347:
1341:
1336:
1332:
1328:
1323:
1319:
1315:
1310:
1306:
1280:
1276:
1255:
1252:
1249:
1245:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1198:
1194:
1190:
1167:
1163:
1142:
1139:
1136:
1132:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1084:
1080:
1027:
1024:
1019:
1015:
1011:
1007:
1003:
998:
995:
992:
987:
983:
971:
970:
957:
952:
948:
942:
938:
934:
930:
924:
921:
916:
912:
908:
904:
898:
895:
892:
888:
884:
879:
876:
871:
867:
862:
856:
853:
848:
844:
840:
835:
830:
826:
820:
816:
812:
808:
802:
799:
794:
790:
786:
782:
776:
773:
770:
766:
762:
757:
754:
749:
745:
740:
734:
729:
725:
721:
716:
711:
707:
701:
697:
693:
689:
681:
677:
673:
669:
663:
660:
657:
653:
649:
644:
641:
636:
632:
627:
623:
618:
614:
590:
587:
584:
580:
576:
554:
550:
523:
520:
515:
511:
507:
503:
480:
477:
472:
468:
464:
460:
435:
431:
427:
423:
391:
388:
383:
378:
374:
362:
361:
350:
343:
339:
336:
333:
327:
323:
319:
314:
310:
280:
276:
255:
252:
249:
229:
209:
198:
197:
184:
181:
176:
172:
166:
162:
156:
153:
150:
145:
142:
139:
135:
131:
126:
122:
106:
103:
15:
13:
10:
9:
6:
4:
3:
2:
2886:
2875:
2872:
2871:
2869:
2859:
2856:
2852:
2849:
2848:
2843:
2839:
2836:
2833:
2829:
2825:
2822:
2819:
2815:
2812:
2809:
2805:
2802:
2799:
2795:
2792:
2789:
2785:
2782:
2779:
2775:
2771:
2770:
2766:
2764:
2762:
2758:
2742:
2739:
2736:
2733:
2730:
2727:
2724:
2719:
2715:
2711:
2708:
2699:
2683:
2679:
2675:
2670:
2666:
2662:
2657:
2653:
2630:
2626:
2622:
2617:
2613:
2609:
2604:
2600:
2591:
2573:
2569:
2565:
2560:
2556:
2547:
2543:
2538:
2524:
2521:
2501:
2498:
2490:
2472:
2466:
2459:
2456:
2453:
2430:
2426:
2422:
2419:
2416:
2396:
2393:
2390:
2382:
2377:
2363:
2360:
2357:
2353:
2349:
2329:
2309:
2287:
2283:
2259:
2255:
2250:
2246:
2242:
2236:
2233:
2228:
2224:
2220:
2215:
2211:
2205:
2200:
2196:
2191:
2187:
2184:
2179:
2175:
2171:
2168:
2165:
2161:
2157:
2152:
2148:
2144:
2141:
2138:
2135:
2131:
2123:
2109:
2105:
2100:
2096:
2092:
2086:
2083:
2078:
2074:
2070:
2065:
2061:
2055:
2050:
2046:
2041:
2037:
2034:
2029:
2025:
2021:
2018:
2015:
2011:
2007:
2002:
1998:
1994:
1991:
1988:
1984:
1976:
1962:
1958:
1953:
1949:
1945:
1939:
1936:
1931:
1927:
1923:
1918:
1914:
1908:
1903:
1899:
1894:
1890:
1885:
1881:
1877:
1872:
1868:
1864:
1861:
1858:
1854:
1846:
1832:
1828:
1823:
1819:
1815:
1809:
1806:
1801:
1797:
1793:
1788:
1784:
1778:
1773:
1769:
1764:
1760:
1755:
1751:
1747:
1742:
1738:
1730:
1729:
1728:
1709:
1706:
1701:
1697:
1693:
1690:
1682:
1678:
1674:
1671:
1668:
1662:
1657:
1653:
1645:
1629:
1624:
1620:
1616:
1613:
1610:
1605:
1601:
1597:
1594:
1591:
1586:
1582:
1574:
1573:
1572:
1570:
1552:
1549:
1544:
1540:
1517:
1512:
1508:
1499:
1495:
1491:
1487:
1483:
1479:
1475:
1459:
1455:
1451:
1448:
1445:
1425:
1421:
1417:
1414:
1411:
1388:
1384:
1380:
1376:
1370:
1367:
1362:
1358:
1354:
1349:
1345:
1339:
1334:
1330:
1326:
1321:
1317:
1313:
1308:
1304:
1296:
1295:
1294:
1278:
1274:
1253:
1250:
1247:
1243:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1213:
1196:
1192:
1188:
1165:
1161:
1140:
1137:
1134:
1130:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1100:
1082:
1078:
1068:
1066:
1062:
1057:
1055:
1051:
1047:
1043:
1025:
1022:
1017:
1013:
1009:
1005:
1001:
996:
993:
990:
985:
981:
955:
950:
946:
940:
936:
932:
928:
922:
919:
914:
910:
906:
902:
896:
893:
890:
886:
882:
877:
874:
869:
865:
860:
854:
851:
846:
842:
838:
833:
828:
824:
818:
814:
810:
806:
800:
797:
792:
788:
784:
780:
774:
771:
768:
764:
760:
755:
752:
747:
743:
738:
732:
727:
723:
719:
714:
709:
705:
699:
695:
691:
687:
679:
675:
671:
667:
661:
658:
655:
651:
647:
642:
639:
634:
630:
625:
621:
616:
612:
604:
603:
602:
588:
585:
582:
578:
574:
552:
548:
539:
521:
518:
513:
509:
505:
501:
478:
475:
470:
466:
462:
458:
433:
429:
425:
421:
412:
407:
403:
389:
386:
381:
376:
372:
348:
341:
337:
334:
331:
325:
321:
317:
312:
308:
300:
299:
298:
296:
295:root of unity
278:
274:
253:
250:
247:
227:
207:
182:
179:
174:
170:
164:
160:
154:
151:
148:
143:
140:
137:
133:
129:
124:
120:
112:
111:
110:
104:
102:
100:
95:
93:
89:
87:
84:
80:
76:
72:
67:
65:
61:
57:
53:
49:
45:
41:
37:
34:
30:
26:
22:
2857:
2854:
2845:
2834:
2831:
2820:
2817:
2810:
2807:
2800:
2797:
2790:
2787:
2780:
2777:
2760:
2756:
2700:
2589:
2545:
2541:
2539:
2488:
2378:
2274:
1726:
1497:
1493:
1489:
1485:
1481:
1477:
1473:
1403:
1211:
1098:
1069:
1064:
1060:
1058:
1053:
1049:
1041:
972:
408:
404:
363:
199:
108:
98:
96:
82:
78:
75:power-of-two
68:
63:
59:
55:
20:
18:
2772:R. Yavne, "
2381:butterflies
2322:range from
1480:, the size-
1293:is simply:
1153:), and let
52:recursively
44:H. Hollmann
2847:Connexions
2767:References
2302:if we let
540:4. Here,
364:and thus:
40:P. Duhamel
2731:−
2725:
2676:−
2522:±
2499:±
2457:±
2361:−
2225:ω
2221:−
2197:ω
2075:ω
2071:−
2047:ω
2035:−
1928:ω
1900:ω
1891:−
1798:ω
1770:ω
1698:ω
1654:ω
1621:ω
1614:−
1583:ω
1541:ω
1509:ω
1415:≥
1359:ω
1331:ω
1251:−
1234:…
1138:−
1121:…
1006:ω
982:ω
929:ω
894:−
861:∑
843:ω
807:ω
772:−
739:∑
724:ω
688:ω
659:−
626:∑
586:−
373:ω
335:π
326:−
309:ω
275:ω
251:−
171:ω
152:−
134:∑
2868:Category
2251:′
2101:′
1954:′
1824:′
1385:′
1214:/4 (for
1197:′
1101:/2 (for
1042:portions
413:indices
92:computer
33:R. Yavne
1063:/2 and
1046:radix-2
2776:," in
2588:, and
2489:et al.
1496:/2 to
1476:/4 to
1048:(size
538:modulo
200:where
77:sizes
35:(1968)
23:is a
2514:and
1532:and
1449:<
1180:and
493:and
411:even
266:and
85:=64
71:real
66:/4.
42:and
19:The
2844:,"
2830:,"
2716:log
2342:to
1044:of
240:to
2870::
2858:34
2835:55
2821:19
2811:32
2791:20
2781:33
2698:.
402:.
297::
2801:6
2761:N
2757:N
2743:8
2740:+
2737:N
2734:6
2728:N
2720:2
2712:N
2709:4
2684:1
2680:x
2671:0
2667:x
2663:=
2658:1
2654:X
2631:1
2627:x
2623:+
2618:0
2614:x
2610:=
2605:0
2601:X
2590:N
2574:0
2570:x
2566:=
2561:0
2557:X
2546:N
2542:N
2525:i
2502:1
2473:2
2467:/
2463:)
2460:i
2454:1
2451:(
2431:8
2427:/
2423:N
2420:=
2417:k
2397:0
2394:=
2391:k
2364:1
2358:4
2354:/
2350:N
2330:0
2310:k
2288:k
2284:X
2260:,
2256:)
2247:k
2243:Z
2237:k
2234:3
2229:N
2216:k
2212:Z
2206:k
2201:N
2192:(
2188:i
2185:+
2180:4
2176:/
2172:N
2169:+
2166:k
2162:U
2158:=
2153:4
2149:/
2145:N
2142:3
2139:+
2136:k
2132:X
2110:,
2106:)
2097:k
2093:Z
2087:k
2084:3
2079:N
2066:k
2062:Z
2056:k
2051:N
2042:(
2038:i
2030:4
2026:/
2022:N
2019:+
2016:k
2012:U
2008:=
2003:4
1999:/
1995:N
1992:+
1989:k
1985:X
1963:,
1959:)
1950:k
1946:Z
1940:k
1937:3
1932:N
1924:+
1919:k
1915:Z
1909:k
1904:N
1895:(
1886:k
1882:U
1878:=
1873:2
1869:/
1865:N
1862:+
1859:k
1855:X
1833:,
1829:)
1820:k
1816:Z
1810:k
1807:3
1802:N
1794:+
1789:k
1785:Z
1779:k
1774:N
1765:(
1761:+
1756:k
1752:U
1748:=
1743:k
1739:X
1710:k
1707:3
1702:N
1694:i
1691:=
1686:)
1683:4
1679:/
1675:N
1672:+
1669:k
1666:(
1663:3
1658:N
1630:k
1625:N
1617:i
1611:=
1606:4
1602:/
1598:N
1595:+
1592:k
1587:N
1553:k
1550:3
1545:N
1518:k
1513:N
1498:k
1494:N
1490:N
1486:N
1482:N
1478:k
1474:N
1460:4
1456:/
1452:N
1446:k
1426:4
1422:/
1418:N
1412:k
1389:.
1381:k
1377:Z
1371:k
1368:3
1363:N
1355:+
1350:k
1346:Z
1340:k
1335:N
1327:+
1322:k
1318:U
1314:=
1309:k
1305:X
1279:k
1275:X
1254:1
1248:4
1244:/
1240:N
1237:,
1231:,
1228:0
1225:=
1222:k
1212:N
1193:k
1189:Z
1166:k
1162:Z
1141:1
1135:2
1131:/
1127:N
1124:,
1118:,
1115:0
1112:=
1109:k
1099:N
1083:k
1079:U
1065:N
1061:N
1054:N
1050:N
1026:k
1023:n
1018:m
1014:/
1010:N
1002:=
997:k
994:n
991:m
986:N
956:k
951:4
947:n
941:4
937:/
933:N
923:3
920:+
915:4
911:n
907:4
903:x
897:1
891:4
887:/
883:N
878:0
875:=
870:4
866:n
855:k
852:3
847:N
839:+
834:k
829:4
825:n
819:4
815:/
811:N
801:1
798:+
793:4
789:n
785:4
781:x
775:1
769:4
765:/
761:N
756:0
753:=
748:4
744:n
733:k
728:N
720:+
715:k
710:2
706:n
700:2
696:/
692:N
680:2
676:n
672:2
668:x
662:1
656:2
652:/
648:N
643:0
640:=
635:2
631:n
622:=
617:k
613:X
589:1
583:m
579:/
575:N
553:m
549:n
522:3
519:+
514:4
510:n
506:4
502:x
479:1
476:+
471:4
467:n
463:4
459:x
434:2
430:n
426:2
422:x
390:1
387:=
382:N
377:N
349:,
342:N
338:i
332:2
322:e
318:=
313:N
279:N
254:1
248:N
228:0
208:k
183:k
180:n
175:N
165:n
161:x
155:1
149:N
144:0
141:=
138:n
130:=
125:k
121:X
99:N
83:N
79:N
64:N
60:N
56:N
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.