· Portal  Help Search Members Calendar 
Welcome Guest ( Log In  Register )  Resend Validation Email 
Welcome to Dozensonline. We hope you enjoy your visit. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access memberonly sections, and use many memberonly features such as customizing your profile, and sending personal messages. Registration is simple, fast, and completely free. (You will be asked to confirm your email address before we sign you on.) Join our community! If you're already a member please log in to your account to access all of our features: 
Dan 
Posted: Nov 7 2014, 04:41 AM


Dozens Disciple Group: Members Posts: 1,463 Member No.: 19 Joined: 8August 05 
This topic is highly related to Optimal base for random guessing by humans, but I decided to create a new thread because I wanted to (1) focus on one particular algorithm, and (2) discuss "computerscale" parameters rather than just "humanscale" ones. The Linear Congruential Generator (LCG) is one of the most common algorithms for deterministic generation of "random" numbers. It is defined by (in Python syntax):
(The sequence is periodic, so technically the "for" statement should be "while True", but the sequence will be easier to analyze by treating it as finite.) Each value of the sequence is an integer between 0 (inclusive) and the modulus (exclusive). For dozenal counting, an obvious choice for the modulus is 12 (*10). This yields a sequence of singledigit numbers. The hard part is deciding on the multiplier and increment. Some choices are quite obviously bad. For example, the multiplier a=3 and increment c=3 (starting with a seed of 0) gives the sequence [3, 0, 3, 0, 3, 0, ...]. This is not only way too obvious of a pattern, but only uses two of the twelve possible values. The most basic desirable property of an LCG is to have a full period of m values, each used once per period. This ensures a uniform distribution of values. With m=12, there are only four possible combinations of parameters meeting this criterion:
But not of these sequences is "random enough" (a concept I'll more formally define in a later post). So, m=12 just isn't a good choice. So, let's try two dozenal digits. With m=144 (*100), there are 576 (*400) possible combinations of a and c to chose from. How do we choose? To be continued... 

Dan 
Posted: Nov 17 2014, 12:19 AM


Dozens Disciple Group: Members Posts: 1,463 Member No.: 19 Joined: 8August 05 
It's hard to find an example of a good random number generator, but it's easy to find an example of a bad one.
Let X_{i} = The day of the week of January 1, 2000+i (Sunday=0, ..., Saturday=6) This isn't an LCG, but it is periodic, with a period of n=400. Computing this "random" sequence over the full period gives:
The relative frequencies are close to the naivelyexpected 1/7 = 0.142 857 142 857..., deviating only because of a mathematical quirk of the Gregorian leapday adjustment. (On the Julian calendar, they'd be exactly 1/7.) To quantify this, define the disuniformity of a periodic PRNG as the sum of (actual  expected relative frequency)^2 over a whole number of full periods. (Note that this is similar to the chisquared test statistic, but is independent of the number of periods taken.) So, for this particular "random" number generator, the disuniformity is 2*(0.141/7)^2 + 2*(0.1425  1/7)^2 + 3*(0.1451/7)^2 = 17/560000 = 0.0000303 571428 571428... Again, this is close to uniform, and would be a passable PRNG if onedimensional uniformity were the only criterion. But random numbers aren't always used one at a time; they're often used in pairs. For example, the roll of a pair of dice in a board game, or the generation of random points in a plane. In theory, taking two random numbers from the range 06 gives 49 possible results. But this particular PRNG makes only 14 of them possible:
This is because for all 7 possible days a year can start on, there are only 2 possibilities for what day the next year can start on, depending on whether the year is a leap year or not. The disuniformity of this PRNG applied to pairs of values works out to 12646433/192080000 = 0.06583940545605997. 

Dan 
Posted: Mar 17 2016, 02:56 AM

Dozens Disciple Group: Members Posts: 1,463 Member No.: 19 Joined: 8August 05 
For a generalpurpose randomnumber generator, we can't assume that the range will be the same as the modulus. Sometimes, we'll want to flip a (2sided) coin. Sometimes, we'll want to roll a 6sided die. Sometimes, we'll want to draw a card from a deck of 52.
In computer programming, there are two main ways of generating a range(k) random number from a range(m) generator. One is the Cstyle way, rand() % k. But this is a bad approach, especially in combination with the LCG method. The other is the BASIC way, INT(RND() * k), where RND is a function that returns a floatingpoint number between 0 (inclusive) and 1 (exclusive). We can convert an integer in range(m) to such a number simply by dividing by m. So, given a generator that returns a random number r in range(m), we can scale it to range(k) by doing INT(k * r / m). If we use a floored integer division operator (like Python's //), then we can simply write k * r // m and avoid troublesome floatingpoint arithmetic altogether. This still gives "subtly nonuniform" results, but at least it avoids the systematic bias towards smaller numbers that rand() % k has when k is not a divisor of m. 
Dan 
Posted: Mar 17 2016, 03:41 AM

Dozens Disciple Group: Members Posts: 1,463 Member No.: 19 Joined: 8August 05 
As illustrated by my second post in this thread, it's not enough for individual "random" numbers to be uniformly distributed. We also need sequences of random numbers to be uniformly distributed as much as possible.
But which sequences? We can not reasonably expect, for example, pairs of numbers from range(144) to be uniformly distributed for the 20 736 possible values, if our generator is to have only 144 possible states. But we can expect pairs of numbers from range(12) to be uniformlydistributed. Or for any factor of 12. For other numbers less than 12, we can't ensure exact uniformity, but we can strive to minimize the disuniformity (as defined above). By similar reasoning, we should have the 125 possible triples of numbers from range(5) be as uniformly distributed as possible. (5 being the floor of the cube root of 144). And for quadruples from range(3) and 5to7tuples from range(2). 
Dan 
Posted: Mar 20 2016, 03:11 AM

Dozens Disciple Group: Members Posts: 1,463 Member No.: 19 Joined: 8August 05 
Another common use case of random numbers is shuffling a deck of cards. The standard algorithm for this is the Fisherâ€“Yates shuffle, which for a deck of n cards requires n1 random integers: the first from range(n), the second from range(n1), etc., down to range(2). Given an ideal random number generator, all n! permutations should be possible.
Because 6!=720 but our proposed PRNG has only 144 possible states, there will be unreachable permutations of 6 or more cards. So let's evaluate the shuffles of 5 cards or less. We can ignore the degenerate cases of "shuffling" 1 card (which is a noop) or 2 cards (which is equivalent to a coin toss). 
jrus 
Posted: Mar 20 2016, 11:43 PM

Regular Group: Members Posts: 195 Member No.: 1,156 Joined: 23October 15 
Forget Linear Congruential Generators. Just use http://www.pcgrandom.org :)

Dan 
Posted: Mar 22 2016, 12:23 AM


Dozens Disciple Group: Members Posts: 1,463 Member No.: 19 Joined: 8August 05 
Nice simple algorithm. Looks like an enhanced version of Xorshift. I'll have to try it the next time I do a Monte Carlo simulation. But this thread was supposed to be about humangenerated random numbers. Bitshifts and XOR may be fast for a computer, but not so much for pencilandpaper (unless you're already using a poweroftwo base). 

jrus 
Posted: Mar 23 2016, 03:12 AM

Regular Group: Members Posts: 195 Member No.: 1,156 Joined: 23October 15 
Do you have some context where you need to generate random basetwelve numbers by hand, or is this just a fun curiosity?

Dan 
Posted: Mar 23 2016, 03:13 AM


Dozens Disciple Group: Members Posts: 1,463 Member No.: 19 Joined: 8August 05 
In summary, the tests I have proposed for a 144state random number generator are:
So, the question is: Is there any combination of multiplier and increment that passes all of these tests? 

Dan 
Posted: Apr 12 2016, 02:39 AM


Dozens Disciple Group: Members Posts: 1,463 Member No.: 19 Joined: 8August 05 
The answer turns out to be "no". So the question is: How close can we get?
To be continued... 

Piotr 
Posted: Dec 27 2016, 12:07 PM

Unregistered 
The problem is that 144 is very composite, so using LCG will make small cycles after doing the result mod divisor. For example all LCGs that use mod even either have all results odd or alternate odd and even. A good LCG can be done by using a mod of 2147483647 (prime) and multiplying by 16807 (no adding). It will make an uniformly random generator from 1 to 2147483646. Primes near powers of 2 are most convenient (3, 7, 17, 31, 127, 257, 8191, 65537, ...)

