how to produce a 6 bit random integer

Quote:

---

Originally posted by AnthonyMai
Here is a function that is fast, and gives you uniform distribution and is completely random:

---

You really shouldn't say that. Although it may be better in some respects, no code is completely random, which is one of the many difficulties in using random numbers. You are right to say that uniform distribution is key, but you want a function that will [list=1][*]Have uniform distribution[*]Emulate randomness as closely as possible[*]Do it as fast as possible[/list=1]
Remember, the random seed you choose has nothing to do with the function you to get the random number.

Quote:

---

You really shouldn't say that. Although it may be better in some respects, no code is completely random, which is one of the many difficulties in using random numbers. You are right to say that uniform distribution is key, but you want a function that will

---

No code is completely random mathematically, short of using a hardware random number generator. But my code is completely random from a practical point of view, since I re-seed it often, at un-predictable intervals, at un-predictable time, and use un-predictable seed.

Totally random sequence can be obtained by reseeding every time using something with maximum entropy, like the CPU clock cycle count. For example this random sequence will be completely untraceable and it is also fast:

Code:

---

int GetRand()
{
    static  int nPrevious = 0;

    do {
        _asm {
            rdtsc
            xor    eax, nPrevious
            mov    cl, al
            ror    eax, cl
            xor    eax, edx
            and    eax, 001fffffh
            xor    eax, nPrevious
            shr    eax, 1
            mov    nPrevious, eax
        }
    } while (nPrevious > 999999 || nPrevious < 100000);

    return nPrevious;
}

---

How many post's we have given to a thread that we still haven't received any clarification on the original intent?

Now, Anthony's post seems to be a good option, but I can't tell just by looking at it that it is truly uniform (I'll run a standard battery tests here shortly to see). However, I agree that it shouldn't be called truly random, and I am curious as to why it would be faster than the previous implementations, as rand() itself on my compiler (VC++ 6.0) and many others I have worked on is implemented by modular multiplication, so the same time consuming function is being performed. If my memory serves me (in Iron Chef fashion) someone said previously

Quote:

---

Of course, the best way is to just exclude the numbers from RAND_MAX down to RAND_MAX - RAND_MAX % N (N = 10, 1000, etc) as contributing to the asymmetry by taking another rand if such occurs (repeat as necessary). Then, its a tradeoff between rand returns to exclude and number of calls of rand to concatenate...

---

but I would qualify that with the fact that a mod multiplying algorithm won't give good randomness for use in higher dimension vector calculations because of the decomposition dependencies of the operation, so if its needed, use a different library's pseudorandom.

I'm still curious, though, whether the OP just wanted 6 bits...
Wouldn't that be funny!

Does anyone have any experience/thoughts on
the Mersenne Twister ?


http://www.math.keio.ac.jp/~matumoto/emt.html

Quote:

---

From the above site:
It is proved that the period is 2^19937-1, and 623-dimensional equidistribution property is assured

---

Hmmm... sounds fancy... that means it must be good, right?

Some runs on a simple mean test for Mai's method gave me
mean 543372.25
mean 542917.05
mean 542035.85
mean 543922.90
mean 543594.95
mean 542931.60
mean 542343.10
mean 543064.20
mean 542116.10
mean 542726.35
mean 543347.50
mean 541208.30
mean 542728.65
mean 542901.30
mean 542912.30
where the decimal rounding was done by my display choice. So, it appears there may be a slight tendency in the algorithm to give smaller numbers (as the expected mean is 550000), and at this point, my simple standard deviation algorithm was showing a discrepancy too high for it to calculate. So I would ask Mai, where did you get your example? Is it modified from some source? Because I don't think it is truly uniform at this point. My tests were on independent trials from 10 million points (put into an array of results) each run, so I think something may be off here.

As to the Mersenne Twister, I checked into once for my company, but since we were interested in cryptographically secure pseudo random number generators, I didn't pursue this option. However, it does seem to have many nice properties (more than many of the competing algorithms!) for scientific simulations...

rand() is slow because it uses integer multiplication, which is slow.

If you use modular calculation, which is division, it is even much more slower than multiplication.

To scramble bits fast, you should use only bit shifts, bit rotates and addition, subtraction and xor operations only.

My code is highly random because for each iteration the cpu clock count is introduced, which carries quite a bit of entropy. Also I rotate bits not by a fixed cousntant, but rather by a random number.

I will look at the average deviation claim and comment next.

Correct me if I'm wrong AnthonyMai, but your code calls rand() atleast once for each random number. If rand() is slow, so will your code be slow.

galathaea, I know the simple test you ran isn't that difficult to write, but I was wondering if there was a random generator test suite out there. I have never found one -- granted I haven't looked very hard.

- Kevin

Hi. Anybody have looked into this API?

CryptGenRandom().

It is stated that the data produced by this function is cryptographically random. It is far more random than the data generated by the typical random number generator such as the one shipped with your C compiler.

However, it is only available on MS system.

Sorry, I was trying to reply earlier, but with all the server probs... anyway check out DIEHARD for a good battery of tests. Its what I use at work. For the test I did earlier, though, I just coded it up because the numbers did not fill a byte boundary (100000 to 999999) and so it would have been much more difficult to output a binary file that would have been meaningful. There is also a standard battery of tests (I think from NIST, but I'll have to check my notes tomorrow) for certification as a good pseudo random number generator.

I wish I had something to say about the API, but after the (confirmed) rumours about Microsoft's communications with NSA, even if it had nothing to do with this (no one I know knows for sure) I stay away from Microsofts API. Plus, it is important to realize that cryptographic security is a separate issue from good random character...

Anyways, really enjoying the discussion so far!

Thanks galathaea, I'll have to check those out.

FYI, I wrote a program to profile MSVC's rand() function, a random class I've been using for a while based on Numerical Recipes' ran2 function, and the Mersenne Twister all in speed-optimized, release builds.

Anyway, the numerical recipes code was only 10% slower than MSVC's rand() and the Mersenne Twister was 450% slower than MSVC's rand(). Granted, ran2() only has a period on the order of 2^18, but for what I do, it works great.

I think Anthony's generator is interesting. I've never seen it before.

I generated 100000 values using the first routine. And produced a point plot of x(i) vs x(i+1). I don't know if the jpg of this plot is succesfully attached to this post but it is interesting. It produces a diagonal line of gaps. In a sense it is autocorrelated.
Take a look at the attached JPG.

I tried this with the second routine and didn't see the gaps but you can see a lattice of values on the 2d plot that are more likely.

I think it deserves more study.

Tom

[CODE]
The program i used to test the routine
int main(int argc, char* argv[])
{
#define ELEMENT_COUNT 100000
FILE *ot;
int i;

int value1;
ot=fopen("random.out","w");
for(i=1;i<=ELEMENT_COUNT;i++)
{
value1=GetRand();
fprintf(ot,"%d %d \n",value1);
}

fclose(ot);
return 0;
}
[CODE\]

Sorry, the plot was too big. Lets try this again.

This is a plot of x(i) vs. x(i+1) i=1,3,5...49999
From the second GetRand() function. I don't know if it will show up in the distorted image but look at the diagonal pattern of values.

The discussion about randomness and the universe has been moved to this post
It's an interesting discussion, but a bit too much off topic here ;)