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.
Sorry, a formula and an algorithm are not at all different.
A mathematical formula is just a symbolic expression of an abstract concept, with the procedure (algorithm) how to use it being implicit (= obvious to the person skilled in the art).
A computer algorithm can be trivially converted into purely mathematical/logic representation ("formulas" if you want), e.g. using things like lambda calculus. And vice-versa - an abstract mathematical problem formulation can be converted into an algorithm (assuming the solution is known).
If you start patenting algorithms, you are patenting math.
It is true that an algorithm can be converted to a formula, and a formula to an algorithm, but it is unlikely a given useful algorithm could be generated mechanically from a (human-written, useful) formula.
For example, you could write a formula to express the property of order in lists, and maybe with some mechanical procedure (falling under "obvious to the person skilled in the art") you could then generate an algorithm that sorted lists. However, what's the time/space complexity of that algorithm? What are the practical runtime characteristics? For industry applications the practical runtime characteristics matter as much as anything else. That you technically could compute something doesn't matter at all, if that computation might not finish until relevant celestial bodies have phase changes.
I'm not saying Quicksort should be patentable, but I do think it's at least a step and a half removed from pure math.
But you could also argue that algorithms can be expressed through Language by trivially converting them into a purely semantic/logic representation. Is then anything that can be expressed through Language not patentable because it is trivially reduced to words?
With an algorithm implementation, you require integration with a runtime, quick storage, data, a data format. You also maybe need some tests and an SLA. There must be other components I missed.
If you take a different example, say, improvements to JPEG, it's a lot harder for camera manufacturers to ignore patents. You're at the mercy of the patent holders, whose terms apparently haven't been reasonable enough for anybody to improve the compression in digital photos beyond what we had decades ago.
You have to be careful to avoid cherry picking results. As a counter-example in the same area, arithmetic coding was arguably shut down as commercial technique by IBM patents.
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.