AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Radix-two discrete Fourier transform

Definition

For a nonnegative integer $q$ , let $M = 2^{q}$ , set $ω = 1$ when $M = 1$ and $ω = e^{- 2 π i / M}$ when $M > 1$ , and let $a = (a_{0}, \dots, a_{M - 1}) \in C^{M}$ . The forward discrete Fourier transform (DFT) is the vector $\hat{a} \in C^{M}$ with ${\hat{a}}_{k} = \sum_{j = 0}^{M - 1} a_{j} ω^{j k}$ . The radix-two procedure returns this vector by the following exact recursion. If $M = 1$ , return $(a_{0})$ . If $M > 1$ , recursively compute the length- $M / 2$ DFTs $E$ and $O$ of $(a_{0}, a_{2}, \dots, a_{M - 2})$ and $(a_{1}, a_{3}, \dots, a_{M - 1})$ , using the primitive root $ω^{2}$ . For $0 \leq k < M / 2$ , return ${\hat{a}}_{k} = E_{k} + ω^{k} O_{k}$ and ${\hat{a}}_{k + M / 2} = E_{k} - ω^{k} O_{k}$ . The inverse transform is obtained by running the same procedure with $\overline{ω}$ and dividing every output by $M$ .

Definition references

Gu, Goel, and Ré, “Efficiently Modeling Long Sequences with Structured State Spaces,” Appendix C.2

Used by

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Gu, Goel, and Ré, Efficiently Modeling Long Sequences with Structured State Spaces, Appendix C.2 (standard reference, not scraped)