Tests not detecting an obvious issue

[Faboor]

While implementing fast_fourier_transform_parfor I have noticed that when I remove the variable w calculated inside the loop completely, my tests still pass. I have tried this also in the basic sequential implementation (see diff below) and found that the test still pass even without the w. I suspect there is a problem somewhere, presumably the tests being insufficient to determine actual correctness of the results.

diff --git a/src/fast_fourier_transform.cpp b/src/fast_fourier_transform.cpp
index 98b783b..cb16d1b 100644
--- a/src/fast_fourier_transform.cpp
+++ b/src/fast_fourier_transform.cpp
@@ -42,14 +42,12 @@ class fast_fourier_transform
 			recurse(m,wn*wn,pIn,2*sIn,pOut,sOut);
 			recurse(m,wn*wn,pIn+sIn,2*sIn,pOut+sOut*m,sOut);
 
-			complex_t w=complex_t(1, 0);
 
 			for (size_t j=0;j<m;j++){
-			  complex_t t1 = w*pOut[m+j];
+			  complex_t t1 = pOut[m+j];
 			  complex_t t2 = pOut[j]-t1;
 			  pOut[j] = pOut[j]+t1;                 /*  pOut[j] = pOut[j] + w^i pOut[m+j] */
 			  pOut[j+m] = t2;                          /*  pOut[j] = pOut[j] - w^i pOut[m+j] */
-			  w = w*wn;
 			}
 		}
 	}

Example running the test on modified fast_fourier_tranform.cpp:

$ grep -B1 -A4 'complex_t t1' src/fast_fourier_transform.cpp; \
> rm -f src/fast_fourier_transform.o; \
> make bin/test_fourier_transform 1>/dev/null; \
> bin/test_fourier_transform hpce.fast_fourier_transform
                        for (size_t j=0;j<m;j++){
                          complex_t t1 = pOut[m+j];
                          complex_t t2 = pOut[j]-t1;
                          pOut[j] = pOut[j]+t1;                 /*  pOut[j] = pOut[j] + w^i pOut[m+j] */
                          pOut[j+m] = t2;                          /*  pOut[j] = pOut[j] - w^i pOut[m+j] */
                        }
hpce.fast_fourier_transform : Passed 73725120 out of 73725120 tests.

[jjd06]

Yes, that's true: because the same implementation (recurse) is being used for both forward and backward transforms, the incorrectness of the forward transform is being cancelled out by the (mirroring) incorrectness of the backward one. Good spot.

The testing only checks for correct DC behaviour and reversability. It should probably be using a reference implementation to compare outputs against, but alas that was not done. I'm not tempted to change the tests now that the coursework has been released, but try to ensure that your implementations are correct; don't just remove w = w*wn because it makes things faster!