Is there a pseudo-random number generator simple enough to do in your head?

Question

Are there are any pseudo-random number generators that are easy enough to do with mental arithmetic, or mental arithmetic plus counting on your fingers. Obviously this limits to fairly simple math - it needs to be something someone of average mathematical ability can do, or maybe average ability for a programmer, not a math prodigy.

The simplest I have found is the Middle square method, but not only is it known to be a poor source of randomness, it still looks too complex to do without pencil and paper.

If the only way to do this is by limiting the range, like maybe it only can output 8 bit numbers, that is fine. I suspect one of the standard PRNG algorithms would be simple enough in an 8 bit version, but I don't know enough to simplify any of them from the 32 bit version to an 8 bit version. (All the ones I looked at depend on specially picked seed numbers that are different depending how many bits you are working with, and usually only 32 and 64 bit examples are given.)

Solution 1

A linear feedback shift register is pretty simple, as long as you're comfortable with thinking in binary (or maybe hex, since it's easy to map between the two).

A more complex one is Xorshift, but if you know your bitwise operations, it should be quite possible to work with as well.

Solution 2

Pseudo-random (according to Dilbert):

Solution 3

In your head you can do "semantic" random number generation :-)

Like taking random word, and calculating some metric out of it, repeat until you'll get number with reasonable length.

For example, word "exercise" might get converted to 10100101b (you can see my conversion idea here).

Solution 4

How about Blum Blum Shub, but with prime numbers too small for secure use? Used securely it's slow, but it involves operations that we're used to dealing with, so you might be able to get to a manageable speed without too much practice, maybe with M = 437 or moderately bigger.

I doubt whether anything I could do in my head will be secure, anyway. I just can't remember big enough numbers to work without mistakes on a reasonably-sized state.

You can easily do a 10 bit LFSR on your fingers, if you have decent tendons ;-)

Not a direct answer, but depending why you're asking you might be interested in Solitaire, which generates a keystream (i.e. a pseudo-random sequence) using a deck of cards. Can't be done in your head, but doesn't require pencil and paper.

Solution 5

This is pretty basic and should fit in most people's heads:

1. Start with a three-digit seed number (finding a suitable seed may be a harder problem).
2. Multiply it by nine.
3. Separate the fourth digit from the bottom three and add the two numbers together for a new three-digit number.
4. Write down these digits. To help disguise the pattern you might write down just one or two of the digits.
5. Repeat 2-4 as required.

So long as you don't start with zero, this will iterate through a period of 4500 results. The output doesn't "look" random, but it's in decimal and even true random results fail to look random, which is why humans suck at this task.

I might try to hack up a program to convert it to binary in an unbiased way to test it.

Alternative configurations:

• three digits and multiply by 3
• four digits and multiply by 6
• five digits and multiply by 2

View more solutions