(whistling) – Hello it is time for

yet another video about the Fourier Transforming epicycles. Now you might be asking yourself, what? Why? I mean what’s wrong with you? What’s this weird,

unhealthy obsession you have with Fourier Transform? That’s a good question,

I’m not so sure actually>But I do know that there

is absolutely at least if not more one thing that I

feel is very important to demonstrate to you as part of this series, this now three part coding challenge about drawing a path with the epicycle, epicycles and the Discrete

Fourier Transform algorithm. Alright, so, what I want you to look at here from the previous

coding challenge is this, this is the coding train,

train logo being drawn by two sets of nested orbits. And the frequencies,

amplitudes, and phases of these orbits are all calculated from the Discrete Fourier Transform algorithm. The Discrete Fourier Transform

algorithm (laughs) takes, it’s over here and this is

going to look like what, are you crazy? I’m not going to watch

the rest of this video. But just stay with me or

don’t stay with me but stay with me if you feel so inclined. Don’t worry if this

looks crazy weird to you, I’m going to help you through it. And actually I did this

already and you might want to stop and go back and

watch that first video but what the Discrete Fourier

Transform does is it takes any signal and that signal, is sort of represented

here by x sub n signal. And you could think of

the signal as really just a list of numbers. One, five, ten, negative

three, seven, nine, four. Right? It’s just a list of numbers

that signal these could be the x values of a path. They could be the y values of a path. They could be the values of a sound wave. There’s so many types of

things that this could be and it takes this signal, and breaks it down into a collection of wave patterns. Each wave pattern has

a particular frequency, frequency meaning how many

cycles does it repeat, within one unit of time. So how many repeats per

second you might think? 60 hertz is 60 cycles per second. It also breaks it down into, so there’s different frequencies. But there’s also different amplitudes. And different phases. So is this wave pattern

like actually a little bit offset one way or the other? Is it much taller? Is it much shorter? It breaks it down and

I can visualize those wave patterns as rotating circles. (imitates bomb exploding) Okay. So that’s a lot! That’s a lot there. I’m sure you have questions. Maybe hopefully some of

this stuff is covered in a bit more depth in my

previous two videos, or of course in the

supplementary material about the Fourier Transform that

I’m including as links in this video subscription,

I’ve talked about those way too much but in

particular I’ll highlight the three blue, one brown video about the Fourier Transform that you might want to check out which goes

into this in more depth. Now! So here I have two sets of signals. I have x’s. Oh no this is y actually, I have y’s. And over there I have x’s. I treat them separately, I

apply the Fourier Transform to each and then I render out

these rotating circles and get this path. What I want to do now is treat, the signal, the signal is not one, a list, a vector, an array of numbers. It is an array of pairs of numbers. So we could think of the

signal as x of a path. X one, y one. X two, y two. X three, y three. And this is a really useful

way of thinking about it because so much in

computer graphics is this. Vector graphics, scalable

vector graphics, SVG’s. Those are really just defined

paths, collections of points. Now we can do all sorts

of crazy math if these points actually mean like draw

a Beziar curve between them. But I’m going to do this in

the simplest way and this is just if I had, this was my path, I would have three points. X one, y one, x two, y

two, x three, y three. And I would want to create

three orbiting circles to be able to render out this path. That’s what I want to do. So how do, what happens when the pairs of

numbers go into this formula. Well guess what? If you watch my first

video, I talked a bit about how this is actually something

known as a complex number. A complex number is a number

that has two components. A real component, a real

number being the numbers we’re kind of familiar

with more often (laughing). And quote, unquote, imaginary number. Now the fact that it’s called imaginary is unfortunate naming, it’s

somewhat misleading. But the idea is that it is

a real number paired with the number i. And the number i is the

solution to the problem, I squared equals negative one. So this is often referred to as an imaginary number because

it’s kind of like what? The square root of negative one? You can’t square something

and have negative one. But yet you can, there

is a solution to this. We can, that’s a topic

for a Khan Academy video, a math video. But if I can treat, any one of these points

as a complex number. X plus, so x one plus y one i, then

and that’s actually what I was doing before. I just was leaving out

the imaginary component, I just had a whole bunch of

x’s and a whole bunch of y’s. Always in the real component. So if I can actually

have this signal be in a list of complex numbers,

I could have this be complex numbers, this is

already a complex number. Then I just need to know how do I multiply two complex numbers together. You got that? Sort of, maybe? Let’s go write some code. I’m going to go write some code. Because there’s more to do over

here but I think we need to take a moment to breathe, absorb that a little bit and write some code. Alright so if we go back

to the code where I left it off from this previous iteration. Which I have right here, I had a particular java script file, fourier.js. Where I had my alimentation of the Discrete Fourier

Transform algorithm, dftx. X being exactly that x, sub n over there. The array of the signal,

the array of numbers. And then big X, being this, the array of complex numbers

that came out that I get the phases, frequencies, and amplitudes. Okay, so, what I want is to rewrite

this so that little x is actually an array of complex numbers. And I think one way

that I could do this is to actually put here, I’m going to write a complex number class. Now if you’re paying attention

or if you’ve used p5 before, you might be thinking to yourself oh just use p5.vector because actually, I’m just going to swing on here over to the Wikipedia page about complex numbers. Look at this, this is how you

represent a complex number. It is a vector in the

complex plane where what we think of as the y-axis

is the imaginary axis. What we think of as the

x-axis is the real axis. And right here it says,

a complex number can visually be represented as a pair of numbers, a, b, forming a

vector on a diagram called the, I never knew this, Argand diagram. Oh look at that. More stuff. So I could just use the fact that p5 has a vector class but I kind

of want to take the time to really think this through and I need to do complex number multiplication which is different than just like a

vector dot product perhaps. (laughs) So… It’s similar, but anyway,

so just let me do it myself. So I’m going to write a constructor. I don’t know that I

should call these a and b. Maybe, so one way to do it is a plus bi, I think though I might stick

with the real and imaginary. So let’s say real and imaginary but I’ll leave these a and b. So this is my complex number. So this is what I wanted to do first. So I just have a complex number and if I go back to the main sketch, instead of having two

separate x and y variables, I’m going to get rid of this. Let’s get rid of y, everywhere in this code. In a weird sort of way I’m

kind of simplifying things. Let’s get rid of y everywhere. Well I’m not going to

worry about this right now. I’ll come back to this in a little bit, let’s comment that out. And let’s, so what I had before,

again you probably want to watch the previous video as

I have this big file that just has a ton of x, y

points for the path of the drawing and I separated them into separate x and y’s and

now what I’m actually going to do is say, constant c equals a

new complex number with the real component as the x

and the imaginary component as the y and then I’m going

to push that into x. So that array is now an array of complex numbers with the x and y’s. And in fact then I want

to go here and say look, you know what? I don’t need to treat these as separate real and imaginary components. I have this idea, I’m going

to call it like the sum. As a new complex number with zero, zero. Then the idea is I could

say sum dot real plus equals sum dot imaginary plus equal. Right I’m going to treat this as a complex number object

with two components. The problem is this is no longer correct. I mean everything is right

but this no longer flies. This asterisk is multiplication. Cosign of phi is a floating point number, it’s like a complex number

with no imaginary component. X, previously, x index n

was just a single number. So I need to rethink how these, because this is now a

complex number how do I multiply a complex number

with another complex number? I have to completely rethink this. So the next step is for us to work out complex number multiplication. So typically, if I’m going to, if I’m going to want to

implement complex number multiplication in my source

code I could actually just look up the formula

for it and put in the code. But I don’t know, I got a

little extra time today. I started early today. Let’s actually do it here. So if I have two complex numbers, let’s say I have a plus bi. And I want to multiply

that and often reference, this is references the dot product. This is exactly what I

have here by the way. I want to multiply that by,

let’s call that c plus di. Then how do I do that? Well guess what? What’s this multiplication

property called, commutative? (laughing) Record scratch sound. (imitates record screeching) A commutative is the

property of multiplication or addition where I could

these in either order and I would get the same result. The distributive property is

the one that I’m looking for. Where I can say a times, well this, a is going to distribute

multiply times c plus this. So I’m going to say a

times c plus adi, right? A times c plus a times di plus, bi times c which is I could write as bci. Plus, look this is crazy

this is the fun part. Plus bi times di, which is bdi squared. Hey guess what? Remember how I wrote up on the board over here i squared equals negative one? By the way somebody pointed

out that the traditional way you might see this written is like, i is the solution to x

squared plus one equals zero. You could see that’s the same thing. X squared equals negative one. Or you could also think of

it as the square root of negative one although somebody, YouTube comment I had

earlier said that’s not a good way to describe it but whatever. This is negative one, so guess what? This becomes negative one which

means this is just a minus. And now a complex number is

real and imaginary components. What’s the real component? The real component is ac minus bd. And the imaginary component,

also I could pop out that distributive property

again as a, whoops ah! Ad… Plus sorry, plus bci. So this is the real component and this is the imaginary component. We have just done, I don’t know what is y, I just can’t believe this

is the coding train first. Complex number mathematics. Now the truth of the

matter is I could probably spend a whole video,

many videos building out an entire complex number class. But I’m just going to

stick to what we need, which basically is just

the multiplication. Alright just in case, just to be sure. I quickly Googled, how do

you multiply complex numbers? And the same notation is here and the same answer dare I say is there. And then I was also reminded

also by the chat, that there is an acronym FOIL, for a

way of remembering this. First, Outer, Inner, Last. (bell ringing) Hah I looked it up I figured it out! First is you first

multiply a and c together. Then you multiply the outer. Which is a and d, right? Oh wait, hold on, hold on. First, first, outer, inner, last. First, outer, inner, last. We’ve got a new coding train

song called FOIL, FOIL, FOIL. (bell ringing) Alright it’s time now, what we can do is take this result that we’ve got here, and add it to the complex number class as a multiplication function. So let’s imagine I am saying I have a complex number dot multiply

another complex number. Which I’ll call c. And so the one complex number is this, and the other complex number is c. So I need to make the, the real component is, this real component times, I’m looking over there on the

white board at this formula. Times c, is the other’s real component, minus this real component, no, yes, no, no, no, this imaginary

component (laughs), is written as b over there. Times the others, d is its imaginary component. Okay. And then the imaginary component is this real component times the

other’s imaginary component plus this imaginary

component times the other’s, let’s see, c, c, c, is the other’s real component. Let’s take a moment to

meditate on that and wait for the chat to tell me I did it wrong. (laughs) And then I’m going to say return, a new complex number with

this real component and this imaginary component. Okay. So now, I should be able to say… Sum.add, x index n, oh I need a new complex number. Okay so I also need, now I

need to make a complex number. I’ll call it c. For what? I need to make a complex

number that is cosign, of this and negative sign of this, okay? So this is the, I did this before but I

just never bothered to separate it out. So my complex number is

a new complex number with cosign of phi and

negative sign of the phi. That’s the complex number. And then the, if I take, sorry x, sum.add x of n, dot multiply c. So I want to add up, this complex number multiplied with c added up to the sum. What does that mean? I need an add function. And so if I go back to

the Fourier class up here. I can write an add

function which also takes a complex number and I just add

the real components together and the imaginary components together, like this. Now I’ve done something

sort of terrible here where the add function adds to, (laughs) this particular

complex number rather than returning a new one and

the multiply function returns a new one. And that’s definitely an opportunity for, (upbeat alternative music)

refactoring this later. But I’m going to just leave that for now. This is not good object-oriented

programming design, maybe I won’t want it to be static, but I’m going to leave that as is. Woo, okay. Then I can say sum, and

I’m just going to do this. Let’s just leave this, I

could write a divide function, but I’m just going to leave this as this. And I think, dare I say, this is now done. This is now the version, and somebody in the chat is telling me I’ve made a mistake so hold that thought. This is the version of this

algorithm where this array is no longer just an array of

floating point numbers but is an array of complex numbers. Ah yes, this is c. I was saying other in my

head but it is c, thank you. So let’s just see, dare I say, let’s just console log

Fourier x and see what I get. Re is not defined, Fourier line 33. I’m sure I forgot, oh boy, oh boy. I forgot (laughs), that now all of this is in an object. Again I should put in

the complex number class, a magnitude function. And an angle function, but

I’ll just do it this way. And then I have to say this. I’m just going to, this really

should be refactored but I will leave it like this

just to see if it works. Great, so here we go and we

can see what does it look like. I have a real component, I have

a frequency, I have a phase, I have a real, where is

the imaginary component? Huh? Okay let’s go back, ah,

imaginary component. Let’s try that again. I have in each one of

these, a real component and an imaginary, you can’t see this. A real component and an

imaginary component, a frequency, a phase, and an amplitude. Those are all the things I need. Now, we’re not going to

know if this worked ’till I try to draw it. All these numbers they’re there. There’s no not a number. But I’m just going to hope. (drum beat) There’s a lot more code

for me to write before I can actually run it. So this timpani sound is premature. Alright so a couple things, one is it’s complaining

to me that there’s some leftover Fourier y in sketch line 58. Oh okay well that’s just the length and we have Fourier x now. Whoops, ah! No errors. (laughs) This is a long timpani sound. So I just need to do the epicycles. This is stuff I wrote in the

previous coding challenge. It’s calculating all

the epicycles based on a particular Fourier series

that was calculated from the Fourier transform. I don’t need separate vx and vy. So and I can just basically, this is actually simpler now,

we don’t need these lines. And what I should be able to do is there. It should actually just be this, ironically it’s a lot simpler, right? ‘Cus all I need to do is

get all the epicycles, the epicycles return

this function epicycles, which I never liked that

I capitalized the c. So let’s fix that. This epicycle’s function

basically goes through and calculates all the xy positions

of the circles and angles. It was done before but the

same function should stand. And now, (rapid drum beat) (laughs) (celebratory orchestral music) Thank you, thank you. Great job, it is now, done, look at that! Woo! Alright so that is the Fourier Transform. Now okay, quickly, quickly, quickly. Let’s not go just yet. I really vastly prefer the

version where the user has to draw their own thing. This is another version of

the coding challenge that I made where the user

just draws something. And very quickly let me bring in my new Discrete Fourier Transform

algorithm to this one. Just so we can see this at play. So what I’m going to do is

I’m going to go over here, to Fourier.js, I’m going

to paste it into here. And so I now have the new algorithm there, then I’m going to go into sketch.js. And the drawing is, so again I don’t have x’s and y’s. Just the x’s. And the x is a new complex number. With the x and y of the drawing, as a component. Just want to see how quickly

I can get this to work, then I’m sorting it. And then all of this is the

same and then here this is just creating the drawing offset by the middle of the screen. And then put that offset in

here, same sort of thing. I can just change this. I don’t like that that function

had the capital c in it so I must fix that as well. A little refactoring now instead of later. I can get rid of these

lines and here we go. And now, 26 I’m missing a parenthesis. Ah, need another parenthesis here. And now alright let’s see. (rapid drum beat) I’m going to draw a little cat. This is going to be really

sad when this doesn’t work. It has to be a continuous path. It’d be interesting to try to do this without a continuous path. Ah! (foot stomping on the floor)

Oh! You can see it did it,

it calculated it but… (sad trombone music)

I need a better sound than that trombone thing, it’s a little cheesy. I mean all of this is cheesy. Fourier y is not defined. I better not do an

elaborate drawing next time. (laughs) Before I, so let’s just redraw it really quick. Okay now it works. Okay. (rapid drum beat) We’ll do my cat now. (laughs) Hold on. (celebratory orchestral music) So now this really is the

end of the coding challenge. There it is. Fourier Transform of a

complex number series into orbiting epicycles drawing this beautiful, Meow, meow, meow, meow. Don’t have a cat sound, it’s a cat. Thank you very much for watching. If you make something from

this, please share it with me. One thing you might try is go look at that quick draw data set, so watch one of my previous coding challenges, or maybe the sketch RNN,

machine learning model. Those will be interesting things to combine with this, right? I think there’s some

interesting possibilities there. Okay? (lips smacking) See you soon. (upbeat pop music) (bell ringing)

1m

holla second one ……

third

I'm the first like lol

Would be super neat to turn an image into a Fourier series.

Maybe edge detection then vertex detection some kind of travelling salesman algorithm to find a path along those edges to get the points.

That'd be pretty dope.

Wow.. This blows me away more than the fact that man went to space and are living there. It just blows my mind so much, just a bunch of circles rotating drawing such things? So damn awesome!

wow great mathematics

Great episode 🙂

Now I have to go implement it by myself 😁

Keep up the good work 👍

Keeps us motivating Sir, awesome coding challenge…

"Nice" + "!".repeat(Infinity)

I'm just wondering if there is a thing like '3D Fourier Transform'. Just what you have now, but with a Z-axis

Wow. I wasn't getting the point of this effort until it started working… Wow

As an engineering nerd and professional programmer (and fellow youtuber) this sort of stuff really gets me going! Awesome job as always Dan 🙂

14:16 Dan the Dancer

I came too late in the stream to get most of this. Time to watch now!

Why I'm bad in algorithm and problem solving? 🙁 I love programming

4:10 your pointing was wrong you pointed to the outer and said last

Grand Slam Dan thE Man ! best yet imo Soooooo Cool

Woah

Hey big man…. You have to reference Welch Labs if you're going to talk about complex numbers…. https://www.youtube.com/user/Taylorns34

Please make some C++ tutorials. Btw,you're the best coding "teacher" (if i can say so)that i know

hi dan! i have proposition for next coding challange : 2048 game in p5.js

You should make a working rubik's cube in p5.js! You could be able to change the size and stuff too!

Very cool video! I'm quickly becoming obsessed with your channel. 🙂 Just a heads up, we use the term "double distribute" now instead of foil. This is because foil only applies to the case of multiplying a binomial by another binomial and implies you're using a "trick", but you can always distribute, double distribute, triple distribute and so on and so forth and it is mathematically sound and flexible.

To multiply complex numbers you can also convert them to polar form and then add the phase angles and multiply the magnitudes.

nice video i really like it

Your videos are amazing and hilarious, thanks for all of your hard work in making these!

i tried that code but, instead to sort by amps, sorted by frequencies, lower first, also begin from part of frequencies (from lower parts beginning); with increase count of wheels, when T is bigger than TWO_PI, just T decrease by TWO_PI, and don't clear previous path, instead to cut end, (you do it on earlier videos). Sorry for complex phrases ))) English is not my native. Result – I have a total mess in beginning, and it gradually draw a something, tried to reach a exact result of Coding Train ))). Very interesting result in live motion.

Hi sir it would be a great help if you do breaking glass effect and fluid Dynamics ……thankyou

Next coding challenge is Tic tac toe or lightning storm in P2D or P3D.

Sir what are our thoughts on Mike Boyd's video?In which he mentioned you,I am subscribed to both of you from a long time and you guys are one of the best content creators in the world.

What do you think about c++?

Hey! Really loved this challenge! Maybe doing this with FFT would be nice too

I’ve watched you GA series and I do have an app that uses GA as part of my master’s dissertation, I have the fitness function and all problem variables but need help in organizing my thoughts. How to reach you ?

Wow!

Hello, new subscriber from Mike's channel. I always wanted to try coding. Here I go… 🙂 Thumbs up on your channel!!

You make every topic appear so simple! You are not just very knowledgeable, but an excellent teacher. Thank you so much for creating videos.I am trying to understand topics related to concurrency and wanted to request you to please consider making videos for the following problems:

i) Execute at most N tasks in parallel using JS promises or generators

ii) Implement an asynchronous concurrent priority queue

iii) Write your own version of V8’s event queue

You inspired Mike Boyd to make his own game using p5.js and he made great game. Check his video https://www.youtube.com/watch?v=s12npdDmGUc

Hey i have a question, how do you get your p5.js to show up in your browser. Thank you!

Hey just curious, why did you swap to VSCode from Atom?

Can you give a video about how you set up everything?

dan looks like a college professor and I dont know if thats a good thing or not.

For your information. This part never worked for me. I tried best to imitate your code on the screen but never worked. it agonized me for 3 days to find out what causing this. I definitely don't spend entire day with coding though. I tried adding arbitrary value to phase but my code insisted drawing strange curves or ellipses, not even close to original picture. I watched again mahologer and goldplated goof channel. and I found my code and your code too has k value ranged 0 to N-1. their k was like ..-2,-1,0,1,2.. . so i changed it to iterate k = -2/N to 2/N.

and it works very well now. I did not changed other part of code. I still don't understand how this is going on mathmatically but if anyone suffering similar symptom, try these minus k range. thank you.

Love these, you should try to do a program to predict a sequence given an array of numbers that follow a certain sequence, I was learning ab sequences in math and thought it would be cool to see but it seems hard to implement and there's not too many good videos on it

Would be cool to see the matching cubes algorithm done in processing.

Genius

Hey can you make a Ludo game in processing. Ludo game challenge please 🙏

Are the number of circles increasing and decreasing as the transform moves around the path?

Who came here after watching smarter every -days video on this?

thanks for helping me out bro! This helped me so much i kind of understand coding now !LOL!

I started programming because of you😊

I watched Mathologer's video about the Homer Simpson drawing, and his explanation of the Fourier Transform and the math behind it all. However, I never knew how EASY it actually is to do… Thanks for the videos!

I never understand why you can just leave out the i 🙁

The output array of the dft function doesn't have to be the same size as the input array. The number of output values you return determines how accurately it will follow the data…