Patents on mp3 and RSA didn’t prevent them from being used everywhere. I guess a patent on FFT (which, by the way, was considered at the time, according to Wikipedia) wouldn’t have stopped its adoption either.
Also, IMO, a formula, which tells you what to compute, is essentially different from an algorithm, which tells you how. FFT would be patentable because it is non-obvious, even when given the formula for doing a Fourier transform.
It still might be non-patentable on other grounds, such as the fact that Gauss apparently described it in 1805 (http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf), two years before Fourier published his work on what now is known as Fourier series.
Also, IMO, a formula, which tells you what to compute, is essentially different from an algorithm, which tells you how. FFT would be patentable because it is non-obvious, even when given the formula for doing a Fourier transform.
It still might be non-patentable on other grounds, such as the fact that Gauss apparently described it in 1805 (http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf), two years before Fourier published his work on what now is known as Fourier series.