Fibonacci

[00:00:00]
>> Now, at this point you should be looking to yourself and saying, like, this is insanity. Every time I change program, I have to change all these values, right? And so you need a compiler, pretty quickly you're like, I need a compiler. And what the compiler allows you to do is to say things like, hey, into a0 I wanna load the address of the data section.

[00:00:19]
And I'm just gonna put a label where the data section is, right. And so when the compiler runs it like does the math and figures it out and like yeah that's 37 and just puts it over there, right. You don't have to do that because you'll just go crazy always changing these values right like imagine every time you add the feature to the program you have to go back and like recompute all these things it's just insanity.

[00:00:42]
So that's basically the difference between assembly and machine language, machine language is just numbers, right? Assembly are for each number we look up its corresponding name on the instruction name of the instruction, so we say load ae instead of 37. And instead of random number, it puts an address, we can put an actual text label in there, and so we know that if we add things, shift things around, the compiler will recompute all these things so you don't have to worry about it, right?

[00:01:10]
And it also makes it much easier for you to read, because now you'll be like, yeah, so a0 gets the address. A1 gets zero then we call the gosubroutine which is the increment. Then we look at array location one increment two, increment three increment halt, right, much easier to read, right?

[00:01:27]
Okay, what does the subroutine label do? Well, the label is increment and what it does is it reads from the memory. It increments the value, stores it back in there. And by the way, the subroutine automatically produces the return instruction and anything else that you need to kinda not worry about it.

[00:01:46]
And then you just have your label for data section and label for Stack. And you know that things get initialized, and everything works, right? This is assembly right here. A little more complicated, but fundamentally that's what it's. Okay, let's implement Fibonacci. So the way Fibonacci works is again, we have to load the data location at zero, and we call the Fibonacci.

[00:02:17]
Go to the subroutine Fibonacci and then we store the result inside of location one and so what is that location zero. So location zero is four so we're asking for the fourth Fibonacci number, right. Okay, so how does it work? The subroutine has a label notice. We save, say, save R1, meaning that in the process of executing this particular code, we're gonna destroy the value of R1.

[00:02:45]
What it means is that we are gonna have to push R1 on a stack. The way this works is you push R1 on a stack, then you do whatever set of instructions you want. And then on the end of it, you pop it out of the stack, right?

[00:02:59]
So the stack not only can store your program counter information, it can also store arbitrary data, including local variables that but that's an advanced concept that we haven't we're not getting into yet. And so this is an example of calling convention, right. We have a deal that when I call a subroutine and when I come back out of it the R1 is going to have the parameter I'm passing in or the result value.

[00:03:25]
So the R1 is used both as an input and an output. Sorry, R0, not R1. And I really don't want you to mess with R1, that is not for you. So if you need to use R1 for some internal things, make sure you save it so that it's available later.

[00:03:42]
And then we can do a comparator instruction. Now remember, at the beginning I said the R0 is little special because when you write into the R0 you set flags. And so what set flags operation does is it says there is a set of bits and says if the value you set is zero, then we'll set a bit if the value is negative, then we'll set a bid if its value is positive, we set a bid, right?

[00:04:09]
And what that allows you to do, is to run a compare instruction. And what compare instruction basically is, a subtraction where you throw away the result. And so you compare it to zero, in other words, you subtract it from zero, and the only time that it's zero is if it's the same number, right?

[00:04:26]
And if you get a negative number, then you know you're less than. If you get a positive then you're greater than etc. And this is basically how you do an if statement. So you do a subtraction which sets a set of flags. And then based on the flags you have special instructions that basically say jump.

[00:04:43]
So, the way that works is that you run your expression which modifies the flags. Then you wanna run your condition in this particular case, it is jump if less than or equal to. And then the condition then has to have a label of where you wanna go to the then location.

[00:05:05]
So you have to have a label for then and you have to have a label for end and so now this if condition either ends up in this location or this location. And then, obviously, if you end up in the else, then you have to jump out of it so you don't double run the end of it, so you have to have a label end in here as well.

[00:05:24]
So you can see how an if statement is actually a bunch of jumps that happen in order to kind of figure out what's going on for the CPU. Does that make sense, or was it too fast?
>> A little fast.
>> A little fast, okay, so basically you run an expression in.

[00:05:47]
So let me just actually do this next to each other. You run a comparator expression which basically is just a subtraction. And the side effect of subtraction is that you set flags in the flags register, okay. These flags are things like, is it zero, is it a positive number, is it a negative number, was it an overflow, is it a carryover, like there's a bunch of different flags that exist in the system.

[00:06:11]
So this instruction that you run, so R0 is special that whatever value you write into R0, again, depends on architecture but typically R0 is special that it ends up affecting the flags register. So by subtracting the R0 from some number unit, we can then see if that number was bigger, smaller equal to whatever, right?

[00:06:32]
And so now based on that you wanna do a conditional jump. In other words, you wanna modify the programme counter to some other address, but only if as positive or negative or equal to, right? And so this is the conditional jump that says hey jump but only if this was true.

[00:06:51]
If it was not true then don't jump, right? So right after the condition you have to give it an address of where exactly you should be jumping, so you make a branch, right? You're either gonna jump or you're not gonna jump. And jump is just like I'm either gonna update the program counter or not, right?

[00:07:09]
It's all it is. So in this case, if I don't update the program counter and I'm running the else branch, which means there's a set of instructions that that deal with the else work. And when the else work is done because the else work is followed by the then work I gotta jump over that, right?

[00:07:26]
So I have to have non conditional jump like I always have to jump over that because I'm into it I have to end up here, right? I have to end up at the label end so if I did jump to the then section then I can just continue running through.

[00:07:39]
If I ended up in the else section then I have to jump out of it, jump over the then section to end up in here. This is pretty low level, right? This is not how you normally think about your if conditions, right? It's just a block, you put curlies.

[00:07:56]
But those curlies somehow have to translate into all of this on the end of the day. Okay, so what this basically says that if you have, if the value of R0, which is the argument into the Fibonacci sequence is 0, then load the result to be 0, and because it's a then, it just falls through and exits the thing, right?

[00:08:22]
So Fibonacci sequence of 0 is 0. Pibonacci sequence of 1 is 1. So you load the result into R0 and then you exit the subroutine, right? So now R0 will contain the result value, either 0 or 1 depending on whether it's 0 or 1, okay. Otherwise, what we're gonna do is we're gonna decrement R0, because the Fibonacci sequence is the sum of the previous two numbers in sequences, right?

[00:08:53]
By the way, did you hear about the Fibonacci conference? It was as big as the last two put together. So you decrement R0, right, and then you make a copy of R0 to put it in the R1, register. But now we're using R1 register, this is the reason why we had to save it.

[00:09:11]
Because if we didn't save it, then the program that called us would be like, hey, you changed my value, that's no good, right? So we had to save it at the beginning. So we make a copy of the value inside R1 register and then we recursively call ourselves, right?

[00:09:27]
So, it goes up to ourselves so that we can compute the result and now we know that the result is gonna be in R0, okay? Now, we need to save R0, so we push it on a stack. And now we can take the R1 and put it back into R0, decrement it one more time, and now call ourselves again, and now we have the result again in R0, and we move it from R0 to R1.

[00:09:56]
And then maybe restore the R0 we had over here, we pop it from the stack. So, now the R0 will contain the Fibonacci of x-1. And now, the R1 contains the Fibonacci of x-2. We add them together. And now, the R0 contains the Fibonacci sequence that we want.

[00:10:18]
So, we can execute this. And you can see that you can see that it recuses quite a lot internally because we all know that Fibonacci is quite a recursive etc. And you can also see that at the beginning we started with four is our kind of the initial value we were interested in to compute.

[00:10:44]
And then by the time we're done, you see the answer three is in here. But notice what's in the back of here, there's a bunch of garbage that ended up in here see all this stuff here. That's a leftover stuff of our stack because when we push things on a stack, we wrote into memory.

[00:11:00]
But when you pop things out, we didn't bother clean up, because that's just extra work, why would you do that? And so now there is potentially dangerous information in there. Let's say somebody pushed a private key onto a stack. And now that memory in one program shuts down and you start up another program and now the program gets that memory.

[00:11:19]
So part of the job of the operating system is to clear that memory to make sure like, there is nothing there when it gives it to you, because you could like accidentally read somebody else's stuff. And you can also see how the stack has kind of grown backwards, right, in towards the data, but hopefully we had enough space.

[00:11:39]
So if I go here and just modify where is my number here. So five so that's the input this is the result, right, if I just modify it to five and I rerun it now you can see that and five is funny because five of the answer is 5 and 4 of the answer is 4, okay, 6.

[00:12:04]
6, the answer is 8, right? So now, you can see that it's computing the other numbers, and you can see just how expensive it was in terms of computation, right? It's quite a lot of stuff that happened inside of it. And notice, the bigger the number you choose, the further the stack has grown into you, right?

[00:12:21]
And so at some point, the stack is so big that it will collide with you. And so that's why you have to have extra stuff in there, inside of it. Okay, so this was kind of the main thing of like showing you how a physical CPU works. And I'm kind of hoping that at this point you kinda have a good idea of how things work on the silicon level, right?

[00:12:48]
What actually is happening under the hood?
>> When numbers are stored in the registers, there'll be.
>> Yes.
>> Binary, when they do addition or subtraction, whatever remember this one to do with like two's complement?
>> Yes.
>> In a different way, doesn't it?
>> So the crazy thing is that CPUs do not know how to subtract.

[00:13:10]
Crazy, right, they can only add negative numbers. And the negative numbers are represented in something called two's complement. And basically it's a negative number I believe don't quote me it's been years but I believe you just take the value of the positive number, you flip all the bits so one becomes 00 becomes 1 and then you add 1 to it into it.

[00:13:33]
And for some strange reason, that particular optimization is called two's complement. And the two's complement has this nice property that if you add it to a number, you've effectively done a subtraction.
>> So would you have one register, basically save for just subtraction.
>> No, the CPU has no instruction for subtraction.

[00:13:56]
I mean, maybe the modern CPUs have for convenience or whatever, but fundamentally, CPUs do not understand subtraction. All they understand is adding two's complement.
>> Yeah.
>> So the compiler will typically take your number and convert it into a two's complement version, and then it will just add it.

[00:14:12]
And so that's the subtraction. So if you say A minus B, it loads B runs a two's complement operation on it, and then just says go and add. And so that's what I mean, like modern CPUs might have a convenience instruction that internally automatically combines two's complement in addition, but in terms of the hardware that does the computation, the arithmetic logic unit only knows how to do additions.