Nota — a free DAW for macOS, Windows and Linux. No subscription, no account — just open it and make music.
C# audioaudio-unitavaloniacpp20cross-platformdawdigital-audio-workstationdspjucelinux-audiomcp-servermidimusicmusic-productionpiano-rollplugin-hostsequencersynthesizervstvst3
// SPDX-License-Identifier: AGPL-3.0-only
// Copyright (c) 2026 Egor Khindikaynen (Nota). See LICENSES/ for license terms.
using System;
namespace Nota.App;
/// <summary>In-place iterative radix-2 Cooley–Tukey FFT (length a power of two).</summary>
internal static class Fft
{
public static void Transform(double[] re, double[] im)
{
int n = re.Length;
for (int i = 1, j = 0; i < n; i++)
{
int bit = n >> 1;
for (; (j & bit) != 0; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j)
{
(re[i], re[j]) = (re[j], re[i]);
(im[i], im[j]) = (im[j], im[i]);
}
}
for (int len = 2; len <= n; len <<= 1)
{
double ang = -2 * Math.PI / len, wr = Math.Cos(ang), wi = Math.Sin(ang);
for (int i = 0; i < n; i += len)
{
double cr = 1, ci = 0;
for (int k = 0; k < len / 2; k++)
{
int a = i + k, b = i + k + len / 2;
double tr = re[b] * cr - im[b] * ci, ti = re[b] * ci + im[b] * cr;
re[b] = re[a] - tr;
im[b] = im[a] - ti;
re[a] += tr;
im[a] += ti;
double ncr = cr * wr - ci * wi;
ci = cr * wi + ci * wr;
cr = ncr;
}
}
}
}
}