3 ms·

An idea I shared on "Can you behave randomly? (1998)" (https://news.ycombinator.com/item?id=11753194 https://news.ycombinator.com/item?id=11753194) seems releva

An idea I shared on "Can you behave randomly? (1998)" (https://news.ycombinator.com/item?id=11753194 https://news.ycombinator.com/item?id=11753194) seems relevant here. The keypresses I entered were not predictable by the Oracle. I generated the keypresses by first picking an arbitrary integer in [0,59]. I then (using simple mental arithmetic) used that integer to seed a PRNG by George Marsaglia [1] to generate a stream of pseudo-random decimal digits. For each digit, if it was in [0,7], then I took the 3-low order bits of its binary representation, in order from least significant to most significant bit (0=f, 1=d). If the digit was 8 or 9, I discarded it. The PRNG I used has period 59, and only 20% of the output digits would have to be discarded. Therefore one could use this approach to generate up to 141 pseudo-random bits. [1] Marsaglia, George. "How to generate random number sequences (in your head)" https://groups.google.com/d/msg/sci.math/6BIYd0cafQo/Ucipn_5T_TMJ https://groups.google.com/d/msg/sci.math/6BIYd0cafQo/Ucipn_5...)

avip 10y ago
Can't you invoke a simpler random generator? Let's say primes % 4 ?
- bumbledraven 10y ago
  Do you have any references on the statistical properties of the primes % 4 sequence? When converted to coin flips, primes % 4 fails the statistical randomness tests at http://faculty.rhodes.edu/wetzel/random/mainbody.html http://faculty.rhodes.edu/wetzel/random/mainbody.html See results at http://imgur.com/iaHBNNr http://imgur.com/iaHBNNr ("Your nth attempt" is primes % 4, "Coin nth attempt" is the Marsaglia PRNG). Note that primes % 4 has too many runs, its prob(H given H) is too low, and its prob(H given T) is too high.
  - avip 10y ago
    It was meant to be read a question, not statement ("are you aware of a simpler PRNG I could pull from the top of my head, using basic arithmetics?"). Maybe a collatz sequence? You're right, apparently it's called Chebyshev's bias.
    - bumbledraven 10y ago
      I'm not aware of a simpler PRNG. It took me quite a search to find Marsaglia's.
kqr 10y ago
I really like this crude PRNG algorithm. Now I also have a reason to learn the multiplication table. Or at least the sixths column.

avip 10y ago

Can't you invoke a simpler random generator? Let's say primes % 4 ?

bumbledraven 10y ago
Do you have any references on the statistical properties of the primes % 4 sequence? When converted to coin flips, primes % 4 fails the statistical randomness tests at http://faculty.rhodes.edu/wetzel/random/mainbody.html http://faculty.rhodes.edu/wetzel/random/mainbody.html See results at http://imgur.com/iaHBNNr http://imgur.com/iaHBNNr ("Your nth attempt" is primes % 4, "Coin nth attempt" is the Marsaglia PRNG). Note that primes % 4 has too many runs, its prob(H given H) is too low, and its prob(H given T) is too high.
- avip 10y ago
  It was meant to be read a question, not statement ("are you aware of a simpler PRNG I could pull from the top of my head, using basic arithmetics?"). Maybe a collatz sequence? You're right, apparently it's called Chebyshev's bias.
  - bumbledraven 10y ago
    I'm not aware of a simpler PRNG. It took me quite a search to find Marsaglia's.

kqr 10y ago

I really like this crude PRNG algorithm. Now I also have a reason to learn the multiplication table. Or at least the sixths column.