V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Fast Fourier Transform

Bit-reverse the input and run logarithmic layers of butterfly operations for a fast discrete Fourier transform.

Core idea

Split a polynomial into even and odd coefficients, evaluate both at squared roots, and combine them with roots-of-unity rotations. Iterative FFT exposes the same recursion as butterfly layers.

Read the visualization

Bit reversal places recursive leaves in iterative order. Each network column doubles block size, and every butterfly transforms one pair with its twiddle factor.

12340000×1×1×1×1×1×ω²×1×ω²×1×ω×ω²×ω³

Load the coefficient sequence and the target transform length.

1function fft(a: Complex[]): Complex[] {
2 const n = a.length; // n init 2 init
3 const A = new Array(n);
4 for (let i = 0; i < n; i++) A[i] = a[bitRev(i)]; // bit-reversal permutation
5 for (let L = 2; L <= n; L *= 2) {
6 const half = L / 2;
7 const w0 = expI(-2 * Math.PI / L); // current layer twiddle digit root ω_L
8 for (let st = 0; st < n; st += L) {
9 let w = ONE;
10 for (let k = 0; k < half; k++) {
11 const u = A[st + k];
12 const v = mul(A[st + k + half], w);
13 A[st + k] = add(u, v); // butterfly: sum
14 A[st + k + half] = sub(u, v); // butterfly: difference
15 w = mul(w, w0);
16 }
17 }
18 }
19 return A; // O(n log n)
20}
input[1, 2, 3, 4, 0, 0, 0, 0]
target8 point DFT, use only O(n log n)
1 / 9

Complexity and tradeoffs

Time: O(n log n). Space: O(n). Pointwise multiplication between forward and inverse transforms yields fast polynomial convolution.

Invariant: After layer s, each completed block contains the transform of a size 2 to the power s subproblem.

Where it fits

FFT reduces polynomial and large-integer convolution to transform, pointwise multiply, and inverse transform. Numerical implementations must round and control floating-point error.