0
\$\begingroup\$

Related: Autocorrelation of a vector series

The given C# source code computes the autocorrelation of a vector series using a Fast Fourier Transform.

Can you review this code for correctness?

using System;
using System.Collections.Generic;
using System.Numerics;

public class TimeSeriesAnalysisForVectors
{
    private static Complex[] FFT(Complex[] x)
    {
        int n = x.Length;
        if (n == 1)
            return new Complex[] { x[0] };

        Complex[] even = new Complex[n / 2];
        Complex[] odd = new Complex[n / 2];
        for (int i = 0; i < n / 2; i++)
        {
            even[i] = x[2 * i];
            odd[i] = x[2 * i + 1];
        }

        Complex[] evenTransformed = FFT(even);
        Complex[] oddTransformed = FFT(odd);

        Complex[] result = new Complex[n];
        for (int i = 0; i < n / 2; i++)
        {
            double angle = -2 * Math.PI * i / n;
            Complex twiddle = Complex.FromPolarCoordinates(1, angle);
            result[i] = evenTransformed[i] + twiddle * oddTransformed[i];
            result[i + n / 2] = evenTransformed[i] - twiddle * oddTransformed[i];
        }

        return result;
    }

    private static Complex[] FourierTransform(List<Vec3> vectors)
    {
        int n = vectors.Count;
        Complex[] fftInput = new Complex[n];

        for (int i = 0; i < n; i++)
        {
            fftInput[i] = new Complex(vectors[i].X, 0);
        }

        // Compute FFT
        return FFT(fftInput);
    }

    private static List<double> ComputeAutoCorrelation(Complex[] fftInput)
    {
        int n = fftInput.Length;
        List<double> autoCorrelations = new List<double>();

        // Compute auto-correlation using the FFT result
        for (int i = 0; i < n; i++)
        {
            autoCorrelations.Add((fftInput[i] * Complex.Conjugate(fftInput[i])).Real / n);
        }

        return autoCorrelations;
    }

    public static List<double> GetAutoCorrelationPoints(List<Vec3> vectors, int maxLag)
    {
        var fftInput = FourierTransform(vectors);
        var autoCorrelations = ComputeAutoCorrelation(fftInput);

        // Extract autocorrelation values up to maxLag
        var result = new List<double>();
        for (int lag = 0; lag <= maxLag && lag < autoCorrelations.Count; lag++)
        {
            result.Add(autoCorrelations[lag]);
        }

        return result;
    }
}
\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.