4
$\begingroup$

I'm working on a simple FFT implementation and currently running some unit tests. Long floating point numbers in C and assembly become very hard to keep track of, and this whole thing is error prone. I was able to some up (purely experimentally) with a few 4-tap and 8-tap arrays whose DFT is all whole numbers. I'm only testing DFT arrays of length $2^N$, and I could, of course, repeat my shorter signals several times until I achieve desired length, but this would give me a whole bunch of zeros, and that's not a good thing to test for. In summary, I need to come up with signals that satisfy the following:

  1. Signals are of length $2^N$
  2. Coefficients of both the signal and its DFT must be whole numbers
  3. Signals are real
  4. Signals must not consist mainly of zeros

Could there be a general way of coming up with such things?

Update To explain number 4 above, let me demonstrate what I mean with an example. I don't want a situation in that was produced by repeating something that has a known integer DFT several times.DFT of [1 5 -1 0] is [5 2-5i -5 2+5i]. If you simply repeat [1 5 -1 0] four times to get

[1 5 -1 0 1 5 -1 0 1 5 -1 0 1 5 -1 0],

its DFT would be

[20 0 0 0 8-20i 0 0 0 -20 0 0 0 8+20i 0 0 0].

This shows that repeating something many times does not add any new non-zero integer numbers to the DFT. This procedure simply inserts zeros between existing DFT coefficients (and scales them depending on definition of the transform). This isn't of much help. So zeros are welcome, but not the zeros achieved this way.

$\endgroup$
  • $\begingroup$ I updated the question. I agree that it lacked some clarity. $\endgroup$ – Phonon Feb 14 '12 at 16:40
  • $\begingroup$ I hope that your procedure does not "simply insert zeros between existing DFT coefficients" but actually calculates them, and so "zeroes achieved this way" do test something about your program, though of course by no means do they test everything. Do not sneer at those zeroes; all my life I have relied upon the kindness of strangers and the result of two floating-point calculations canceling out to give me exactly $0$. Old-timers will remember that writing loops beginning for i = 0.0 step 0.1 until 20.0 was generally frowned upon as resulting in a nonterminating loop.... $\endgroup$ – Dilip Sarwate Feb 14 '12 at 16:55
  • $\begingroup$ @DilipSarwate Agreed. = ) I was thinking more in terms of testing IFFT functions, but I guess I should just do all the general cases, not just these special ones to keep everything neat. $\endgroup$ – Phonon Feb 14 '12 at 17:37
  • 5
    $\begingroup$ Complex numbers $a+jb$ where $a$ and $b$ are integers are called Gaussian integers. So your question in effect asks for constructions of arrays of Gaussian integers whose DFTs are also arrays of Gaussian integers. Perhaps asking this question over in math.SE might get some more answers. There are lots of things known about Gaussian integers, but a lot unknown too, e.g. how many Gaussian integers are there inside a circle of radius $r$ centered at the origin? $\endgroup$ – Dilip Sarwate Feb 14 '12 at 20:27
  • $\begingroup$ @DilipSarwate Thanks, this is very interesting! $\endgroup$ – Phonon Feb 14 '12 at 20:49
5
$\begingroup$

The DFT matrix has $e^\frac{-2 \pi j}{2^N}$ as coefficients. For $N >= 3$, these coefficients might have irrational numbers as real/imaginary parts (eg $\frac{\sqrt 2}{2}$ for $N=3$); so all these irrational terms will have to cancel out exactly in the DFT computation. There are ways of achieving that (repeating is one of them) ; but this keeps you away from the general case that your code has to test! For example, this will create symmetries in your data that might make an error in the bit reversal, or in the higher orders (3rd level or above) of butterflies undetected!

Another thing to take into account is that due to the pure floating point implementation, even if the expected result should be a whole number, your FFT code, especially on large sizes, might find a result like 0.99999999 (Heck, some whole numbers are not even representable as floats!) ; and this wouldn't be incorrect. Plausible on doubles, very likely of floats.

So you'd rather use very generic data (ie: that will yield some irrational numbers) ; and some unit tests that guarantees you that your results are within some tolerance of values computed by a reference implementation such as FFTW. For example in gtest there is EXPECT_FLOAT_EQ or EXPECT_NEAR to check for float equality (up to representation errors) and for float equality given a tolerance.

$\endgroup$
  • $\begingroup$ Makes sense. I guess I shouldn't avoid the tedious cases and just test everything. $\endgroup$ – Phonon Feb 14 '12 at 17:36
  • $\begingroup$ I'd still like to know how to generate them $\endgroup$ – endolith Aug 31 '13 at 20:57
0
$\begingroup$

What I typically do is to port a version of the UUT into MPFR so that I can assume without too much analysis that I am not generating test cases whose results are degraded by roundoff. This provides the patterns at the input and output to test the UUT. Then throw some randomly generated distribution of inputs into it.

The combinatorics of integer-in / integer-out have been studied for millenia, most famously Diophantus. I think it is pretty easy to prove that a DFT has no all-integer solutions except for the trivial cases you point out.

BUT

This really seems to be a test situation of an algorithm where the roundoff accumulation must be studied and given values to. Then that roundoff analysis will provide the test case with the pass/fail limits that must be used.

Also, to inform your approach ... are you testing the validity of your algorithm, the validity of the machine or the validity of the compiler? The weighting of the relative importance of each of these needs should tell you how long to spend on the problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.