multiple bugs in the fourier transform function; aka FFT; involves complex numbers

Submitted by John Denker

Description

Created attachment 239575 demonstrate multiple related bugs in the fourier(...) function

In the attached example, one sheet contains live formulas, while the other sheet shows the results I obtain chez moi, pasted by value. Experience suggests this may help clarify the discussion, insofar as it makes it 100% clear what results I am obtaining, even if different versions behave differently. I am using gnumeric version 1.10.17. Red background indicates some of the the /primary/ errors; errors that are obvious consequences of earlier errors are not highlighted.

In cells G7:H10 we see that the inverse FT of {1;0;0;0} is {.25;.25;.25;.25} This is as expected.

In cells D7:E10 we see that the forward FT of {1;1;1;1} is {1;0;0;0} which is almost as expected. The slightly weird thing is that these numbers are left-justified in the cells. This suggests that the spreadsheet thinks these are complex numbers. This "should" be harmless, however ....

In cells E7:F10 we see that the inverse FT of the results of the previous computation gets completely the wrong answer. Even though the numbers in cells E7:E10 look numerically correct, and and even though they have exactly zero imaginary part, they are somehow damaged. They are different from the ordinary numbers {1;0;0;0} and the inverse FT cannot cope with them.

There is no error message and no warning message; just grossly incorrect numerical results.

In cells G16:19 we find that adding zero to these numbers -- even using complex arithmetic -- undoes the damage. The new numbers display right- justified in the usual way, and the FT can cope with them. The fact that G16:G19 displays differently from E16:19 suggests there is something weird in the core of the complex number system.

There's more: In cells D25:E28 we see that the FT can handle an input with one complex number; so far so good. However, in cells D34:E37 we see that it cannot handle an input with two complex numbers.

It should go without saying that a FT that cannot handle arbitrary complex numbers on the input is pretty much useless.

Suggestion: After the FT is fixed, it would be good to test it systematically. One fairly sensitive test is to perform a transform/inverse-transform pair and check that we get back what we started with. On the input, use random data, or perhaps quenched pseudo-random data. That means complex data, not just real data. A useful qualitative check is to make sure that Parseval's theorem is upheld; see row 13 in the attachment. It would be good to include such tests in the release-validation/regression-testing suite.

Attachment 239575, "demonstrate multiple related bugs in the fourier(...) function":
fourier-bug.gnumeric

Version: 1.10.x