0.2 Implementation details  (Page 3/9)

The source code has a few subtle differences that are not revealed in the pseudocode. The pseudocode in [link] requires an array of complex numbers $x_n$ for input, but the source code requires a reference to an array of complex numbers with a stride A stride of $n$ would indicate that only every $n^{th}$ term is being referred to. – this avoids copying $x_n$ into three separate arrays, viz. $x_{2n_2}$ , $x_{4n_4+1}$ and $x_{4n_4-1}$ , with every invocation of [link] . The subtle complication arises due to the cyclic shifting of the $x_{4n_4-1}$ term; the negative shifting results in pointers that reference data before the start of the array. Rather than immediately wrapping the references around to end of the array such that they always point to validdata, the recursion proceeds until the base cases are reached before any adjustment is performed. Once at the leaves of the recursion, any pointers that reference data lying before the start of the input array are incremented by $N$ elements, In this case, $N$ refers to the size of the outer most transform rather than the size of the sub-transform. so as to point to the correct data.

Tangent

The tangent FFT is divided into two functions, described with pseudocode in [link] and [link] . If the tangent FFT is computed prior to convolution in the frequency domain, theconvolution kernel can absorb the final scaling and only [link] is required. Otherwise [link] is used as a wrapper around [link] to perform the rescaling, and the result $X_k$ is in the correct basis.

[link] is similar to [link] , except that $Z_k$ and $Z_k^{\text{'}}$ are computed with [link] , and thus scaled by $1/s_{N/4,k}$ . Because $Z_k$ and $Z_k^{\text{'}}$ are respectively multiplied by the coefficients ${\omega }_N^k$ and ${\omega }_N^{-k}$ , the results are scaled into the correct basis by absorbing $s_{N/4,k}$ into the coefficients.