Filling an array with random numbers from 1 to 10^10 in C or C++

Question

a part of an assignment of mine is based on an array (its size is given by the user) which contains random numbers from 1 to 10^10. Then we have to find the k-th smaller number of the array. Here's what I tried:

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

using namespace std;

void swap(int *x,int *y)
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

int choose_pivot(int i,int j )
{
    return((i+j) /2);
}

// Print array
void printarr(int arr[],int n)
{
    int i;
    for(i=0;i<n;i++)
        printf("%d\t",arr[i]);
}

// Find algorithm
int find1(int arr[],int left,int right,int k)
{
    int i,j,pivot;
    if (left==right)
        return arr[left];
    else
    {
        i=left;
        j=right+1;
        pivot= arr[left];
        do
        {
            do {
                i=i+1;
            } while (arr[i]>=pivot);
            do {
                j =j-1;
            } while (arr[j]<=pivot);
            if (i<j)
                swap(arr[i],arr[j]);
        } while (j<=i);
    }
    swap(arr[left],arr[j]);
    if (k==j)
        return arr[j];
    else if (k<j)
        find1(arr,left,j-1,k);
    else 
        find1(arr,j+1,right,k-j);
}

int main(int argc, char *argv[])
{
    srand(time(NULL));
    int n,i,fi,k;
    printf("Give array's size:\n");
    scanf("%d",&n);
    int pin[n];
    for (i=0;i<n;i++)
        pin[i]=((rand()*rand()) % 1000000000) +1;
    printf("Give k: \n");
    scanf("%d",&k);
    printf("The array contains the following numbers:\n\n");
    printarr(pin,n);
    fi=find1(pin,0,n-1,k);//find the k-th smallest number in the array
    printf("The k-th smallest number is: %d",fi);

    system("PAUSE");
}

As you can see 10^10 is a very big value, and I did something else to fill the array with the random numbers. Is it correct? Is there something else I could do? And my second problem is on the find algorithm. It doesn't work. Could anyone help me with these? Thank you very much

Answer 1

long long get_big_rand()
{

    long long result;
    do {
        result = (rand() & 0x3ff);
        result <<= 12;
        result |= (rand() & 0xfff);
        result <<= 12;
        result |= (rand() & 0xfff);
    } while (++result > 10000000000ULL);
    return result;
}

Answer 2

rand()*rand() is a lot different than a single rand(), it decreases the randomness and changes its distribution. See this question for a deeper explanation.

Also, an integer usually is 4 bytes. It can contain a value as big as 2^31 (2 billions and something) or 2^32 (4 billions and more) if it's unsigned. You can see the max number it can contain checking the INT_MAX macro defined in limits.h. 10^10 is 10 billions, it won't fit in an integer, you'll have to use a bigger type (long long usually is 64 bytes thus more than you need).

rand, also, returns numbers up to RAND_MAX, and since it returns an int, it won't bigger than INT_MAX. You should use some other way to generate a number as big as 10^10.

If you don't care about randomness and random number distributions you could sum n random numbers (obtained by rand) so that n=10^10 / RAND_MAX.

Answer 3

If you take a closer look at 10¹⁰ you will notice that it's quite a round limit. My take on this would be to generate each number, one digit at a time and ignoring insignificant zeroes. At this point you would have a number between 0 and 10¹⁰-1 inclusive. All you're left with doing is adding a 1.

As for random()*random(), that is the exact topic of this other question.

Alin

Answer 4

Problem #1, an int will only hold a number of size 2^31 in size. You'll need a slightly bigger alternative for your pin array.

Also, multiplying your two random numbers together really doesn't do much - except perhaps make the number less random.

Next, you can't create an array on the stack dynamically with the user's input. That will require a new solution to make alloc an array for you.

Answer 5

rand()*rand() isn't going to do anything for you. It doesn't scale the way you think it does, and it does change the distribuon. In fact

double norm_rand(){
    double r=0;
    for(unsigned i=0;i!=12;++i)
        r+=rand()/static_cast<double>(RAND_MAX);
    return (r/12)-6;
}

is a common way to simulate a normal distribution with mean 0 and variance 1;

The best way to to get large random numbers is using a random number device, like /dev/urandom or RtlGenRandom. i.e.

typedef unsigned long long big_type;
std::vector<double> rnums;
std::vector<big_type> buf(numtoread);
        std::ifstream rnds("/dev/urandom"); 
rnds.read(reinterpret_cast<char*>(&buf[0],buf.size()*sizeof(big_type));
std::transform(buf.begin(),buf.end(),std::back_inserter(rnums),
     [](big_type const& i){
        return (i*100000000000.)/(std::numeric_limits<big_type>::max());
     });

At the risk of doing your homework for you, an entirely different approach is to use the libraries that come with C++.

#include <cassert>
#include <sstream>
#ifndef _MSC_VER  //then assume Linux
#include <tr1/random>
#else
#include <random>
#endif
#include <boost/lexical_cast.hpp>
#include <algorithm>
#include <iterator>
#include <iostream>
int main(int argc, char** argv)
{
    assert(argc==3);
    unsigned const numentries=boost::lexical_cast<unsigned>(argv[1]);
    unsigned const k=boost::lexical_cast<unsigned>(argv[2]);
    std::cout<<" finding "<<k<<"th of "<< numentries<<" entries\n";
    assert(k<=numentries);
    std::vector<double> nums(numentries);
    std::tr1::uniform_real<> rng(0.,10000000000.);
    std::tr1::minstd_rand generator(42u);
    std::tr1::variate_generator<std::tr1::minstd_rand, std::tr1::uniform_real<> >
            uni(generator, rng);
    std::generate_n(nums.begin(),nums.size(),uni);
    std::cout<<" Generated:\t ";
    std::copy(nums.begin(),nums.end(),std::ostream_iterator<double>(std::cout,"\t"));
    std::sort(nums.begin(),nums.end());
    std::cout<<"\n The "<<k<<"th smallest entry is "<<nums[k]<<"\n";
    return 0;
}

(If you are in class at the level of just asking for making an array of rand numbers and you hand that in, they'll probably fail you) What I do in practice is to combine the two approaches. This is used in place of the linear conguentual rng used above (the minstd_rand):

template<typename bigtype=unsigned>
struct randeng {
    typedef bigtype result_type;
    randeng(unsigned x) :
        m_samplesrequired(x), m_samples(x), m_lastused() {
        std::ifstream rand;
        rand.open("/dev/urandom");
        assert(rand);
        rand.read(reinterpret_cast<char*> (&*(m_samples.begin())),
                m_samplesrequired * sizeof(unsigned));
    }
    result_type operator()() const {
        assert(m_lastused<m_samplesrequired);
        return m_samples[m_lastused++];
    }
    result_type max() const {
        return std::numeric_limits<result_type>::max();
    }
    result_type min() const {
        return 0;
    }
    unsigned m_samplesrequired;
    std::vector<result_type> m_samples;
    mutable unsigned m_lastused;
};

This always seems to give much better results.

Answer 6

you forgot your return statements. at the end of find1 you should be doing:

if (k==j)
    return arr[j];
else if (k<j)
    return find1(arr,left,j-1,k);
else 
    return find1(arr,j+1,right,k-j);
}