// Tests half-bits-set property of an optimally configured Bloom filter

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

char *bitTab;

int k,n,m;

int main()
{
int i,j;
int clear=0,set=0;

printf("Enter k and n\n");
scanf("%d %d",&k,&n);

m=k*n/log(2.0);
printf("m is %d\n",m);

bitTab=(char*) malloc(m*sizeof(char));
for (i=0;i<m;i++)
  bitTab[i]=0;

srandom(k*m);
for (i=0;i<n;i++)
  for (j=0;j<k;j++)
    bitTab[labs(random())%m]=1;

for (i=0;i<m;i++)
  if (bitTab[i])
    set++;
  else
    clear++;

printf("%d clear %d set\n",clear,set);
printf("n*k=%d m*ln m=%f\n",n*k,m*log(m));
}