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.)

Answer 1

A comment points out that this is wrong. Months later I still haven't found the time to revisit how I came up with the magic numbers and where I went wrong, so I'm adding this note at the top in the interim.

---

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

Answer 2

Here is a very simple one that is based on a linear method:

1. Pick three number $a$, $b$, $n$ with $2<=a<n$ and $1<=b<n$ with $n$ being a prime. In this example, I'll use $a=83$, $b=52$, $n=101$.
2. Let $f(x) = (ax+b) (mod n)$.
3. Find the unique stationary point, which is the value $k$ such that $f(k)=k$. For the values of $a$, $b$, $n$ as above, the stationary point is $k=24$.
4. Recursively apply $f$ starting with a seed that is not the stationary point. You get a stream that outputs values from $0$ to $n-1$ except $k$. When the value $n-1$ is generated, write it down as $k$ instead.

For this example, starting with 0, we get a stream of 0, 52, 25, 6, 45, 50, 61, 65, 94, 77, 80, 26, 89, 66, 76, 98, 5, 63, 29, 35, 28, 53, 7, 27, 71, 87, 1, 34, 46, 32, 82, 91, 30, 17, 49, 79, 44, 68, 40, 39, 57, 36, 10, 74, 33, 64, 11, 56, 54, 90, 48, 97, 23, 42, 3, 99, 88, 84, 55, 72, 69, 22, 60, 83, 73, 51, 43, 86, 19, 13, 20, 96, 41, 21, 78, 62, 47, 14, 2, 16, 67, 58, 18, 31, 24, 70, 4, 81, 8, 9, 92, 12, 38, 75, 15, 85, 37, 93, 95, 59, which has a period of 100. A period of $n-1$ is guaranteed if $a$ is a primitive root of $n$, so there are many pairs of $(a, b)$ that gives a period of $n-1$.

Answer 3

I recommend a set of 23 functions

X = 0 Definition_0ne(X); .... Definition_TwentyThree(X);

What each one does can be as simple as (X^2), but given 1 value all 23 most provide unique results.

From here you build a sequencer , that will call all 23 in a given order based off any seed, so if I gave you "Jimmy" as a seed for example. You could accept that and covert it to some form of decimal, then multiply it by some known non repeating decimal that goes out 23 decimal spots ( this value can be made up on the spot )

Then it will call the function closest to the last 2 decimal values, and Everytime it has already been called it will attempt to call the 2nd closest above, followed by 2nd closest below, after 23 passes, all remaining will be sequenced in , in a predertermined order , highest to lowest will work fine, stopping at the point that at least half of the functions have been called , and X is very much psuedo random, after all functions remaining are called the class will return the final X value

This takes a computer like .000000001 seconds to do, a human about 15 minutes on paper.

Your 23 functions could be as simple as X+1 , to X+23 , return X, you will never be able to accurately predict without first do the math of each function, then run on decimal modifier , then redoing the math , over and over to find out which functions will get called , and what order the would get called in, and only the author would know this, given that 12 of the 23 of the functions will get called minimally, and 23 max , you shouldn't ever have to worry about anyone backwards engineering your code :)

Sure they can keep putting in the same seed, but that won't solve anything and in a game or application setting your seed will be amended with a piece of extra info generated from storage in most cases. I like to use touch sequences on Mobile for that extra data, is your last 3 initial contact points are always saved and added to what ever random seed you start with , on a computer if it's an application I used a pointer to some kind of memory that only gets allocated after the initiation of the application, and i don't know what to use html , but I am sure there is a way to get information that isnt random but isn't the same in every instance to amend to the seed, to make backward engineering much more difficult

Answer 4

If non deterministic algorithms are allowed, your eyes are in your head, so What about something like "the number of red objects in front of me plus the number of blue things modulo the number of green things plus the height of the tallest stack of things containing at least one thing with the letters g and uppercase A on it."

I'm sure there is a way to do this that would actually be fairly random.

Answer 5

The easiest way would be to generate several numbers that come to your head and then sum and mod 10 each of the digits. The more numbers you add, the more random and less biased it will be.

510932
689275
539108
======
628205

Answer 6

Yes I know of one that can possibly be done in your head , and if modified further can result in truly random numbers take a list of numbers , an ordered list of numbers in base ten cause that would be the easiest to calculate in. Add them up together , the keep only the ones digit place number of that resulting number and then place that on the end of the list and drop off the first digit , and then repeat , this will not produce true random numbers but random enough and depending on the size of the list of numbers that you choose to use , will eventually repeat but for a large initial list will not repeat for a sufficiently large amount of time.

for example if I used just 5 numbers in a list 12345 then the next list would be 2345 and the rightmost digit of 1+2+3+4+5ie 15 or 5 so the list would be 23455 now the one has dropped off and is not used anymore so the next sum adds up to 20 -1 (15+5 minus the one that dropped off) so the next list would be 34559 then 45596 then 55969 then 59694 now here we stop , because we have generated a full seeds worth of digits so initially we had 12345.

For the next seed we got 59694 , now there is a kind of a shortcut that you can also use once a full seed has been calculated, or the shortcut itself could be used, which is you take the last digit , multiply it by 2 and subtract the first digit doubling one digit is easily done in the head, the important thing is to remember all the other digits and their order in the sequence, this will at best though only produce pseudo - random numbers , with some long repeat times the larger the list of numbers that you use, but the initial list must be chosen with care, like for instance don't pick all zeroes as you list or you will have an endless stream of zeroes and well some sets of digits will produce longer repeat cycles than others (but maybe this should be done on paper provided you have a pencil or pen and a sheet of paper handy... :) hope this helps..(modified a bit this makes the start of a very good true random number generator) enjoy...

I hope this is better if not then tell me so :) (I was never very good in English ! :)

Answer 7

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.

Answer 8

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.

Answer 9

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).