random function

[mayarb]

hi,
Did someone familiar with random function that generate numbers between 0-1,000,000 ?

thanks,

maya

[imi]

If you don't care much about the quality of the random number, you can use rand() % 1000000 (use "% 1000001" if you want a both-inclusive range) . The distribution won't be good, but it suits simple needs.

For better quality random numbers, you have to use libraries. I use GNU's GMP library, but there are several easier-to-use. In the upcoming C++0x is more elaborated random number functionality included as well so you may try whether its already shipped and available for your environment.

Ciao, Imi.

[mayarb]

first of all, thank you very much imi.
i need my random function to be quality.
can you instruct me how can i use this library or easier one?

thanks,

maya

[AngelHoof]

Define "quality" random numbers for me? :P

I'd say the usual time-seeded random number generator is of the same quality as any other.

[jsmith]

I'd say the usual time-seeded random number generator is of the same quality as any other.

Very naive statement. Yes, seeding can affect the "quality" of the PRNs generated, but the actual
algorithm itself is at least equally important.

[imi]

i need my random function to be quality.

As AngelHoof said: What do you mean by "quality"? ;)

I'd sort random number generators into three levels.

First are the sort of "rand() % num" which is fast, simple and good for daily cases where you can tolerate some quirks in the random number distribution e.g. getting lower numbers more frequently (very slightly).


If you need statistical very good random numbers, but that don't have to withstand an intelligent attacker (means, it's ok if in theory someone mallicious user could break the random sequence, but it won't happen by accident), then the GMP library is probably good enough for you. It implements a couple of fast and very widespread algorithms (like Mersenne Twister), but which are not cryptographical strong. You can also take Wikipedia and try to implement an own Mersenne Twister which is not that hard. Wikipedia has good pseudo code for this (tip: The german wikipedia has a C-version of Mersenne Twister ;-).


The end of the road are things where you need to generate random numbers which must be secure against all kind of evil things, e.g. when you are creating certificates and other crypto stuff. Then you should look into crypto-libraries which usually have an interface of getting high-secure random numbers. (probably OpenSSL, OpenSSH and the sorts). I would recommend against trying to write an own version of these. They are terrible easy to do wrong.

Although some cryptographers will most probably disagree, it is also widely considered safe to use a good hash function repeadetly on an incrementing number and use it's output as random numbers. Java's SecureRandom does work like this. So if you already have a version of SHA-2 lying around and don't want to install complicated libraries, you could go for this approach.

Ciao, Imi.

[AngelHoof]

Very naive statement. Yes, seeding can affect the "quality" of the PRNs generated, but the actual
algorithm itself is at least equally important.

didn't know. Sorry.

Would you mind elaborating that?

[imi]

didn't know. Sorry.

Would you mind elaborating that?

One nice example is the "n-tupel equal distribution" property. This means, if you split your random sequence into n-tuples, then the sequence is equal distributed in the n-dimensional vector space.

For example if n = 2, then if you draw your random numbers into (x,y) - vectors, then these vectors should point in all possible places equal distributed, right? The C-buildin "rand" function is a "LCG generator" and it does this for n=2. But IIRC, not anymore if n>5. Regardless of what you feed to srand!

For example the Mersenne Twister guarantee equal distribution until n=623.


Another way of thinking about this:
How many continuous integers do I need from a random sequence to be able to predict the next integer better than just blind guessing? (just better guessing - not necessarily exact prediction)

rand(): less than 6.
Mersenne Twister: more than 623.
SHA-2: forget it..


There exist really strong pseudo number generators which are proven secure against some very common mathematical problems like factorizing big numbers*). This means in other words: If anyone could break them and guess any random number in the sequence better than blind guessing, then he could also break the mathematical problem (and get a nobel price and become Professor for Math at a university of his choice blabla). But these algorithms are usually a lot slower than "shuffeling around" - things like SHA-2, so seldomly used..


Note that I only spoke about algorithms, not about the seed. You were right in the point that the seed has to be good or else nothing in a pseudo-random number generator will help you making good numbers. But the seed is not even nearly all of the story.

Ciao, Imi.

*) An algorithm called "x² mod n" is secure against the Discrete Logarithm Problem, whereas GMR is secure against factorizing big numbers.