递归FFT java算法返回null？

Question

我目前正在尝试在java中实现FFT算法，但遇到了一些麻烦！我已经很好地测试了算法的所有其他部分，它们似乎运行良好。

我遇到的问题是，在基本情况下，它返回一个复数数组，在基本情况下填充了 A[0] 。执行基本情况后，执行 for 循环，发现 y0[0] 和 y1[0] 为 null，尽管将它们分配给基本情况，但对此感到非常困惑。这显示在 System.out.println 行中

有人能告诉我我的方法的错误吗？

    //This method implements the recursive FFT algorithm, it assumes the input length
//N is some power of two
private static Complex[] FFT(Complex[] A, int N) { 
    double real, imag;
    Complex A0[] = new Complex[((int) Math.ceil(N/2))]; 
    Complex A1[] = new Complex[((int) Math.ceil(N/2))];
    Complex[] omega = new Complex[N];
    Complex[] y = new Complex[N];
    Complex[] y0 = new Complex[((int) Math.ceil(N/2))];
    Complex[] y1 = new Complex[((int) Math.ceil(N/2))]; 

    //base case
    if (N == 1) {
        return A;
    }
    else {
        real = Math.cos((2*Math.PI)/N); if (real < 1E-10 && real > 0) real = 0;
        imag = Math.sin((2*Math.PI)/N); if (imag < 1E-10 && imag > 0) imag = 0;
        omega[N-1] = new Complex(real, imag);
        omega[0] = new Complex(1, 0);
        A0 = splitInput(A, 1);
        A1 = splitInput(A, 0);
        //recursive calls
        y0 = FFT(A0, N/2);
        y1 = FFT(A1, N/2);
        for (int k = 0; k < ((N/2)-1); k++) {
            System.out.print("k: " + k + ", y0: " + y0[k]); System.out.println(", y1: " + y1[k]);
            y[k] = y0[k].plus(omega[k].times(y1[k]));
            y[k+(N/2)] = y0[k].minus(omega[k].times(y1[k]));
            omega[0] = omega[0].times(omega[N]);
        }
        return y;
    }
}

这是根据要求的 splitInput 方法的代码

//This method takes a double array as an argument and returns every even or odd
//element according to the second int argument being 1 or 0
private static Complex[] splitInput(Complex[] input, int even) {
    Complex[] newArray = new Complex[(input.length/2)];

    //Return all even elements of double array, including 0
    if (even == 1) {
        for (int i = 0; i < (input.length/2); i++) {
            newArray[i] = new Complex(input[i*2].re, 0.0);
        }
        return newArray;
    }
    //Return all odd elements of double array
    else {
        for (int i = 0; i < (input.length/2); i++) {
            newArray[i] = new Complex (input[(i*2) + 1].re, 0.0);
        }
    return newArray;
    }
}

编辑：我已根据您的建议更新了我的代码，但仍然从行 y[k] = y0[k ].plus(omega[k].times(y1[k])); as y0 &在基本情况之后 y1 仍然为 null :( 还有更多想法吗？这是更新后的算法

//This method implements the recursive FFT algorithm, it assumes the input length
//N is some power of two
private static Complex[] FFT(Complex[] A, int N) { 
    double real, imag;
    Complex[] omega = new Complex[N];
    Complex[] y = new Complex[N];
    Complex[] A0;
    Complex[] A1;
    Complex[] y0;
    Complex[] y1;

    //base case
    if (N == 1) {
        return A;
    }
    else {
        real = Math.cos((2*Math.PI)/N); if (real < 1E-10 && real > 0) real = 0;
        imag = Math.sin((2*Math.PI)/N); if (imag < 1E-10 && imag > 0) imag = 0;;
        omega[N-1] = new Complex(real, imag);
        omega[0] = new Complex(1, 0);
        A0 = splitInput(A, 1);
        A1 = splitInput(A, 0);
        //recursive calls
        y0 = FFT(A0, N/2);
        y1 = FFT(A1, N/2);
        for (int k = 0; k < ((N/2)-1); k++) {
            y[k] = y0[k].plus(omega[k].times(y1[k]));
            y[k+(N/2)] = y0[k].minus(omega[k].times(y1[k]));
            omega[0] = omega[0].times(omega[N-1]);
        }
        return y;
    }
}

Answer 1

一些想法：

每当我看到像 Math.ceil(N/2) 一样频繁地重复出现的内容时，我认为它证明拥有自己的命名变量是合理的。 （我知道命名变量并不总是那么容易，但我发现它对于易读性至关重要。）

Complex A0[] = new Complex[((int) Math.ceil(N/2))];
Complex A1[] = new Complex[((int) Math.ceil(N/2))];

请注意，当 N==1 时，计算结果为 new Complex[0]。我不确定这会做什么，但我想我应该在内存分配之前进行 N == 1 基本情况检查。

Complex[] y0 = new Complex[((int) Math.ceil(N/2))];
Complex[] y1 = new Complex[((int) Math.ceil(N/2))];
/* ... */
    y0 = FFT(A0, N/2);
    y1 = FFT(A1, N/2);

我相信您可以跳过这些数组的 new Complex[...] 分配，因为您实际上从未在其中存储任何内容。

Complex[] omega = new Complex[N];
/* ... */
        omega[0] = omega[0].times(omega[N]);

我很惊讶这还没有爆发——omega[N]应该引发IndexOutOfBounds异常。

Answer 2

跳出来的问题：

1. (int) Math.ceil(N/2) 你仍然在做 int 除法，所以 Math.ceil()< /code> 无效，并且您的分割数组对于奇数 n 可能不正确，
2. 您只填充 omega[0] 和 omega[N-1]< /code>，我希望当您尝试访问 omega[1] 时，NullPointerException 会在 N >= 6 时发生。
3. omega[N]，正如 sarnold 也提到的，
4. 您分配 A0 和 A1，然后将 splitInput 的结果分配给它们代码>