5 ms·
It's an interesting area, but a quick scan of the generators section makes it look quite inaccessible. I actually have a pseudorandom number generator as my in
by martythemaniak 6y ago
It's an interesting area, but a quick scan of the generators section makes it look quite inaccessible.
I actually have a pseudorandom number generator as my interview question and it's quite simple. I have a slightly simplified asci-art version of it that use essentially a variation of Wolfram's Rule 30.
Coding it is easy, requiring no algorithms or data structures, just some iteration, if statements and substring look ups. At first some are annoyed at what looks like a useless, made up toy project, but then I tell them this was actually a part of Mathematica in the early versions and we start discussing how you'd turn that output into a useful pseudorandom number generating function with a seed, acceptable performance etc. Quite a few end up happy with the problem at the end.
- pastage 6y agoI've looked around abit and pseudorandomness is not an accessible subject, if you have any links for something then please share. I can not judge this, at least it seems thorough, but too much math but it feels like it at least is a good starting point.
- martythemaniak 6y agoWolfram has a lot of talks, etc but this interview seems like a decent intro: https://www.youtube.com/watch?v=VguG_y05Xe8 https://www.youtube.com/watch?v=VguG_y05Xe8 Let's implement Rule30, which is quite beautiful and he talks about it a lot: https://mathworld.wolfram.com/Rule30.html https://mathworld.wolfram.com/Rule30.html https://jsfiddle.net/zL6pgyo4/1/ https://jsfiddle.net/zL6pgyo4/1/ We start with a simple seed and apply a set of simple rules over and over again. If you scroll past the first few lines of the output, you start to get very complicated patters. If you try other rules, you usually don't see any patterns or anything interesting, rule30 is kind of rare. Wolfram's done some analysis and he says if you go down the central line (assuming the width keep on growing, which is not the case in my fiddle), and take each "bit" (which I represent as "-" and "X") and plot it, you'll find they're fairly uniformly distributed. Once we have these stream of uniformly distributed bits, you can convert it a string of integers or whatever you need. For the math behind whether something is random or not, you can look up the "chi squared test", but I think the intuition is way simpler - random things are uniformly distributed. Random things look like white noise on old TVs. If you plot the frequency of their occurrence, each one should be just as likely as every other thing. In our example, if you take the output, flatten it into a string, segment it into chunks of 8 (representing a byte), then count the occurrence of each byte ("--------", "-------X", "------X-") they should have the same number of occurrences.
- price 6y agoHere's an alternative exposition (by Goldreich) recommended in this one's introduction: http://www.wisdom.weizmann.ac.il/~oded/prg-primer.html http://www.wisdom.weizmann.ac.il/~oded/prg-primer.html It ends up getting pretty mathematical too, but it seems like Goldreich takes more time up front to really get into the concepts at a philosophical level before proceeding to the math - so you might enjoy reading the introduction, if nothing else.
- Ar-Curunir 6y agoThis is a mathematical treatment of pseudorandomness, intended to prove guarantees against specific classes of algorithms . It’s not concerned with “practical” PRGs which don’t provide guarantees about the quality of their randomness