If you don't need it in real time and don't have a whole lot of points, you can do discrete Fourier transforms in even less code by just doing FT instead of FFT. Modern computers are fast enough that the most straightforward O(n^2) algorithm that is immediately obvious from the definition of the discrete Fourier transform given in Wikipedia will often be fast enough. E.g., something like this in C:

  typedef struct {
      double r;
      double i;
  } complex;

  void fourier(complex * x, complex * y, int np)
  {
      int n, k;

      for (k = 0; k < np; ++k)
      {
          y[k].r = y[k].i = 0;
          for (n = 0; n < np; ++n)
          {
              double c = cos(2*M_PI*k*n/np);
              double s = sin(2*M_PI*k*n/np);
              y[k].r += x[n].r * c + x[n].i * s;
              y[k].i += -x[n].r * s + x[n].i * c;
          }
      }
  }

20 years ago, on a middle of the road desktop, that was fast enough that I was able to do an almost real time guitar tuner with it.

I remember getting a very helpful tip as an undergrad Math major: once you start doing senior undergrad/early graduate level classes, expect each textbook page to take a long time to read. Upwards of an hour is not uncommon. And I found this to be very true in my own experience.

I'm always struck by this thought when I see code like this. It's not a lot of code, but if I had to actually go through and internalize it, it would certainly take me a while.

This canvas activity also uses my FFT library. https://www.nayuki.io/page/gaussian-blur-demo

I should have a 2d line chart, and I should be able to draw magnitude at each frequency. It rotates and filters. Right now, a line chart consists of 1 between two frequencies, and 0 elsewhere.

Or I should have a 2d image, and I draw dark/light. It reflects appropriately to get the other half, and multiplies the image (without rotating). Right now, this image looks like a donut.

I'm drawing the filter, you see. It applies the filter, and shows me:

* The source image FFT(what I drewFFT(image))

The point spread function / convolution kernel FFT(what I drew)

I don't want to draw an image. I want to draw a filter of an image. Right now, I have a rock-hard cutoff at two frequencies. I'd like to draw a curve, and have it Fourier filter based on that curve.