 As Tukey did not work at IBM, the patentability of the idea was doubted and the algorithm went into the public domain, which, through the computing revolution of the next decade, made FFT one of the indispensable algorithms in digital signal processing.Let "x"0, …, "x""N"−1 be complex numbers.The DFT is defined by the formula

where formula_8 is a primitive th root of 1.