2008-07-26 day of the sysadmin hangover
by Vasil KolevLast night while somewhat drunk around a discussion with Guninski (I owe him a beer) I wrote some test proggy…
The question was as follows – if we have two sets with 2^16 elements, and each element can be from 0 do 2^32, what’s the chance for the intersection of both sets not to be the empty set. Because the quantity of alcohol wasn’t good for the math skills (and chervarium just swore at us and declined to calculate it), this is what I wrote to get some stats:
(to be noted that this is the first time I manage to use qsort() :) )
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/fcntl.h>
#include <stdlib.h>
#define LEN 65536
#define NTEST 100
static int compare(const void *a, const void *b)
{
if (*((int *) a) > *((int *) b)) return 1;
if (*((int *) a) < *((int *) b)) return -1;
return 0;
}
int do_whatever()
{
int s0[LEN],s1[LEN];
int i=0,j=0;
int rndsrc;
rndsrc=open("/dev/urandom",O_RDONLY);
read(rndsrc,s0,(sizeof(int)*LEN));
read(rndsrc,s1,(sizeof(int)*LEN));
close(rndsrc);
qsort (s0,LEN,sizeof(int),compare);
qsort (s1,LEN,sizeof(int),compare);
while ( (s0[i]!=s1[j]) && (i<LEN) && (j<LEN))
{
if (s0[i]<s1[j]) { if (!i<LEN) i++; }
else {if (!j<LEN) j++;};
}
if (s0[i]==s1[j]) return 1;
return 0;
}
int main()
{
int i,num=0;
for (i=0;i<NTEST;i++)
num+=do_whatever();
printf ("tests %d true %d false %d\n",NTEST,num,NTEST-num);
return 0;
}
Guninski was saying that the chances incline to 1, and seems to be right – according to this it’s more that 1:2, which is inclining to 1 :)
And damn, Shopov, how could you buy me two beers after I’ve drunk so much. Half of the morning I wanted to be dead :).
Whomever remembers more of the celebration – feel free to write.