multiple bugs in the fourier transform function; aka FFT; involves complex numbers
Submitted by John Denker
Link to original bug (#696418)
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