Random Number Generation

* BigRand and RandInt
long long bigrand()
{ return (long long)RAND_MAX * rand() + rand(); }
int randint(int l, int u)
{ return l + bigrand() % (u-l+1); }
Here rand() returns one random number with 32bits; bigrand returns one big random number with 64bits and randint(l, u) returns one random number between l and u.

* Select K random numbers in an array of N with sorted output
To select s number out of r remaining, the next number would be selected with probability s/r. It could be expressed by
if (bigrand() % r) < s
The pseudocode is:
select = K
remaining = N
for i = [0, N-1]
   if (bigrand() % remaining) < select
     print i
     select--
   remaining--
Alternatively, the data structure of set could be used:
initialize set S to empty
size = 0
while size < K do
   t = bigrand() % N
   if t is not in S
     insert t into S
     size++
print S in sorted order
The third one allowing number repeating is to shuffle the array, like this:
for i = [0, N-1]
   swap(i, randint(i, n-1))