0
\$\begingroup\$

I want to show you an iterative algorithm to convert a signal to a Fourier series. When I ran unit tests I gaven following results:

  • one iteration: 1 sec, passed;
  • ten iterations: 3 sec, passed.

I use Visual Studio Community 2015 environment. I'm writing this library in C# and MathNet NuGet package.

How can I optimize this algorithm, and what are your opinions about this library?

The unit tests:

[TestMethod]
    public void OneIterationTest()
    {
        double[] points = new double[628];
        FourierSeries fourier = new FourierSeries((x) => Math.Sign(Math.Sin(x)), 1);
        for (int current = 0; current < 628; current++)
        {
            points[current] = fourier.GetHarmonicWavePoint(current);
        }
    }

    [TestMethod]
    public void TenIterationTest()
    {
        double[] points = new double[628];
        FourierSeries fourier = new FourierSeries((x) => Math.Sign(Math.Sin(x)), 10);
        for (int current = 0; current < 628; current++)
        {
            points[current] = fourier.GetHarmonicWavePoint(current);
        }
    }

This is my implementation:

using MathNet.Numerics.Integration;
using System;

namespace SignalProcessingLibrary
{
    /**
     * <summary>
     * The assumption of following class is distribution signals to Fourier Series.
     * First, we calculate the coefficient a_0 by integrate function in -T/2 to T/2 interval
     * and multiply it by 2/T. Next, we apply iterative algorithm to superposition of harmonic waves.
     * At the beginning this algorithm, we calculate coefficient a_n and b_n and sum it using
     * math formula. We substitute to n index of the loop and loop is performed until reach N.
     * </summary>
     */
    public class FourierSeries
    {
        /**
         * <summary>
         * Initalizes fields by default values.
         * </summary>
         */
        public FourierSeries() : this((x) => Math.Sign(Math.Sin(x)), 10, 2 * Math.PI)
        {
        }

        /**
         * <summary>
         * Sets function and iterations. This leaves the default value of _period.
         * </summary>
         * <param name="function">Analyzed function</param>
         * <param name="iterations">Degree of approximation</param>
         */
        public FourierSeries(Func<double, double> function, double iterations) : this(function, iterations, 2 * Math.PI)
        {
        }

        /**
         * <summary>
         * Sets all fields.
         * </summary>
         * <param name="function">Analyzed function</param>
         * <param name="iterations">Degree of approximation</param>
         * <param name="period">Period of analyzed function</param>
         */
        public FourierSeries(Func<double, double> function, double iterations, double period)
        {
            Function = function;
            Iterations = iterations;
            Period = period;
        }

        /**
         * <summary>
         * Implements a_n coefficient.
         * </summary>
         * <param name="n">Number of iteration</param>
         * <returns>a_n coefficient</returns>
         */
        private double GetA(double n)
        {
            return (2 / Period) *
                GaussLegendreRule.Integrate(
                (x) => (Function.Invoke(x) * Math.Cos((2 * n * Math.PI * x) / Period)),
                -Period / 2,
                Period / 2,
                1024);
        }

        /**
         * <summary>
         * Implements b_n coefficient.
         * </summary>
         * <param name="n">Number of iteration</param>
         * <returns>b_n coefficient</returns>
         */
        private double GetB(double n)
        {
            return (2 / Period) *
                GaussLegendreRule.Integrate(
                (x) => (Function.Invoke(x) * Math.Sin((2 * n * Math.PI * x) / Period)),
                -Period / 2,
                Period / 2,
                1024);
        }

        /**
         * <summary>
         * Implements a_0 coefficient.
         * </summary>
         * <returns>a_0 coefficient</returns>
         */
        private double GetA0()
        {
            return (2 / Period) *
                GaussLegendreRule.Integrate(
                    (x) => (Function.Invoke(x)),
                    -Period / 2,
                    Period / 2,
                    1024);
        }

        /**
         * <summary>
         * This does superposition of harmonics waves.
         * </summary>
         * <param name="x">Desired point</param>
         * <returns>Superposition of harmonics waves</returns>
         */
        public double GetHarmonicWavePoint(double x)
        {
            double sum = this.GetA0() / 2;
            for (int i = 0; i < Iterations; i++)
            {
                sum = sum +
                    (GetA(i) * Math.Cos((2 * i * Math.PI * x) / Period) +
                    GetB(i) * Math.Sin((2 * i * Math.PI * x) / Period));
            }
            return sum;
        }

        public Func<double, double> Function { get; set; }
        public double Iterations { get; set; }
        public double Period { get; set; }
    }
}
\$\endgroup\$
3
\$\begingroup\$

You could calculate all values that are calculated multiple times once. I am not sure if that has any significant effect to the performance... Probably the most time consuming call is GaussLegendreRule.Integrate, however it is worth a try.

That requires that the Iterations and Period, passed to the constructor, become readonly. But that is advisable anyway.

It is also good practice to check if the values of the arguments, passed to a (public) constructor are valid for that class.

That would change the code to something like:

public class FourierSeries
{
    private readonly double _iterations;
    private readonly double _period;
    private readonly double _periodDividedByTwo;
    private readonly double _twoDividedByPeriode;
    private readonly Func<double, double> _function;

    private const double TAU = Math.PI * 2;

    public FourierSeries() : this((x) => Math.Sign(Math.Sin(x)), 10, TAU)
    {}

    public FourierSeries(Func<double, double> function, double iterations) : this(function, iterations, TAU)
    {}

    public FourierSeries(Func<double, double> function, double iterations, double period)
    {
        if (function == null) throw new ArgumentNullException("function");
        if (iterations < 1) throw new ArgumentException("iterations must be greater than 0")
        if (period < 1) throw new ArgumentException("period must be greater than 0")

        _function = function;
        _iterations = iterations;
        _period = period;
        _periodDividedByTwo = period / 2;
        _twoDividedByPeriode = 2 / period;
    }

    private double GetA(double n)
    {
        var factor = TAU * n;
        return _twoDividedByPeriode *
            GaussLegendreRule.Integrate(
            (x) => (_function.Invoke(x) * Math.Cos((factor * x) / _period)),
            - _periodDividedByTwo,
            _periodDividedByTwo,
            1024);
    }
    private double GetB(double n)
    {
        var factor = TAU * n;
        return _twoDividedByPeriode *
            GaussLegendreRule.Integrate(
            (x) => (_function.Invoke(x) * Math.Sin((factor * x) / _period)),
            -_periodDividedByTwo,
            _periodDividedByTwo,
            1024);
    }

    private double GetA0()
    {
        return _twoDividedByPeriode *
            GaussLegendreRule.Integrate(
                (x) => (_function.Invoke(x)),
                -_periodDividedByTwo,
                _periodDividedByTwo,
                1024);
    }

    public double GetHarmonicWavePoint(double x)
    {
        double sum = this.GetA0() / 2;
        for (int i = 0; i < _iterations; i++)
        {
            sum += GetA(i) * Math.Cos((2 * i * Math.PI * x) / _period) +
                   GetB(i) * Math.Sin((2 * i * Math.PI * x) / _period);
        }
        return sum;
    }
}

I suppose that GaussLegendreRule.Integrate uses an iterative integration algorithm which is quite expensive. Therefore, another optimization could be to integrate functions analytically if possible - But that depends on your use cases...

\$\endgroup\$
  • 1
    \$\begingroup\$ For C# 6.0, declarations like private readonly double _iterations; could become public double Iterations { get; } which clears up unsightly underscores but also publicly exposes the readonly property. Also in some circles, 2*PI is called Tau. See tauday.com . \$\endgroup\$ – Rick Davin Jun 17 '16 at 14:46
  • \$\begingroup\$ @RickDavin τ=2π applies to all circles. =) \$\endgroup\$ – 200_success Jul 23 '16 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.