Random Numbers (2 of 2: Linear Congruential Generator)

so let me show you a pseudo-random number oh by the way just to give you some examples you know we said we said dice add coins for this that's a bit pedestrian right in reality people who use true random generator you can go to well I think it's random Dorgan I think is a website which does which time this it uses far more sophisticated and exotic kinds of physical phenomena to users for example it uses a radioactive decay so if you've got like a radioactive particle and it's setting off you know bits of energy it's losing bits of fast right are the quantity at which it does that and the frequency with which it does it is sort of predictable but it's not really predictable right it's it's quite random the other cool thing that they use atmospheric noise so what they've got is uh they've got some microphone pointed at the sky and it's listening to sound and that's pretty pretty random it's about as random as weather right now we can predict weather kind of three days in a row but as anyone knows when they've sort of relied on a weather report and it hasn't come to I that's you know it's it's it's not super liable because of the randomness of it all right so the pseudo-random number generator I'm going to teach you today pretty simple it's called the LCG or I'm giving you the acronym because the full name is a bit of awkward it's a the linear congruent sure generator LCG is a bit better right alright so I'm going to give you the formula that that makes this work the mathematical mechanism that sort of turns the wheels and uh it's pretty simple actually but it's it's quite powerful okay so here's the way the formula works and you'll see hopefully you'll see why the name is what it is so how does the LCG work let me explain it by means of the name okay so what we're going to do is generate random numbers each called X right so there will be the first X the second X the third x a whole bunch of them however many you want however many random numbers you want okay so this is what we call a recursive generator okay or a recurrence relation so you guys know how Fibonacci works right so a Fibonacci number the nth Fibonacci number is equal to the previous two added together right so the nth Fibonacci number is the previous one plus the one before that and that gives you you see this formula relies on itself it's self referential okay so that's what recursion means and this is the same okay so if I want to know what the next number is you take the previous number you multiply it by some number you add something and then you take you do the remainder thing where we're looking at a modular arithmetic right so you can see where the name comes from Linnea comes from the a right it's a linear function right in a very crude way of think about it this is MX plus B this is a straight line okay but it's congruent sure because this R is much of a fitting thing right it's the idea of numbers being congruent to one another okay so for example this example I'm going to give is um the modulus thing is is five okay so we're dividing by five so soon and seven in this scheme are congruent right they're the same number really they're both going to reduce that to okay so this idea of congruence is really a frame to the fact that it's using modular arithmetic so you need some conditions you've got these three numbers here they've all got to be less than whatever you want to take of okay all the values have the positive integers that's fine X naught that's a subscript not an index okay is the seen number it's what you start with it's just starting point okay so here our our building blocks here's an example okay I messed up with one as my seed number and then I just kind of picked some numbers at random I picked them all very small so that we can follow the maps but just like with prime numbers right this whole process gets more and more effective than larger our numbers are all right so let's give this a go let's start crunching through it okay we've got our first random number here what's not really random we chose earth okay so how do I get the next one x1 what's it going to be equal to well you go a times X naught the previous one so that's going to be two times one you're going to add this constant C per constant and then you're going to score more funny so far so good so let's work this out 2 plus 3 is 5 so this is 5 1 5 so to do this mod bit you say well what's the remainder after I divide by 5 and the answer is 0 good so x1 our first real random number is 0 now how do we get the next one x2 ok you repeat the process we can do this probably be a bit quicker company ok to tire 0 plus 3 is 3 and when you take mine 500m star into 5 on time so this is just going to be 3 I just went you we knew it was going to have these properties ok what's going to matter is the numbers that come out there now I look at X 3 okay what's going to happen I'm going to go 2 times 2 times 3 which is 6 plus 3 which is 9 so I've got to go 9 mod 5 which is 4 okay so another four and we'll do the fourth one ok 4 times 2 which is 8 plus 3 that's 11 mod 5 now I take the remainder after I divide by five as many times I can I decide by five once or you take away five you get six you can take away again now I've got one okay now what has happened I've returned to one which was my seed number here okay so you can see why it's periodic okay now by the way semi codes dentally I hit that the period of five after going to the fourth number why was it the fourth number do you think wait wait why did I hit after like seven or eight or nine can you see this is kind of like my limiting factor right because no matter what I remember I get out here I'm gonna get I'm gonna get zero one two three or four I can't get anything higher because I'm going to go mod five on whatever result I get right so I'm circling around zero one two three four in some kind of order now do you have a look at the order what number what order if we ended up with we've got one zero one three and then four so I actually skip down on to starting one I'll never get to add this because now that I've got two four I'll get back to one so I'll go one two three four one zero three four and this is like there's some randomness to this right like you could have come up with a random series of numbers and this could have been here okay so it has that uniform distribution nature to it okay but it has these problems you can see now this is what we this is what we did right we just had the same numbers we had x 2 adding 3 and then taking your modulus of 5 is my I put it in red because this is my seed number this is what I started with what you got here are one of the prime which prime number of magic first second third fourth fifth six and sure enough here the same results that we just got one zero three four one two three four no no no no so I want to show you well if i graph those okay you can clearly see the period picture of what's happening right there is one zero three four one zero three four and it's happening over again okay now the great thing about doing this buying computer is that I can adjust these dynamically right rather than crunch through all the numbers of things for a lot of it so for instance if I change let's cheat a single number okay let's just change the modulus what we're dividing by finding window so if I change it to 6 okay what do you get now what happens hmm this is worse than what we had before I wonder if you can work out why look I'm only going 1/5 1/5 1/5 I keep back and forth doesn't look good well it's good guy who's trying I'm like 707 is a bit more your school it's better when you sure what did you think why is 7i more useful number it seems ok guy straight hey it's a it's a bag what happened 8 I like to 8 right I get 5 and then what happens I go 5 times 2 which is 10 then I have 3 which is 13 and then I take away 8 which lands me back on 5 so you kind of automatic option by choice right let's go to 9 I can now I'm signing it something more interesting now as the number gets bigger you can see that these numbers are getting really because I've got more numbers to choose from I can get a 0 1 2 3 4 5 6 7 8 before I have to come back to all real of so that's looking better what if I go 10 why I go 11 now just hold on many undo that yeah I just changed a single number neither changed by one tense okay but 11 is much better why would 11 be better so much better than 10 I got 12 okay think about this 10 okay 11 good 12 awful why is 12 so bad it's a silly factors but not only is it not prime it's very very not prime okay see you see you see how prime numbers and what is it today I don't keep going let's up let's skip forward a little bit a little bit I'm gonna go on to a hundred how do I get a hundred Oh now remember I said we're play with pretty small numbers for a computer a hundred is still a very small number but it looks pretty good doesn't it right now watch what happens if I just go up just go up 101 it's very different isn't it if I go up again now you see what we talked about when we say random right every time I go up you're getting quite drastically different ups by the way you might have noticed as I went through all I do them you can see it in a row even though this part sees to be changing quite a lot this part doesn't watch it again go back 1 2 3 why is that bit so consistent I know because I think the numbers I'm getting slowly up to the original good ok so remember this is the linear complementary generator right so this thing over here is kind of mimicking what a linear function is doing is I know it doesn't look like it because there's there's that adding of a clustered right but it's growing a linear rate until it hits somewhere where when you multiply the next one it goes over the threshold ok and the modulus kind of kicks in and then it started to get really interesting axle hat closes for prime a bit both better as you can see right it's not completely it's not really random I mean if you knew these numbers you get exactly the same thing out but it's random enough right if I gave you look at these look at these numbers if I gave you this list of numbers you didn't see the graph okay 1 5 13 2961 if we play that kind of game where it's like you know you get one of these quizzes guess the next number in the sequence right you're gonna know what's the difference there he was there and then it's gonna be like 51 before what just happen it should hope so it has enough randomness to it to actually use damage it's gonna be a bit tricky when you think about module Susan like boy let's look I don't know as you see what happens 3.1415 it was you can put the symbol in it what's happening there so there you go random number generators they're kind of like a lost piece of the puzzle when it comes to cryptography

Channel: Eddie Woo

Views: 36,586

Rating: 4.9941521 out of 5

Keywords: math, maths, mathematics, Linear Congruential Generator, Random Number Generation, Randomness (Literature Subject)

Id: PtEivGPxwAI

Length: 12min 46sec (766 seconds)

Published: Fri Nov 14 2014