FFT Class Clarification


#1

I think the FFT class needs some clarifaction

 /** Initialises an object for performing either a forward or inverse FFT with the given size.
    The the number of points the FFT will operate on will be 2 ^ order.
*/
FFT (int order, bool isInverse);

When i read the code right it should be

The number of complex-pairs the FFT will operate on will be 2 ^ order.

Also

 /** Returns the number of data points that this FFT was created to work with. */
    int getSize() const noexcept            { return size; }

should be

the number of complex pairs that this FFT was created to work with

am I right?

Also it would very handy to have a static function in the FFT class to find the right order for given number of real samples, i think something like this does the job

int findMinimumOrder(int realSize) { return highestBitInInt(realSize-1)+1; }

highestBitInInt borrowed from BigIngeger, where the lowest bit returns 0, the second lowest 1


#2

A point generally refers to a location on a plane (possibly cartesian), so it would have x,y components. Complex numbers are not a pair per se, they are a single entity and they consist of a real and imaginary component that on a complex plane map to x,y coordinates.

So while point may not be the most natural name, it isn’t wrong.

N=2^order

therefore

order=log2(N)

for any natural N, this works:

order = std::log2(juce::nextPowerOfTwo(N))

#3

well of course, but its not precise, especially if you want to know whats going on

order = std::log2(juce::nextPowerOfTwo(N))

imho it feels not good to use floating point arethmetic, for a pure integer task

thats why i prefer something like return highestBitInInt(realSize-1)+1


#4

Floating point math is exact for powers of two and integers below 2^53, so you shouldn’t worry. It is also the most idiomatic way to calculate this result, using the exact formula, thus I would argue it is the best solution. This ‘task’ has no performance implications, anyway?

But…
There’s some merit to other approaches, if you’re worried about performance etc. you can count the leading number of zeros and derive the log2 from that value. It’s the inverse to your approach, the difference being that there’s a CPU instruction directly performing this calculation and you can skip the BigInteger.


#5

FYI I’ve made that highest-bit function public now.