[Math] Generate random number based on a certain pattern and able to test against the pattern

pattern recognitionrandom

I have very little idea about random numbers and patterns, so I am not sure whether this is actually possible or not.

I want to generate random numbers, that will follow a fixed pattern (perhaps this itself breaks the definition of 'randomness'?). Say for example, a number whose every alternate digit will be even/odd, like 123456. For such a pattern, say of 30 digits, I want to generate random numbers. And when generated, I want to verify the number against the pattern (so here I will verify whether the random number generated has every alternate digit as odd/even, if so, then it succeeds the check)

Is there any way to develop a fairly complicated (and if I may, notoriously difficult to find out by anybody else) pattern and generate random numbers in that pattern?

Best Answer

Yes, the problem is much more with defining a pattern you like than with the random numbers. Taking your alternate even/odd example, each digit has five choices, so you can just generate a random number from $0$ through $4$ for each digit. If the digit is supposed to be an even one, double it. If the digit is supposed to be odd, double it and add $1$. Now you have a number with digits alternating as desired that is randomly chosen among all the numbers that satisfy your criterion.

The problem you are seeing is that this is too easy a pattern for someone to identify. Choosing an appropriately hard pattern is not really a mathematical problem. You might just pick some ten digit prime number $p$ and have your pattern be multiples of that. When you want a random number thirty digits long, generate a random between $0$ and $10^{30}/p$, multiply by $p$ and report the result. Again your reported number will be random in the acceptable space. Clearly there are many patterns that can be defined.

Related Solutions

Random – Pseudo Random Number Generation on the GPU

I queried fellow students and they brought my attention to this paper: https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch37.html

Since the paper is quite long and might not be online forever below is the general idea:

Linear Congruent Generators are ideal for use on the GPU because they are simple and do not require much state (only the previously generated number). but they are not 'random enough' for, for example, Monte Carlo based simulation. A generator like a Mersenne Twister would be better but requires way too much state to be stored.

The solution proposed by the paper is combining several LCGs using a combined Tausworthe Generator (as used by the Mersenne Twister) this guarantees a much better randomness without having to store as much state as the Mersenne Twister. The final algorithm looks like this:

struct RandomResult
{
    uint4 state;
    float value;
};

uint TausStep(uint z, int S1, int S2, int S3, uint M)
{
    uint b = (((z << S1) ^ z) >> S2);
    return (((z & M) << S3) ^ b);    
}

uint LCGStep(uint z, uint A, uint C)
{
    return (A * z + C);    
}

RandomResult Random(uint4 state)
{
    state.x = TausStep(state.x, 13, 19, 12, 4294967294);
    state.y = TausStep(state.y, 2, 25, 4, 4294967288);
    state.z = TausStep(state.z, 3, 11, 17, 4294967280);
    state.w = LCGStep(state.w, 1664525, 1013904223);

    RandomResult result;
    result.state = state;
    result.value = 2.3283064365387e-10 * (state.x ^ state.y ^ state.z ^ state.w);

    return result;
}

Note that the initial seed values for state should be larger than 128! (For background information reed the paper) and that you should fill the seed with 4 good random numbers from the CPU + four values unique for that pixel to get a nice result.

Best Answer

Related Solutions

Random – Pseudo Random Number Generation on the GPU

Related Question