//================================================== file = ballsBinsSim.c =====
//=  Simulation of N balls thrown into M bins                                  =
//==============================================================================
//= Notes:                                                                     =
//=   1) Need to set NUM_EXPER, M, and N in #define section                    =
//=   2) Determines Pr[i bins are non-empty]                                   =
//=----------------------------------------------------------------------------=
//= Example execution:                                                         =
//=                                                                            =
//=   Running...                                                               =
//=   =========================================== ballsBinsSim.c =====         =
//=   = Number of experiments = 10000000                                       =
//=   = M = 4 bins                                                             =
//=   = N = 8 balls                                                            =
//=   =---------------------------------------------------------------         =
//=   = Pr[ 1 bins are non-empty] = 0.000063                                   =
//=   = Pr[ 2 bins are non-empty] = 0.023373                                   =
//=   = Pr[ 3 bins are non-empty] = 0.353744                                   =
//=   = Pr[ 4 bins are non-empty] = 0.622819                                   =
//=   ================================================================         =
//=----------------------------------------------------------------------------=
//=  Build: bcc32 ballsBinsSim.c                                               =
//=----------------------------------------------------------------------------=
//=  Execute: ballsBinsSim.c                                                   =
//=----------------------------------------------------------------------------=
//=  Author: Ken Christensen                                                   =
//=          University of South Florida                                       =
//=          WWW: http://www.csee.usf.edu/~christen                            =
//=          Email: christen@cse.usf.edu                                       =
//=----------------------------------------------------------------------------=
//=  History: KJC (04/11/09) - Genesis (from bfSim.c)                          =
//==============================================================================
//----- Include files ----------------------------------------------------------
#include <stdio.h>                 // Needed for printf()
#include <math.h>                  // Needed for pow()

//----- Constant defines -------------------------------------------------------
#define  NUM_EXPER      10000000   // Number of experiments to run
#define          M             3   // Number of bins
#define          N             3   // Number of balls

//----- Function prototypes ----------------------------------------------------
unsigned int randInt(int seed);    // LCG from Jain

//==============================================================================
//=  Main program                                                              =
//==============================================================================
void main(void)
{
  unsigned int bin[M];             // The bins
  unsigned int nonEmptyCount[M+1]; // Count of occupied bins
  unsigned int count;              // Counter of occupied bins
  unsigned int index;              // Bin index (0, 1, ... M)
  int          i,j;                // Loop counters

  // Seed the RNG
  randInt(1);

  // Clear binCount vector
  for (i=1; i<=M; i++)
    nonEmptyCount[i] = 0;

  // Loop for number of experiments to run
  printf("Running... \n");
  for (i=0; i<NUM_EXPER; i++)
  {
    // Clear the bins
    for (j=0; j<M; j++)
      bin[j] = 0;

    // Randomly throw the balls into the bins
    for (j=0; j<N; j++)
    {
      index = randInt(0) % M;
      bin[index] = 1;
    }

    // Count the number of non-empty bins
    count = 0;
    for (j=0; j<M; j++)
      if (bin[j] == 1) count++;

    // Increment the corresponding nonemptyCount value
    nonEmptyCount[count]++;
  }

  // Compute and output the results
  printf("=========================================== ballsBinsSim.c ===== \n");
  printf("= Number of experiments = %d \n", NUM_EXPER);
  printf("= M = %d bins  \n", M);
  printf("= N = %d balls \n", N);
  printf("=--------------------------------------------------------------- \n");
  for (i=1; i<=M; i++)
    printf("= Pr[%2d bins are non-empty] = %f \n",
      i, (double) nonEmptyCount[i] / NUM_EXPER);
  printf("================================================================ \n");
}

//==============================================================================
//= Multiplicative LCG from Jain                                               =
//==============================================================================
unsigned int randInt(int seed)
{
  const long  a =      16807;  // Multiplier
  const long  m = 2147483647;  // Modulus
  const long  q =     127773;  // m div a
  const long  r =       2836;  // m mod a
  static long x;               // Random int value
  long        x_div_q;         // x divided by q
  long        x_mod_q;         // x modulo q
  long        x_new;           // New x value

  // Set the seed value
  if (seed != 0)
    x = seed;

  // RNG using integer arithmetic
  x_div_q = x / q;
  x_mod_q = x % q;
  x_new = (a * x_mod_q) - (r * x_div_q);
  if (x_new > 0)
    x = x_new;
  else
    x = x_new + m;

  // Return a random unsigned integer
  return(x);
}