Рекурсивный алгоритм FFT Java, возвращающий ноль? - PullRequest
Новая
       27

Рекурсивный алгоритм FFT Java, возвращающий ноль?

3 голосов
/ 24 декабря 2011

В настоящее время я пытаюсь реализовать алгоритм FFT в Java, и у меня возникли некоторые проблемы с ним!Я хорошо протестировал все остальные части алгоритма, и они, кажется, работают нормально.

Проблема, которую я получаю, заключается в том, что в базовом случае он возвращает массив комплексных чисел, в базовом случае 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]));, поскольку y0 & y1 по-прежнему null после базыcase :( есть еще идеи? вот обновленный алгоритм 

//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;
    }
}

Ответы [ 2 ]

2 голосов
/ 24 декабря 2011

Несколько мыслей:

Каждый раз, когда я вижу, что что-то повторяется так часто, как 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.

1 голос
/ 24 декабря 2011

Проблемы, которые выпрыгивают:

  1. (int) Math.ceil(N/2) Вы все еще делаете int деление, поэтому Math.ceil() не имеет никакого эффекта, и ваши разделенные массивы, вероятно, неверны для нечетных n
  2. вы только когда-либо заполняете omega[0] и omega[N-1], я ожидаю NullPointerException при попытке доступа к omega[1], что произойдет, когда N >= 6.
  3. omega[N], как также упоминал sarnold
  4. Вы выделяете A0 и A1, а затем присваиваете им результаты splitInput
...