3 ms·

Looking at the page source they seem to be using the library from Project Nayuki[0]. I'm actually quite amazed at how few lines of code are required for an FFT

Looking at the page source they seem to be using the library from Project Nayuki[0]. I'm actually quite amazed at how few lines of code are required for an FFT implementation[1]. Anyway, I might give a simple draw-on-canvas website a go, give me a few hours. [0] https://www.nayuki.io/page/free-small-fft-in-multiple-languages https://www.nayuki.io/page/free-small-fft-in-multiple-langua... [1] https://www.nayuki.io/res/free-small-fft-in-multiple-languages/fft.js https://www.nayuki.io/res/free-small-fft-in-multiple-languag...

tzs 6y ago
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.
content_sesh 6y ago
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.
- vanderZwan 6y ago
  > 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. Oh yeah, I definitely didn't mean to imply that it was easy code. It has that elegance that you really only see in the kind of concise code that can only be written by people who really grok the underlying system (both programming and FFT).
  - content_sesh 6y ago
    For sure. As Brooks might say, code like that is high in "essential complexity". There's almost no boilerplate - there's a nearly 1:1 ratio of lines of code to important idea.
nayuki 6y ago
This canvas activity also uses my FFT library. https://www.nayuki.io/page/gaussian-blur-demo https://www.nayuki.io/page/gaussian-blur-demo

tzs 6y ago

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.

content_sesh 6y ago

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.

vanderZwan 6y ago
> 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. Oh yeah, I definitely didn't mean to imply that it was easy code. It has that elegance that you really only see in the kind of concise code that can only be written by people who really grok the underlying system (both programming and FFT).
- content_sesh 6y ago
  For sure. As Brooks might say, code like that is high in "essential complexity". There's almost no boilerplate - there's a nearly 1:1 ratio of lines of code to important idea.

nayuki 6y ago

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