- Hello, welcome to a coding challenge.

I actually just finished this coding challenge,

and I'm coming back to re-record a little intro to it.

And what I made in this

coding challenge is a drawing machine.

Maybe let's call this a Fourier transform drawing machine.

There's a few more things we want to do with it.

There's going to be some followup videos.

But this very, very long video, if you can stand

to watch it, has, as part of it, at the end, this.

This is the end result.

I am using an algorithm called Fourier Transform

to take an arbitrary signal, in this case, a sequence of X's

and a sequence of Y's, the path of the Coding Train logo,

thank you to Tom Fevrier.

I will link to Tom Fevrier's Twitter, who provided

the path for this particular logo, to trace

the path of the logo through this sort of sequence

of rotating circles, sometimes referred to as epicycles.

Okay, so what's going on here?

So, first thing I should mention is this is

a continuation of my coding challenge Fourier Series.

And so, what I did in that particular coding challenge,

which was inspired by a Smarter Everyday video on the same

topic, was create the Fourier series for a square wave.

I don't know why I just had to write that.

But in this video, I'm going to do something different,

which is I'm going to use the Fourier transform algorithm.

And these are different concepts.

I somewhat conflated these in my previous video.

The idea of the Fourier transform.

Now, where I know this algorithm from, where I learned

about this algorithm first in like, learning about coding

and creative coding and new media and sound and video

is with the terminology FFT, and actually,

if you go into the p5 sound library, you'll see

there is a class or function called p5.FFT.

I don't remember exactly what it's called,

but something like that.

The F here stands for fast, Fast Fourier Transform.

The algorithm I'm going to implement,

by the way, is discrete Fourier transform.

Why is this FFT thing, where is it typically used?

Well, it's typically used in, it's in signal processing,

but a familiar place where you might find that

is in audio signal processing.

So let's say you have some arbitrary sound wave

that maybe looks like this, and it has a really

high-pitched, awful, screeching sound in it.

How would you filter that out?

Well, if you could take this sound wave pattern

and break it into a bunch of smaller sound waves,

a bunch of sound waves that have varying

amplitudes and frequencies, then you could take,

you could sort of remove the one that has

the high-pitched sound in it and then

add them all back together and get a new sound wave.

So the idea of a Fourier transform, I think I said this

in the Fourier Series, but it's unsmoothie-ing a smoothie.

If we could take a smoothie that's made with blueberry,

mango, and strawberries, and like, separate it out

and then put it back together without the strawberries,

this is essentially what happens in signal processing.

But in this video, what I'm going to do is

instead of the signal being an audio, it's going to be

a series of X values or a series of Y values,

and eventually, there actually a way to do that

with the X, Y values together that I will get to.

So, I am not going to go too deep into the math

in this particular video.

I'm not going to derive the Fourier Transform algorithm.

I'm not going to talk about Fast Fourier Transform.

I'm just going to use a very crude, discrete Fourier Transform

implementation just to get the thing working.

If you want to know more about the math, though,

let me reference a few really key references.

The 3blue1brown video, But what is the Fourier Transform?

will give you an infinitely better understanding

of what the Fourier Transform algorithm is

and what it does, and even how it works, way better than my

trying to ramble through that over on the whiteboard.

I would also highly recommend this GoldPlatedGoof video,

Fourier Analysis for the Rest of Us, which goes

through the details of the math in a much deeper way,

and then there's this wonderful video from Mathologer,

Epicycles, complex Fourier series and Homer Simpson's orbit,

which will give you the full story of everything

that I'm trying to do.

But hopefully, what's useful to you that's different

in my video than from these is I'm just going to sit here

and attempt to code the thing.

And I know that it's going to work, because I already did it,

and here is the result.

So enjoy.

This is a very long video.

I hope that if you watch it, you get the code,

you make your own variation of it, please share it with me.

You can go to thecodingtrain.com, to the particular

coding challenge page, and then there's instructions

on how to submit a user community variation thingy there.

Okay, goodbye, enjoy, or not, or whatever.

I am ready to start coding, finally.

Now, this is where I left off before in my Fourier Series

coding challenge, and the difference now is

what I want to do is be able to have an arbitrary signal

and then compute what all of these amplitudes

and frequencies and phases should be.

So, the way that I'm going to do that is,

so let's think about this.

This is really a bunch of Y values that I'm calculating.

So let's make an array called something like Y,

and this is going to be the signal, this is my signal.

This could be audio, it could be Y positions,

any arbitrary digital signal/array of numbers.

Then what I want to do is I want to have

like, the Fourier transform of that particular signal.

So I want to say, fourierY = fourierTransform, or maybe

like dft, discrete Fourier Transform, of the Y value.

So this is the idea.

The first thing that I need to do is compute

the discrete Fourier transform of an arbitrary signal.

Now I need some kind of signal.

So I think what I'm going to absurdly do

is hardcode the signal.

Let's actually make it the square wave,

and then we'll know if it kind of worked.

So what is the square wave?

Square wave would be something like 100, 100, 100,

- 100, -100, -100, and then like, do that a few times.

So this is going to be my arbitrary signal,

which I'm just hardcoding the square wave.

And we'll do some interesting things that we might,

maybe I'll try a Perlin noise signal

or just a sine wave signal.

We'll try different things,

random numbers, and see what that does.

So then, this actual code here can largely stay the same,

'cause in theory, the difference is now,

instead of following the specific Fourier Series

for the square wave, I just need to take

the results of my discrete Fourier transform.

So this would be a loop that's going to

go through the length of that transform, how many

different wave patterns are there that I'm adding together,

and then this ultimately, I'm going to have to figure out.

So let's comment this out right now,

and there's a little bit of an issue where I have

this x and y as like, local variables here.

But let's, I think this will be okay.

So let's refresh this, and DFT is not fine.

Okay, step one, let's write

the discrete Fourier Transform algorithm.

So, I'm going to start by making a function called dft.

It's going to have some array of values, and now,

I need to, at the end, I need to return something.

(laughs)

The idea is that I will return

the discrete Fourier transform of those values.

So, a couple things.

One is I highly recommend, if you want to pause

this video right now and read this particular article

on the Algorithm Archive

by James Schloss or the LeIOS YouTube channel.

This is a really nice article about Fourier transforms

and the discrete Fourier Transform algorithm,

and this particular algorithm for FFT.

But what I'm going to do is I'm just going to follow

exactly what's here on the Wikipedia page.

So, my signal is x sub n, lowercase xn.

So what I need to do is basically,

and the transform is capital X sub k.

So I need to write a function that computes

this exact equation and returns it as an array,

and this is exactly what I'm going to do.

This is exciting.

Now, one thing I should mention is that

in order to work with Fourier transforms,

I need to understand something called a complex number.

Now, if I recall correctly, the last time a complex number

came up on this YouTube channel was probably in my

Mandelbrot set coding challenge, where I visualized

the famous Mandelbrot fractal, and I referenced something

called an imaginary number, and I was way too informal

and loosey goosey and jokey

about how I talked about imaginary numbers

being this pretend thing that doesn't exist,

which is absolutely incorrect.

The reason why the term imaginary is used

is because there is no real number solution

to the square root of negative one, but the square root

of negative one is referred to in mathematics as i.

I is a complex number.

A complex number is a number with both a real, a,

plus an imaginary component.

So it's two real values, a real value

and another real value kind of multiplied by i,

the square root of negative one.

So, this is the idea of a complex number, and by the way,

another way for me to refer to a complex number

is by its position on the complex plane.

So if this were the real axis,

and this were the imaginary axis, this would be a,

and this would be b, and this is a vector representation,

whoa, of this particular complex number.

So, why do I bring this up?

The reason why I bring this up is that the Fourier Transform

algorithm, even if I start with an array of real numbers,

single numbers, I'm going to apply the Fourier Transform

and get out a complex number.

What I'm going to return from that function

is both a's and b's, otherwise known as the real component,

which is often written in code as re,

and the imaginary component, which is often written as im.

So this is one bit that I really need to understand

before working with this formula.

So now is this moment, this moment that happens to you

in life, where you see one of these formulas

on a Wikipedia page or in a math textbook,

and you're a creative coder making some

kind of visualization thing, and you just want to stop.

But together, you and me, we're not going to stop.

We're going to figure out how to translate all this

notation and symbols and stuff into JavaScript code.

Now, again, it'll be super interesting to go down the rabbit

hole of deriving all these formulas and the background

for how Fourier transform works, but I'm not going to do that.

If you look in the video description,

there are several excellent videos and resources

linked to that will give you that background.

But I do want to mention one thing, which is quite important,

which is that this particular formula in the top here

for the discrete Fourier transform uses this symbol e,

Euler's number, or the base of natural law.

This is a very famous number in mathematics, much like pi,

but there's also a very well known formula

called Euler's formula, which looks like this:

e to the i, which, complex number i, x, equals

cosine of x plus i times sine of x.