how to produce a 6 bit random integer

[wang miao]

how to produce a 6 bit random integer. i means how to control the bits
e.g.

213432,
312356,
,,,,,

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

main()
{
int i;
srand( (unsigned)time( NULL ) );

/* Display 10 numbers. */
for( i = 0; i < 10;i++ )
printf( " %6d\n", rand() );

printf("new line \n");

}

[galathaea]

6 bits:
rand() % 64

but 213423 is six digts? base 6? I'm sorry, but I don't quite understand... If you post a clarification, I would love to try to help!

[kuphryn]

Do you mean a six digits random number? Otherwise, use bit shift << operator. An integer is 32-bits in Windows.

Kuphryn

[vinodp]

-----------------------------------------------
how to produce a 6 bit random intege
----------------------------------------------------
Assuming u need 6 digit number

The rand functions returns a number between 0 to RAND_MAX
By standard the RAND_MAX is implementation dependant
for Microsoft compiler this is 0x7fff
So therotically u can not get number bigger than 0x7fff in VC++ by random method

kuphryn provides shifting solution which is going to give u six digit number but the last digit always going to be same

Vinod

[anujseth]

If you are looking at a more reliable random stream of data, you could try the implementations in OpenSSL (http://www.openssl.org/) or Crypto++ (http://www.eskimo.com/~weidai/cryptlib.html).

[s. roelants]

i think for a 6 bit one galathaea's answer would be correct
for a 6 digit one you could try something like
1000*(rand()%1000)+(rand()%1000)

of course initializing first with srand

[cup]

Problem with rand() on some machines is that the range is from 0 to RAND_MAX. On a lot of compilers, this happens to be 32767. What is being done in the solution is to get two pseudo random 3 digit numbers and concatenate them.

[SolarFlare]

When I make random numbers that way, I find that the fewer digits you take, the more "random" they are. I once made a short little function that gives you a random number of n digits. Here's the gist of it (although I'm not sure it will compile because it will probably have typos here):

int randomnum(int a)/*a is the number of digits you want it to have*/
{
int b=0;
for(int c=0;c<a;c++)
{
b*=10;
b+=rand()%10;
}
return b;
}

You could simply use this with a=6.

[galathaea]

Solarflare is absolutely correct. Since RAND_MAX is not an exponent of ten (on any machine I've seen, but generally its at least not guaranteed to be), there will be some numbers that will have a greater likelihood of occuring than others.

For example: take RAND_MAX = 32767
taking % 1000 gives

33 possibilities to get #s 0 - 767
32 possibilities to get #s 768 - 999

but taking % 10 gives

3277 posibilities to get #s 0 - 7
3276 possibilities to get #s 8, 9

By choosing a smaller modulus to concatenate makes the likelihood ratios closer to 1:1, thus giving a better random character. 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...

[SolarFlare]

If you take rand()%(2 to some power less than 16) then you will get a truly random number. Even rand()%10 has some (ignorable) flaws because it's not a power of two. But it's easier to work with ;).
I suppose you could have

int randomnum(int a)/*a is the number of digits you want it to have*/
{
int b=0;
for(int c=0;c<a;c++)
{
b*=10;
b+=rand()%8;
b+=rand()%2;
}
return b;
}

and it would be even better.

[galathaea]

I don't know how to delicately do this... but there are a couple of flaws in SolarFlare's last post...
The rands will only give an integer from 0 to 8, not 0 to 9 (0-7 plus 0, 1) and also, the endpoints 0, 8 will have less of a chance (only one possibility each) of being picked than 1-7 (2 possible ways each). But I absolutely agree with the opinion that, for around the house type didn't get out of my pjs today random number generation, the %10 solution's side effects are ignorable.

[SolarFlare]

Originally posted by galathaea
I don't know how to delicately do this... but there are a couple of flaws in SolarFlare's last post...

NOOOO!!!!! now I must commit ritual suicide!!!! I'm a failure!!!!!
I mean, I just forgot to check over my logic ;)
Hmmm... I guess there's no easy way, then, to get a truly random decimal number unless you have something like this:
b=10;
while(b>=10)
{
b=rand()%16;
}
but it's not very efficient.

[SolarFlare]

Or, to increase the likelihood that it won't have to loop more than once:

do
{
d=rand()%512;
b=d%10;
}while(d>=510);

Now it will only repeat the loop once every 256 times you run it.

[KevinHall]

First off, using the line:

rand()%(maxval + 1)

to produce a random integer between 0 and maxval *generally* does not produce uniformly random results. As solarflare pointed out, for most implementations, if maxval is ((power of 2) - 1), then this will produce uniformly random results assuming rand() produces uniformly random results.

I have worked in the science and engineering fields for a while and do not trust most compilers' implementations of rand(). I personally recommend reading chapter 7 of Numerical Recipes for C. This has good algorithms for random numbers and some suggestions for producing the very results you wanted.

PDF versions of Numerical Recipes for C are available online at:
http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf.html

Hope this helps!

- Kevin

[AnthonyMai]

Using modular or divide operation to get random number of a specific range is extremely slow and gives you none-uniform distribution. So it is not recommended.

Here is a function that is fast, and gives you uniform distribution and is completely random:


int GetRand()
{
static int nPrevious = 0;

if (((nPrevious&0xff) ^ (nPrevious>>12)) == 0)
{
// Make sure we re-seed once in a random while.
srand(nPrevious ^ GetTickCount());
}
do {
int tmp = rand();
nPrevious = ((tmp<<5) - tmp) ^ (nPrevious>>1);
} while (nPrevious > 999999 || nPrevious < 100000);

return nPrevious;
}

[SolarFlare]

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.

[AnthonyMai]

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:


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;
}

[galathaea]

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

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!

[Philip Nicoletti]

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


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

[SolarFlare]

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?

[galathaea]

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

[AnthonyMai]

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.

[KevinHall]

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

[Kheun]

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.

[galathaea]

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!

[KevinHall]

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.

[Tom Frohman]

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\]

[Tom Frohman]

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

[Tom Frohman]

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.

[Yves M]

The discussion about randomness and the universe has been moved to this post (http://www.codeguru.com/forum/showthread.php?s=&threadid=218865)
It's an interesting discussion, but a bit too much off topic here ;)