8 ms·
An RNG that runs in your brain
- aredox 3y agoSee also: the Solitaire cipher[0] (requires a deck of cards) Geomantic charts[1], which are... kinda binary encoding and shuffling? [0]https://en.wikipedia.org/wiki/Solitaire_%28cipher%29 https://en.wikipedia.org/wiki/Solitaire_%28cipher%29 [1]https://digitalambler.com/2020/05/08/how-to-construct-the-shield-chart-of-geomancy/ https://digitalambler.com/2020/05/08/how-to-construct-the-sh... Related : how to debias a biased coin[2] (aka. a Von Neumann extractor). It is not exactly the same (randomness extractor vs. PRNG), but there are similarities[3]. [2]https://carlos.bueno.org/2011/10/fair-coin.html https://carlos.bueno.org/2011/10/fair-coin.html [3]https://en.wikipedia.org/wiki/Randomness_extractor https://en.wikipedia.org/wiki/Randomness_extractor I want to take this opportunity to recommend Hillel's writing and depth of analysis (on top of the quirkiness of doing it in a weird lang). Compared to the equivalent answers on stackoverflow[4], there is just no comparison. [4]https://stackoverflow.com/questions/3919597/is-there-a-pseudo-random-number-generator-simple-enough-to-do-in-your-head https://stackoverflow.com/questions/3919597/is-there-a-pseud...
- camel-cdr 3y agoI stumbled over marsaglias usenet post before. One thing this article didn't discuss is choosing a seed, I think humans are better at coming up with a single random number than with a sequence of random numbers, but I still like to incorporate some "randomness" from the environment. You can e.g. add the count of something you don't know the count of until you count it to the seed. For example: floor tiles in a room, books with the color red in a book shelve, ... you can obviously also throw a coin or something like that, but that's a more involved action. If you are really dedicated, then you could mix in some environmental randomness after ever n iterations.
- aredox 3y agoA good seed under 60 is simply the second or minutes when you check the time.
- kqr 3y agoAnd as long as you don't need numbers at a high rate, you can just use the seed as the random number. I rarely need more than one in sequence so I just use the second hand. Come to think of it, I rarely need to choose between more than 10 alternatives so it's realistic to get at least two somewhat random alternatives per minute out of this idea.
- rjmunro 3y agoI just looked at my clock; it was 10:59. So I tried 5 + 9 * 6 = 5 + 54 = 59. That doesn't seem right. Then it was 00. That doesn't work either...
- ajb 3y agoIf we're talking about something what can be done by a human, then Othello counters or coins are each 1 bit. If not, then a hash of a new photo is probably simplest
- taneq 3y agoI like 4, that's pretty random.
- DeathArrow 3y agoWhy are people bad at coming up with random numbers?
- TonyTrapp 3y agoMathematical randomness is not exactly a skill required for survival. In fact, our ability to produce random numbers is so bad that our brains consider true randomness to not be random, as this blog post from Spotify shows: https://engineering.atspotify.com/2014/02/how-to-shuffle-songs/ https://engineering.atspotify.com/2014/02/how-to-shuffle-son...
- photonthug 3y agoDoesn't Spotify basically need to pay nonrandom royalties on stuff inside any given playlist such that streaming some content costs them more than others, while the users payment is constant? If that is true it defies belief that they would avoid cost optimization on their side and give users a truly random shuffle. Especially if they can argue that users don't know randomness when they see it
- TonyTrapp 3y agoI'm not sure that has anything to with the algorithm described in the blog post. I posted it because it's a popular, often-referenced example for this type of problem. The problem exists outside of Spotify, in any music player. And I believe that back when this was written, Spotify was paying the same amount of money for all streams, as it was way before the whole problem with people streaming white noise to launder money arose that they currently try to combat by essentially not paying artists with little exposure at all.
- Tainnor 3y agoSpotify's shuffle is hilariously bad though (to the point that there exist outside tools to pre-shuffle your playlists). I see that article more as an "excuse" for their bad engineering. I'm sure there are people who will get angry if they get two songs in a row from the same artist on a "random" playlist, but I'll much rather have that than the pseudo-random Spotify nonsense that will only play similar tracks next to each other or just ignore 90% of the playlist.
- defrost 3y ago> Marsaglia is most famous for the diehard suite of RNG tests, so he knows his stuff. Fame is relative, for my part Marsaglia is most famous for The Ziggurat Method for Generating Random Variables and numerous other PRNG delights .. the testsuite comes way down the list. * https://www.jstatsoft.org/article/view/v005i08 https://www.jstatsoft.org/article/view/v005i08 * https://en.wikipedia.org/wiki/Ziggurat_algorithm https://en.wikipedia.org/wiki/Ziggurat_algorithm Once upon a time I made a branchless generator of large blocks of random points on S2 (the surface of a unit sphere) for an astrophysics sim, it was a fun exercise
- camel-cdr 3y agoMarsaglia was also behind the MWC, SWB, xorshift and KISS PRNGs. Edit: removed a bit because I confused the polar with the ratio method
- gcr 3y agoOooo post it post it! Was it “generate a multivariate Gaussian distribution and then divide each point by its norm”?
- whyever 3y agoThat works for N dimensions, but for N=2 or 3 there are faster methods: For N=3, there is a method by Marsaglia: https://doi.org/10.1214/aoms/1177692644 https://doi.org/10.1214/aoms/1177692644 For N=2, there is a method by von Neumann: https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf All of these use rejection sampling, so they are not branchless.
- defrost 3y agoI'm staying vague for the sake of anybody noodling away at this, it's fun but not deep. It's a twofer, first there's a choice of algo to choose an unbiased unit vector (or point on sphere), then there's implementing it on a particular vector RISC architecture to avoid stutters from branch prediction gone awry - constant steady performance being desirable (in this and all the other parts of the larger program). "Branchless" decisions are possible; Compute D = decision = 0 or 1 as result (no branch, just arithmetic) Compute R = result = DA + (!D)B = result A OR result B depending on D with no jumps or decision penalties. It's an implementation hack and one dependant on architecture, some chips are fancy enough to pursue two branch in parallel and using the correct choice without have to suffer a time costly pipeline flush for path better not taken. DSP architectures have long pipes and consistent timing, complex arithmetic statements (once setup) take a single clock cycle; interate result vector = modulo scalar vector1 * input vector1 + modulo scaler vector2 * input vector2 type FFT "atomics" are a single clock .. you can push inputs once per clock and extract ouputs once per clock (with a delay of time to fill pipe).
- weinzierl 3y agoThis is about an interesting way to produce a pseudo random sequence. From the title I was expecting something a little different, more akin to Diceware [1], but without dice. Thinking of random numbers, but debiasing with John von Neumann's method sprung to my mind. [1] https://en.m.wikipedia.org/wiki/Diceware https://en.m.wikipedia.org/wiki/Diceware
- bsza 3y agoWe might be bad at generating uniform, independent random numbers, but I submit that we’re still capable of generating some true randomness. Perhaps take the best of both worlds and mix in new entropy at each step? Something like, take the previous 2-digit value, add a "random" digit and generate the next output from that?
- aquafox 3y agoI've memorized the first 130 digits of pi. Should be good enough for most tasks that require a human RNG.
- mark-r 3y agoSame here. There's that long string of 9's in a row, but that's well beyond 130 digits. I can recite pi faster than a person can make up random digits. Try it some time and see how fast you start to totally run out of randomness.
- basil-rash 3y agoTechnically any RNG should be very able to produce a king string of the same digit, and artificially filtering that out would be a very bad sign indeed.
- keepamovin 3y agoI've always been partial to Von Neumann's middle square method myself. https://en.wikipedia.org/wiki/Middle-square_method https://en.wikipedia.org/wiki/Middle-square_method
- robobro 3y agoHuh, I remember writing that python snippet for the page about 10 years ago. Nice to see it's still there!
- memming 3y agoI used this to shuffle my MTG deck when I was a kid.
- zanfr 3y agowhy just use the center digits all the time? just randomize it too
- keepamovin 3y agoCool idea. Implement it! and test out with Dieharder :) -- Haha :)
- alanbernstein 3y agoHere is my idea: pick a longish phrase of words, "at random". A song lyric, a book quote, etc. Count the number of words or the number of letters. Apply modulus if necessary. Repeat.
- andrewla 3y agoI often use the Fibonacci numbers mod 10 when I need to do this in my head. It isn't great -- odd numbers are twice as frequent (because mod 2 they're [1,1,0]) and you get sequences like [7,0,7,7], but easy to keep track of and the cycle is 60 elements long. The other one I use sometimes is the powers of 2 mod 100 and use the leading digit. This gives a cycle length of 20 with a flat distribution.
- librasteve 3y agocan try that in raku like this > (1, 1, * + * ... Inf)[^42].pick mod 10
- gilbetron 3y agoOne I use for random gaming needs, but requires two brains, if I want to emulate a dN die (d6, d10, d20, whatever) is I think of a number between 1 and N, and the other person does the same. Then add them together and mod by N. Works well enough, although you can get into game theory and the results aren't very random because we tend to pick certain numbers. Thinking about it, I wonder if both people picking multiple numbers and adding them all up mod N would improve things.
- deleted 3y ago[deleted]
- jetrink 3y ago> Thinking about it, I wonder if both people picking multiple numbers and adding them all up mod N would improve things. I bet that our bias against clustering and repetition when creating a pseudo-random list of numbers would mean that a list would be less random than an individual pick. As a simple example, if picking two numbers, people would probably be more likely to pick one even and one odd number than two even or odd numbers, since a mix of even and odd feels more authentically random, resulting in an excess of odd sums. As an alternative, what if each person created a short list and then blindly chose one number from the other person's list?
- RugnirViking 3y agoblindly picking from a shortish list of values then doing the addition and mod thing only seems better than the naive case of blindly picking from a list of 1 to N when we are talking about large values of N
- drdrek 3y agoWhen I want to be random enough I pick a large number than mod by another random number that is bigger then the max option. (mod again in the max number if needed) This seems unpredictable enough I've been unable to see any patterns in it. lets say you need to pick a number from 1 to 20, if you take 1235 and mod 22. mod is easy to do in your head as you can just subtract in steps until you get there. so 50 times 22 is 1100, we are left with 135. 5 * 22 is 110 so we are left with 25. 25 - 22 is 3. I picked 3 and I would be hard pressed to guess it would end up 3.
- sega_sai 3y agoGreat method! It's better though to choose prime numbers for mod X operation, that'll make biases less likely.
- chrisshroba 3y agoIn your example, 1 and 2 are twice as likely as any other number, because of the 22 possible results of n%22, 3 through 20 all only have one result that yields them, but 1 gets generated by 1 and 21, and 2 gets generated by 2 and 22. You could adapt your algorithm by adding "if the result is greater than the range of values you're picking from (i.e. 21 or 22 in your case), try again with a new number." >>> import collections, random, pprint >>> pprint.pprint( sorted( list( collections.Counter( [ ((random.randint(1,10000000) % 22) % 20) for x in range(10000000) ] ).items() ) ) ) [(0, 908920), (1, 908264), (2, 454167), (3, 456019), (4, 454551), (5, 455183), (6, 454127), (7, 454308), (8, 454939), (9, 454602), (10, 454963), (11, 453117), (12, 454046), (13, 453812), (14, 456243), (15, 455025), (16, 454101), (17, 455072), (18, 454409), (19, 454132)]
- drdrek 3y agoNice catch, I adopted your sugggested improvement: )
- bumbledraven 3y agoThis is the most in-depth analysis of Marsaglia's mental PRNG I've seen. A question, though. The author writes: > So what other numbers work? ... if n is a good multiplier, then the period of the orbit starting from 1 should be 10n − 2. > (2 3 6 11 15 18 23 27 38 39 42 50 51 62 66 71) > The last interesting number is 18. It has a respectable period of 178 and has every possible digit transition. The downside is that you have to learn the 18 times-table. This isn’t too bad: I internalized it with maybe 10 minutes of practice. Why is 18 the "last" interesting number? The largest number on the list, 71, has a period of 708 (10n − 2). Given that he is willing to memorize the first 10 multiples of a 2-digit number, why didn't he choose 71 over 18, which has a period of only 178? The 2-digit transitions for 71 are pretty evenly distributed: 7 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 8 7 7 7 7 7 7 7 7 7 7 7
- librasteve 3y agoin case you were wondering, raku DOES have built in proper random number generation: > (^6).roll #picks a random number from range 0..5
- zvr 3y agoIn case anyone is interested, the sequence of two-digits numbers is shown at https://imgur.com/a/sfxepRb https://imgur.com/a/sfxepRb.
- MagicMoonlight 3y agoMaybe we can’t pick random numbers because we’re just LLMs
- cmiller1 3y agoThe math as expressed in English in the original usenet post is ambiguous which confused me for a moment until I figured out what I was doing wrong. > Choose a 2-digit number, say 23, your “seed”. > Form a new 2-digit number: the 10’s digit plus 6 times the units digit. Here's where the ambiguity is, I interpreted this as (tens_digit+6)*units_digit so I did (2+6)*3=24 > The example sequence is 23 –> 20 –> 02 –> 12 –> 13 –> 19 –> 55 –> 35 –> … 24 != 20 so I had to walk back and figure out that they in fact meant tens_digit+(6*units_digit)