Algorithm for Generating a Random Number

Algorithm for generating a random number

No your algorithm is not scalable. What I've done before is to issue numbers serially (+1 each time) and then pass them through an XOR operation to jumble the bits thus giving me a seemingly random numbers. Of course they aren't really random, but they look so to users eyes.

[Edit] Additional information

This algorithm's logic goes like this you use a known sequence to
generate unique numbers and then you deterministically manipulate them,
so they don't look serial anymore. The general solution is to use
some form of encryption, which in my case was an XOR flipflop, because
its as fast as it can get, and it fulfills the guarantee that numbers
will never collide.

However you can use other forms of encryption, if you want prefer even more
random looking numbers, over speed (say you don't need to generate many
ids at a time). Now the important point in choosing an encryption algorithm
is "the guarantee that numbers will never collide". And a way to prove if an encryption algorithm can fulfill
this guarantee is to check if both the original number and the result of
the encryption have the same number of bits, and that the the algorithm is
reversible (bijection).

[Thanks to Adam Liss & CesarB for exapanding on the solution]

How do you make an algorithm for a Random Number Generator?

Bottom line up front - Generating random numbers is really hard to do right, and has badly burned some seriously smart people (John Von Neumann for one). Normal people shouldn't try to create their own RNG algorithms. It requires expertise in number theory, probability & statistics, and numerical computation. Unless you qualify in all three fields, you're much better off using algorithms developed by people who are. If you want to know how to do it right you can find lots of good info at http://en.wikipedia.org/wiki/Random_number_generation and http://en.wikipedia.org/wiki/Pseudorandom_number_generator.

Speaking bluntly, your teacher is totally clueless about this topic.

What is the optimal algorithm for generating an unbiased random integer within a range?

The problem occurs when the number of outputs from the random number generator (RAND_MAX+1) is not evenly divisible by the desired range (max-min+1). Since there will be a consistent mapping from a random number to an output, some outputs will be mapped to more random numbers than others. This is regardless of how the mapping is done - you can use modulo, division, conversion to floating point, whatever voodoo you can come up with, the basic problem remains.

The magnitude of the problem is very small, and undemanding applications can generally get away with ignoring it. The smaller the range and the larger RAND_MAX is, the less pronounced the effect will be.

I took your example program and tweaked it a bit. First I created a special version of rand that only has a range of 0-255, to better demonstrate the effect. I made a few tweaks to rangeRandomAlg2. Finally I changed the number of "balls" to 1000000 to improve the consistency. You can see the results here: http://ideone.com/4P4HY

Notice that the floating-point version produces two tightly grouped probabilities, near either 0.101 or 0.097, nothing in between. This is the bias in action.

I think calling this "Java's algorithm" is a bit misleading - I'm sure it's much older than Java.

int rangeRandomAlg2 (int min, int max)
{
    int n = max - min + 1;
    int remainder = RAND_MAX % n;
    int x;
    do
    {
        x = rand();
    } while (x >= RAND_MAX - remainder);
    return min + x % n;
}

How to pick a random number from 1 to 100? Repeat this 10 times and make sure no number is repeated?

Take the numbers 1–100. Shuffle them randomly. Return the first 10.

This is a variant of the Fisher-Yates shuffle, for a zero-based array a of length n:

for i from n − 1 downto 1 do
     j ← random integer with 0 ≤ j ≤ i
     exchange a[j] and a[i]

Random Number Generator Algorithm

There are three general solutions to the non-duplicate random number problem:

If you want a few numbers from a large range then pick one and reject it if it is a duplicate. If the range is large, then this won't cause too many repeated attempts. This is what you mention above.
If you want a lot of numbers from a small range, then set out all the numbers in an array and shuffle the array. The Fisher-Yates algorithm is standard for array shuffling. Take the random numbers in sequence from the shuffled array.
If you want a lot of numbers from a large range then use an appropriately sized encryption algorithm. E.g. for 64 bit numbers use DES and encrypt 0, 1, 2, 3, ... in sequence. The output is guaranteed unique because encryption is reversible. The Hasty Pudding Cipher can be set for any convenient range of numbers.

Generate a random number sequence to get and average

I think it is impossible for them to be uniformly distributed between 70 and 100 and have a given average at the same time.

What you can do is generate random numbers that have a given average and then scale them to fit into [70, 100] (but they will not be uniformly distributed there).

generate random numbers [0..1(
calculate their average
multiply all of them to match the required average
if any of them does not fit into [70, 100], scale all of them again by reducing their distance from y by the same factor (this does not change the average). x[i] = y + (x[i] - y)*scale

You will end up with numbers that are all in the range [70, 100(, but they will be uniformly distributed across a different (but overlapping) interval that is centered on y. Also, this approach only works with real/floating-point numbers. If you want integers, you got a combinational problem on your hands.

Algorithm for Generating a Random Number