Randomness is calculated - Linear Congruential Generators Explained
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/jo...
Linear Congruential Generator Wiki:
en.wikipedia.o...
"Random Number Generators" (Hull-Dobell Theorem) - by Hull, T.E. and A.R. Dobell:
dspace.library...
My Last Video on Perlin Noise:
• [Explained] Perlin Noi...
Пікірлер: 49
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
@BearTheCoder
7 ай бұрын
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
This is great and fun explanation of this algorithm, thanks a lot man
By far the best video on LCG in YT. Top notch editing a bonus !
Great video!! I love your editing. Keep it up! :)
@BearTheCoder
2 жыл бұрын
TYSM!
you smoked this video! Please keep creating content like this
@BearTheCoder
Жыл бұрын
Thank youi!
amazing video man!
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).
@BearTheCoder
2 жыл бұрын
Interesting. I’ve never worried about Big O notation before because I’ve always been someone that has programmed for fun instead of work.
@ninjroidsolutions549
Жыл бұрын
@@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.
This video was very nicely edit and informational :] thanks a lot
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!
@BearTheCoder
2 жыл бұрын
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.
This is just absolutely awesome!
thanks for this great content I hope you get more subscribers
@BearTheCoder
Жыл бұрын
1 at a time. Thank you!
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 ?.
@BearTheCoder
Жыл бұрын
en.m.wikipedia.org/wiki/List_of_random_number_generators
@BearTheCoder
Жыл бұрын
“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.
@malvis8737
Жыл бұрын
@@BearTheCoder thank you for your answer .
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.
This is so goood! Thank you!
Great vid mate! Commenting for the youtube algorithm
@BearTheCoder
2 жыл бұрын
Thank for that! Appreciate the love!
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.
@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.
woah tommorow is my crypto exam and this helps me lot mate thankz:D
How does number 8 comes after 5,7,7 in linear method please explain.
Goodddam it ur awesome bro , keep it up ur videos are soo good GL
Also commenting for the algorithm. This was a fun watch ^_^
@BearTheCoder
2 жыл бұрын
Thank you!!
Nice ! you helped me thank you
@BearTheCoder
2 жыл бұрын
Glad I could help!
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?
@BearTheCoder
8 ай бұрын
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.
@JamesSarantidis
8 ай бұрын
@@BearTheCoder Ah, I see. Thank you both for the explanation and the video :)
Finally understood 👌🤞🤞
great vid
@BearTheCoder
2 жыл бұрын
Thanks so much!
Hey Beavis, what if every number was 69? Hehe yea, that'd be cool!
nice likes in this video
I didn’t get the 🌈 flag joke, so I checked the KnowYourMeme database.
Noyce.
😁😁😁