Real Fast Fourier Transform (RFFT)

complex.dart

import 'dart:math' as math;

/// Represents a complex number in the form [a] + [b]i.
class Complex {
  /// The origin of the complex plane.
  static const Complex zero = Complex(0, i: 0);

  /// The real part of this number.
  final double a;

  /// The imaginary part of this number.
  final double b;

  /// Creates a complex number from its parts.
  ///
  /// The real and imaginary parts are represented by [x] and [i], respectively.
  const Complex(double x, {required double i})
      : a = x,
        b = i;

  /// Creates a complex number from a real [value].
  const Complex.real(double value) : this(value, i: 0);

  /// Creates a complex number from an [angle] in radians.
  Complex.angle(double angle) : this(math.cos(angle), i: math.sin(angle));

  /// The absolute value of this number.
  ///
  /// The absolute value of a complex number is the distance to the origin of
  /// the point representing the complex number in the complex plane.
  double get abs => math.sqrt(a * a + b * b);

  /// The argument of this number.
  ///
  /// The argument of a complex number is the angle of the radius *Oz* with the
  /// positive real axis, where *O* is the origin and *z* is the point
  /// representing the complex number in the complex plane.
  double get arg => math.atan2(b, a);

  /// Adds this and [other] complex number.
  operator +(Complex other) {
    return Complex(a + other.a, i: b + other.b);
  }

  /// Subtracts this from [other] complex number.
  operator -(Complex other) {
    return Complex(a - other.a, i: b - other.b);
  }

  /// Multiplies this to [other] complex number.
  operator *(Complex other) {
    return Complex(a * other.a - b * other.b, i: a * other.b + b * other.a);
  }

  /// Divides this from [other] complex number.
  operator /(Complex other) {
    return Complex(
      (a * other.a + b * other.b) / (other.a * other.a + other.b * other.b),
      i: (b * other.a - a * other.b) / (other.a * other.a + other.b * other.b),
    );
  }

  @override
  String toString() => 'Complex($a, i: $b)';
}

rfft.dart

import 'complex.dart';

/// Compute the one-dimensional discrete Fourier Transform for real input.
///
/// This function computes the one-dimensional discrete Fourier Transform (DFT)
/// of a real-valued array [x] by means of an efficient algorithm called the
/// Fast Fourier Transform (FFT).
Iterable<Complex> calculateRFFT(List<double> x) sync* {
  final int size = x.length;
  for (int i = 0; i < (size ~/ 2 + 1); i++) {
    Complex sum = Complex.zero;
    for (int j = 0; j < size; j++) {
      sum += Complex.angle(-math.pi * 2 * i * j / size) * Complex.real(x[j]);
    }
    yield sum;
  }
}