Welcome to the legendary

The Very Fast Fourier Transform

"Any sufficiently advanced technology is, of course, indistinguishable from magic".

Arthur C Clark.

The graph below says it all. The solid black line is the O(n2) matrix algorithm known to Gauss in 1805. The dashed line underneath it is the famous Cooley-Tukey algorithm of 1965 with complexity O(n.log(n)). This algorithm is widely credited as "... the single breakthrough that made modern signal processing a practical proposition ...". All the other black lines are the results of various other algorithms and optimisations developed since 1965.

The red line is the VFFT of 2003 with complexity O(n). What made the big difference for the Cooley-Tukey algorithm was the change in slope on the graph. All the refinements didn't change the slope any more, they just lowered the curve a bit on the vertical axis. But, like the Cooley-Tukey, the VFFT again changes the slope of the line.

Remember the paradigm shift that Cooley-Tukey made possible. You are now looking at the next one.

Go imagine.

Fast Firmware Technology Ltd

British technology (still) leading the world.