NMCS4ALL: Random number generators

Twenty minute introduction to randomness and pseudorandom number generators, with demos. The New Mexico CS for All project is teaching computational thinking and programming.
PLEASE NOTE: I WILL NOT HELP YOU 'PREDICT RANDOM NUMBERS' UNDER ANY CIRCUMSTANCES.
Production supported by the National Science Foundation, award # CNS 1240992

[@jasonthomas2908]

This is great. I really enjoyed the observation about how we perceive large things to be constant, small things to be random, and everything else having cause and effect. That's a great observation.

[@DaveAckley]

That's my favorite bit in the video. Thanks for the comment.

[@augustjohnny1913]

instablaster

[@GNU_Linux_for_good]

That's one cool video. Very well explained, in a clear voice, black background, and on top of it: the animation on the left. Bravo.

[@DaveAckley]

FreeSoftware Thanks.

[@insearchoftrance5214]

Dave Ackley can you text me 281-995-5091 or email me [e-mail] I have to tell you something

[@EliGamesOfficial]

Please, never stop doing what you do. I am in awe of your instructional quality.

[@livelaurent]

Just subscribed. Discovered your video series today (started with the Artificial Life one) and they are really good. Your way of explaining things and the format is just perfect to me :) Great job, we need more like you on the Internet!

[@zyenapz]

What a really elusive topic, if I do say so myself! Thanks for the really simple explanations and the graphical representations. I appreciate how you explained how a Mersenne Twister works in a simple manner. I was looking for videos on it and chanced upon yours! Your channel is interesting and might check out more of your videos in the future! Have a nice day!

[@kikemelly81]

Brilliant video, Dave! Thank you very much.

[@Ani-sf4yr]

A doubt I have from 5 years has been cleared finally thank you sir. Mind Blowing explination.

[@nateshrager512]

Fantastic breakdown and love the Mersenne Twister demonstration

[@MudHoleCreation]

Wow. Great explanation, and visualization.

[@bha9036456887]

Awesome video! Very well explained.

[@nomorehentai1331]

Quality content! Can't think other word to describe

[@ThankYouESM]

Liked and Subscribed! I've been trying forever to figure out how to generate 600x600 smooth images of a seemingly infinite variety without random that has constraints such as not allowing for there to be more than 10 of the same RGB values.

[@tiberiu_nicolae]

Your channel is excellent! You should have more viewers!

[@DaveAckley]

Thanks for watching! The viewers seem to be arriving slowly but steadily now.

[@RahulJain-wr6kx]

Thats too god, It helped me to understand this Practically.. Thank you so much for sharing it

[@anindyakusumaningrum341]

thank you for sharing, it helped me a lot.

[@gurkiratsingh1216]

Great video helped me in understanding basic concept.

[@bertblankenstein3738]

Thank you for not going through the entire Mersenne Twister sequence. Thank you for the video.

[@khisteatul123]

Dave , I hope you are doing great !!!!!!!! thanks for sharing this useful video. Very few people understands it practically... :) :) I am following your channel.

[@DaveAckley]

Thanks for the comment!

[@PvblivsAelivs]

The Mersenne Twister is a lot like a linear congruential generator except that it operates in a different type of field. An LCG (designed to be maximal length) with a similarly sized modulus would be equally good (or equally bad, depending on your point of view.)

[@insearchoftrance5214]

So is it impossible to find the next term in a sequence without knowing any of the inputs and just knowing three terms in a sequence of six.

[@DaveWhoa]

cool to see MT visualised like that

[@fixfaxerify]

Is it possible to gauge randomness by something similar to a discrete Fourier transform? Like simple repeating bit patterns would have a fundamental and very few "harmonics", whereas the spectral pattern with equal number in every bin would correspond to the most random string of bits. Is that feasible?

[@VinVinzens]

great explanation, thx prof.! 🙂

[@smashinglabu3942]

The best video for explanation about RNG... can you share formula for number begin with 4 and end with 46?

[@nak6608]

Awesome video! I subscribed to your channel. Keep it up

[@DaveAckley]

+naK Leon Thanks!

[@puruagarwal8356]

Amazing Video!! Even if we find a source to generate random numbers, them how do we use that source as a part of our code?

[@gabrielrobin3956]

thanks for the video !!!

[@JGunlimited]

sweet explanation!

[@thyagtubes]

Awesome lecture|

[@trejohnson7677]

This is a human treasure.

[@jobmathenge8111]

Awesome...

[@ehsanreghabi]

Jackpot!! what a channle ! What a Guy!

[@gianlucaconsagro7429]

Complimenti Prof è possibile avere il software..?Volevo chiedere c'è possibilità di realizzare un RNG per le scommesse virtuali calcio cavalli cani etc..?grazie

[@ajzaff2]

As I understand, some scenarios exist where you can get "undefined behavior," out of a computer. (As in the order of execution on forked processes, for example). This has always been interesting to me. Could this be used as a random source?

[@DaveAckley]

ajzaf 'Undefined' typically means there's no promise the behavior will be predictable. But for a good random source, what we really want is a promise the behavior will be unpredictable. Thanks for the question!

[@onedevil420]

Thank you for creating the amazing video. you are great. Sir I have a series of number that I want to predict next number I searched a lot on the internet I don't know much about PRNG and everything I watch on the internet is out of my mind . Sir If I give you the series of the number can you do any kind of tests on them. This will be very helpful to me. I just want to know that these numbers are really random or not. I convert last number to binary number system then I inverse 0 instead of 1 and 1 instead of 0 then I get three decimal digits that are included in 6 digit random number.

[@DaveAckley]

+Capstan Cig I generally don't do that sort of consulting work, but good luck understanding your numbers and thanks for the comment!

[@PunmasterSTP]

If you didn't know ahead of time that primes could be used to generate random numbers, then you're in for a twist!

[@primodernious]

random number generators are very important. without them we can not simulate evolution. i use them all the time for al kinds of program projects what ever algorithms i want to make.

[@primodernious]

check out this video. its from someone else. kzbin.info/www/bejne/eaPZfKiCeauhbNk its shows evolution in action. its not perfect, but it works as designed.

[@tiernanmorgan]

ive been trying to understand the prng in slots machines if you know the seed is datetime i feel like you could fine patterns if you graph out outcomes overt time down to the .001 of a second

[@ytw6461]

impressive！

[@KeithWiley]

Heh heh. This is great Dave. I just found your channel. Hope all's well.

[@DaveAckley]

Hey Keith! Been a while. Thanks for the comment!

[@3mptyzer016]

Thank you sooo much wise dude Dave, even in the epoch of A.I. it is so nicer just to listen smn with a deep voice explain everything like, with structure and professionalism 🤌

[@davidrealphanzer8148]

Wow it's amazing, Can you explain the random generator in lotto machine?

[@abhinavgaur13]

@Dave Have you shared the source code of the animation anywhere?

[@DaveAckley]

I work viz code up just enough to make the (whichever) video, and it's far faaar from distribution quality..

[@rahulprasad2318]

Nice

[@ThYRaNdOmTr011]

Neat stuff

[@karemali4551]

You Are Great i never understood some thing that easily Thank You For That

[@bryceevans1143]

good video

[@mckinley3]

Could you output the answer in a random number generator?

[@madmike178]

This was awesome, I feel justified grabbing my silly games numbers from a hrng now... Though some ugrad in 2050 will probably still be able to guess them. lol.

[@drs9489]

I wish I had intelligent people like him around me to talk to. Every time I try to talk to anybody I know about the things that interest me they look like deer in my headlights.

[@simonmultiverse6349]

I know that look.

[@carleeto302]

What visual programming language are you using?

[@T2TileProject]

It's just Java/Swing

[@DrSlots-hs4if]

Wow.... Why delete my post? Did I do something wrong? Or was it because I wrote SLOTS are not random....with the explanation to it?

[@DaveAckley]

Apologies! I sometimes see weird YT behavior with vanishing comments, but I haven't deleted any comments myself in years. I don't see anything in 'Held for review' either..

[@zifnow]

Hi Dave. I play a game where the RNG is based on MTwister. It involves, for various reasons, to roll a D100. Some player claims there are far too much streak of rolls which "break" the chances, like rolling a 5% chance twice or three in a row, not too rarely 4 times. I mean it not happens all times but that definitely happens, and it's 1/160000 chance, on a playerbase of 2k people. Not impossible but unlikely; anyway rolling 5% twice in a row is 1/400, when that happens in a couple tens rolls more than once players get upset (when the game AI screws them that way). Now, as you can imagine there are two parties: those who claims that RNG is broken and those who claims RNG is fine, usually the last party include players which are very good in the game. My opinion is that being good or bad at the game has nothing to do with the RNG quality. Good players mindfully put in strategies which minimize the RNG impact, and exploit several other aspect of the game. The only way to tell that a RNG is good is that it should show, as you explained, no pattern and it should be unpredictable. I woud like to gather data from the game, like to track the rolls and put them on a spreadsheet and by the least check how many times streaks of double, triple, poker rolls happens within a fixed number of rolls. Do you think that could work as a testing bench, or would you suggest me something to make an analysis? Awesome video btw.

[@DaveAckley]

There's lots of PRNG test suites out there -- DIEHARD, DIEHARDER, SP800-22... But MT has been pretty thoroughly studied, and humans are notoriously bad at estimating the likelihood of random sequences, particularly runs. That said, for sure you could test your specific code to make sure nothing funny is happening downstream of the PRNG, and the stats are close to the expected in the long run.

[@danded2192]

Genius.... Super... Your explanation is make sense,, can you broke the "higgs domino island" slot game for me please,,

[@SJAutomotiveDesign]

3:46 your pattern seems to produce numbers that are one even, one odd. :)

[@GamingX8631]

u r really great.i am very glad to know it cz it was badly need for me thanx a lot Dave Ackley.

[@henryhache5509]

I put this on when i want to go to sleep...

[@smashinglabu3942]

20, 8, 6, 15, 35, 6, 10, 5, 20, 23, 14, 28, 28.....

[@jamesPratt-cm6yk]

Lotteries are not random because the weight of the balls vary and this causes an unrandom situation

[@tjcogger1974]

Even if all the balls were perfectly calibrated, it wouldn't be truly random. However, it's still not a predictable system.

[@Graeme_Lastname]

I think the casino wants it very predictable.

[@DaveAckley]

But not by the customers..

[@jonahansen]

Very well done.

[@desmondbonnici9636]

18,30,12,15,8,25,0,8,8,25,20,4,5,32 - are these random number generated?

[@Broadsmile1987]

You can’t say really. You could take the first half of the numbers, analyze it and try to predict the second half of the numbers and your accuracy (statistic of how many numbers you got with your predictions) could mean how random these numbers are. The thing is, a statistical error is a thing, and in this case you supplied so few numbers that the statistical error will overshadow any result.

[@stromboli183]

Probably not (for various reasons). But even if you have a 100% true random number generator, at some point you will encounter this subsequence: 4, 4, 4, 4, 4, 4, 4. So you really can’t tell just from the numbers :)

[@cpndSimyule]

this is some craic

[@DaveAckley]

I learned a new word!

[@cpndSimyule]

@@DaveAckley here’s another useful one- suimiúil, it means interesting in Irish! Sim-ule! Which is exactly how I found your video!

[@damon6717]

I can guarantee if you have every sequence possible , you will at least get it right, the problem is , most outcomes will be wrong if your looking specifically for something.

[@PvblivsAelivs]

In fact, the state of the art has not moved on beyond linear congruential generators. LCGs have a lot going for them, especially that they are fast. If the state of the art ever does move beyond LCGs, the Mersenne Twister will be left in the same dust. The Mersenne Twister is a simple linear feedback shift register -- with a terrible sparse feedback polynomial. The only thing that makes it look even halfway decent is that it throws so much state at you -- the very thing you mocked in LCGs ("get these big things out that look like ooh must be really random.") This video is a sales pitch for Mersenne Twister. It downplays flaws in such a way that the unwary won't notice them at all but that gives you a way to say that you mentioned it if called out. There is a lot of theory behind what makes a good LCG. You applied it in reverse to construct an abomination. You point out the flaws in the last bits. Well that's why they are never output -- except when you are trying to make LCGs look worse than they are.

[@cnsnmms3708]

Nice shot. Can I show this in my class? :))

[@DaveAckley]

Sure! What class?

[@MrOz-rt4bz]

Sir, how can we apply Psuedo in Slot Machine ?? Please explain in next video..

[@elctro4079]

3:12 i predicted that 50 some how :)

[@SendyTheEndless]

A random number between zero and infinity.... Infinity :) (always)

[@stromboli183]

What if it has to be between 0 and ∞ non-inclusive? So larger than 0 but smaller than ∞. How do you pick a random positive integer? 😀

[@fredmauck3547]

It’s not random because you are Observing it

[@mukuruagent3346]

Uh um!

[@Rexvideowow]

It's interesting to watch the encoding of the video go to absolute crap on your face once you begin running the twister really fast. lol. And then when you stop it, your face is clear as day once again.

[@DaveAckley]

yeah that pissed me off at first but eventually I decided it was a nice example of Random Don't Compress

[@herminioarlindonhavene5842]

Excellent video and very well explained I hope you are doing great Please Teacher can you give me the algoritm of Marsene that you show in this video? help

[@stromboli183]

Random numbers are too important to be left to chance.

[@simonmultiverse6349]

Seminumerical Algorithms (volume 2 of THAT series) p.5 just after the description of Algorithm K - "random numbers should not be generated with a method chosen at random." tee hee hee.

[@simonmultiverse6349]

For passwords, I wrote a program in Python which puts a series of letters on the screen (pseudo-random), and I have to type each letter as it appears. What is not obvious is that the computer is measuring my reaction time. From each reaction time, the program extracts two bits, which is justifiable based on the measured units of time (about 1/60 of a second on Microsoft products, about 1/600 of a second on Linux). In other words, I'm not trying to extract more randomness than is actually present in my reaction times. This has worked well for a few years. I can tell it how many of each type of character I want (digits, symbols, capital letters and small letters) and then say "go". The program also tells me how many possible passwords there are, based on how many letters, digits, etc. I have asked for. Obviously, I can't generate millions of passwords and analyse the statistics to see if it's really random, but every password looks like a meaningless jumble of letters, digits and symbols, which is the idea. I also have a list of 1296 short words which I downloaded (i.e. 6^4 words, related to diceware). The program can also make a password if I tell it how many words I want from the list. This kind of password is much easier to remember. Three words gives about 2x10^9 possible passwords, four words about 2.8x10^12 passwords.

[@stromboli183]

@@simonmultiverse6349 Interesting! 😄 Nice to see your line of thinking underlying the process. I've been experimenting with something similar. How I generated strong random passwords was like this: First the user can enter random gibberish on his keyboard and make random mouse moves. Everything is taken into account, keystrokes, clicks, mouse pointer location, and every event's microsecond timestamp. Along with several system random sources (such as /dev/urandom if it's available). This results in an entropy buffer of, say, several kilobytes. I then apply multiple rounds of Sha3 hash on that. Or actually I take H=Sha3(entropybuffer) and then for each subsequent round I take H=Sha3(H⊕entropybuffer). Now either I generate a chaotic alphanumeric password from that, by base64-encoding the resulting hash and truncating at the desired length (after removing or forcing any non-alphanumeric characters as required). Or I generate a readable passphrase, for this I use the 2048 word dictionary which is also used by many Bitcoin wallets to generate backup phrase mnemonics. People put some clever thinking into that list (first 4 letters are always enough to identify a word, and no two words are very similar either literally or phonetically). Every word makes for 11 bits of space or entropy. [technical details here: github.com/bitcoin/bips/blob/master/bip-0039.mediawiki ] However in my experience, by far the hardest part with passwords is getting non-tech savvy people (we all have a friend or family member using his birthday as password) to use strong unique passwords as well 😬 Fortunately password managers have become much better over the years.

[@simonmultiverse6349]

​@@stromboli183 Yes, getting people to use strong passwords takes some persuading. With my password generator, I quickly found it became second nature to generate a new password when one expired. I think the diceware list of words has the same characteristic you mention: the first 3 or 4 letters are unique. One word list I downloaded included 676 two-letter "words", i.e. it included aa, ab, ac, ad..... az, ba, bb, bc, .... zx, zy, zz. That destroys the whole point, i.e. that they be ordinary words and easy to remember. I have also experimented with asking the user (me!) to type eight letters, but they must be all different. That's too easy to fool, i.e. all of the top row of the keyboard, therefore use the same letters all the time, so I ended up not using that.

[@cpndSimyule]

Solved the JFK murder at eighteen minutes three seconds @18:03

[@primodernious]

the best way to make a random number generator is a collision based simulation to model randomness. randomness is like stirring a soup. no matter how much you stirr, you never get the same arangement of particles in the soup twice.

[@insearchoftrance5214]

dumbcreaknuller yeah but you’re talking about true randomness. This is pseudorandomness

[@insearchoftrance5214]

Pseudo so it’s predictable.

[@davidjohnston4240]

Let me contradict your claims and introduce you to a one line nondeterminstic program in X86 assembly: "RdSeed EAX" . You're welcome.

[@DaveAckley]

And that's progress, at least as far as we trust NSA/Intel/GlobalFoundries/..

[@davidjohnston4240]

@@DaveAckley As far as I'm concerned, myself and a couple of other people designed the RNG in Intel chips. The NSA, the Government nor anyone else had any hand in the design. The entropy source and extractor design predated sp800-90B and the that spec is in part based on our extractor design. So your trust or lack thereof in the government has nothing to do with it. As for AMD's implementation, ask AMD.

[@hollythomason9013]

Couldn't you just start a page where you invited people to put in a number, and then the numbers would be random? They could be volunteers in an experiment, and they would be unable to see the output. There would need to be enough volunteers from different backgrounds and ages to produce a certain time period of random generations. The random numbers would be spit out for analysis, say once a month for evaluating its randomness. As long as the page was secure, the numbers would be truly random? It sounds too simple to be complicated.. If you stored the numbers for thousands of years, and only released in a set date in the future, where the numbers were spit out on that date, and there were enough numbers that had been generated to outlive those who lived in the year of official output, then for that moment in time the number generator would not be solved as long as the computers holding the list were under tight security?

[@DaveAckley]

holly thomason It's actually tough for people to be deliberately random (e.g., google "most random number"), so your analysis step would be important -- but it might be easier to look elsewhere for unpredictability. Thanks for the thoughts!

[@hollythomason9013]

Lol, you're welcome. I thought it was an interesting video. I'm interested in random number generators because in my personal opinion they can likely show proof of connected consciousness. I remember reading about how a random number generator somehow linked with internet usage was showing order right before September 11th and a few other events. I am a logical, rational person, but the idea that humans are so in synch that a random number is hard to deliberately come up with is an anomaly worth questioning. I can comprehend the change in the moment, but before implies the scary possibility that we have little control, because destiny is decided. I got to learn how the typical number generators work from your video, and some fun pseudoscientific experimentation ideas, lol. Plus now I know that if I get lucky and find a terribly made casino machine, I have a chance at cracking a code, lol.

[@gzitterspiller]

LCG can be made equally good as the mersenne... I could use 1mb of state with an lcg, or even just create a group or lcgs and get a k-dimensional, equally distributed, en with an astronomial huge period. This is a good introductory lecture but you bashed the lcgs too much lol, there are techniques to make them good.

[@reddot7756]

i need to talk to you

[@DaveAckley]

I try to check in here every week or so.

[@insearchoftrance5214]

Whoever created this method should burn in hell.

[@kishorshettykudal5249]

Can you tell nxt number on dragon tiger game plzzzzz

[@iliapopovich]

From a logical and philosophical point of view, there should be no random.

[@DaveAckley]

and therefore as a stranger give it welcome