Randomness is calculated - Linear Congruential Generators Explained
Vložit
- čas přidán 16. 06. 2021
- In my last video I began my exploration into Perlin Noise because of Minecraft and my unhealthy need to do something with graphics. Well, I completely abandoned that this week and did nothing but math.
The Linear Congruential Generator, often referred to as LCG, is an equation that computers use in order to create "random" numbers. The result of this equation is calculated often by using prime numbers and a mathematical operator called a modulo. The resulting number from the LCG is our "random" number. This number is then fed back into the equation creating a chain of random numbers until the equation ultimately loop. Since the 50's mathematicians have been searching for the right combination of numbers to create the ultimate LCG...this is not that.
There are a couple resources that might help you on your journey if you are attempting to write your own LCG or join the fight to create the best LCG you can.
Good Luck.
"Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure" - by Pierre L'ecuyer:
www.ams.org/journals/mcom/199...
Linear Congruential Generator Wiki:
en.wikipedia.org/wiki/Linear_...
"Random Number Generators" (Hull-Dobell Theorem) - by Hull, T.E. and A.R. Dobell:
dspace.library.uvic.ca/bitstr...
My Last Video on Perlin Noise:
• [Explained] Perlin Noi...
![[Explained] Perlin Noise and Unity](http://i.ytimg.com/vi/BO7x58NwGaU/mqdefault.jpg)
![[Explained] Perlin Noise and Unity](/img/tr.png)
I wasnt expecting such a tastefully comedic and thorough explanation. I tip my hat you my good sir
Beard, jokes, no tie, glasses,... Except for the beer; my kind of teacher. I wish you were in front of the class in sat in 50 years ago.
I loved this video! It was super useful for me to understand LCG and your video style is through the roof! I see you haven't made videos recently but I would absolutely watch more of your stuff
Thank you for the love! Not that I don't want to make videos, just haven't figured out how to navigate the coding and tutorial space with AI coming around. Got to decide if there is still a need for videos like these.
This is so awesome! I have never heard of LCGs until class today! And I got a far better understanding
By far the best video on LCG in YT. Top notch editing a bonus !
This is great and fun explanation of this algorithm, thanks a lot man
Great explanation. Thanks for the links.
This is just absolutely awesome!
Great video!! I love your editing. Keep it up! :)
TYSM!
This video was very nicely edit and informational :] thanks a lot
@6:11. I appreciate the time and effort you put into this. It really does take a long time to direct and edit a video.
you smoked this video! Please keep creating content like this
Thank youi!
This is so goood! Thank you!
Came for the knowledge, stayed for the fun and aesthetics (and knowledge ofc)! Fun video, edits and the script! Keep going dude, your audience is niche but once the YT nerds find you, they will appreciate the effort (I hope). Fingers crossed!
Thank you! I’m enjoying making the videos as a journal I can look back on, so I don’t see myself stopping anytime soon! Though I have been really absorbed in a lot of other things the past few weeks so new videos are kinda stuck in the editing process…
And I don’t think the topic is too niche, at least I don’t think. People like Michael Reeves and Code Bullet can garnish millions of views with every video, I just gotta get my videos up to their standards.
thanks for this great content I hope you get more subscribers
1 at a time. Thank you!
To fix your code, you need to store the results in a set, rather than a list. The contains() method of a set is way faster than that of a list. Your runtime is a parabola, you can get it down to a straight line. In other words, your code is O(N^2), but you can get it down to O(N).
Interesting. I’ve never worried about Big O notation before because I’ve always been someone that has programmed for fun instead of work.
@@BearTheCoder Great video! Just came to add to this comment. Big O improvements aside, a program of N print statements is still incredibly more expensive than N arithmetic/logic operations. Your program is as slow as it is largely because the CPU is constantly having to yield for I/O.
Goodddam it ur awesome bro , keep it up
ur videos are soo good GL
Here’s another comment: I love the title of your video. It’s one of two reasons I picked yours over the other video which showed up in spot 1 when I searched for “linear congruential generator”. The second reason is because you use colorful illustrations in your thumbnail. The other video looked dry.
woah tommorow is my crypto exam and this helps me lot mate thankz:D
Great vid mate! Commenting for the youtube algorithm
Thank for that! Appreciate the love!
How does number 8 comes after 5,7,7 in linear method please explain.
what is the difference in between using the random numbers generated by the libraries in the differnets programing languages instead of using the congruential generator? which one is better and why ?.
en.m.wikipedia.org/wiki/List_of_random_number_generators
“Randomness” is an arbitrary and unmeasurable value so it’s impossible to determine quality or difference based on that value. But, the period, or looping period is measurable and that is the primary difference.
@@BearTheCoder thank you for your answer .
Nice ! you helped me thank you
Glad I could help!
Finally understood 👌🤞🤞
The second "ridiculous" method is also found in _The Art of Programming_ The general idea is to use a modulus that is a large prime or a large power of 2. If you use a large prime, 'c' should be zero and 'a' should be a primitive root of that prime. It's a very interesting topic. But I suspect I have gone deeper into it than you have. And that's okay. Most people just want a black box that spits out "random" numbers and are more than happy to use library routines to do it.
Also commenting for the algorithm. This was a fun watch ^_^
Thank you!!
great vid
Thanks so much!
How does one calculate the efficiency of the sequence produced by an LCG? In the video the example was about 40%. How does one derive that?
So, LCGs have a maximum amount of number sit can produce because you are using a modulo. If the modulo is 10 the maximum amount of random numbers it can produce is 10. But LCGs tend to loop. So if an LCG produces a 6 then 4 then 3 then 7 then 6, you only got 4 numbers out of the possible 10, so 40% efficiency.
@@BearTheCoder Ah, I see. Thank you both for the explanation and the video :)
Hey Beavis, what if every number was 69?
Hehe yea, that'd be cool!
nice likes in this video
😁😁😁
Noyce.
I didn’t get the 🌈 flag joke, so I checked the KnowYourMeme database.