//==================================================== file = genuniq. =====
//=  Program to generate unique random integer values                       =
//===========================================================================
//=  Notes: 1) Writes to a user specified output file                       =
//=         2) Generates user specified number of values (up to 2^32 - 1)   =
//=         3) Uses Roy Hann's Generate31()                                 =
//=-------------------------------------------------------------------------=
//= Example execution:                                                      =
//=                                                                         =
//=   ---------------------------------------- genuniq.c -----              =
//=   -  Program to generate unique random integers          -              =
//=   --------------------------------------------------------              =
//=   Output file name ===================================> out.dat         =
//=   Random number seed (greater than 0) ================> 1               =
//=   Number of unique values to generate ================> 1000000         =
//=   --------------------------------------------------------              =
//=   -  Generating samples to file                          -              =
//=   --------------------------------------------------------              =
//=   --------------------------------------------------------              =
//=   -  Done!                                                              =
//=   --------------------------------------------------------              =
//=-------------------------------------------------------------------------=
//=  Build: bcc32 genuniq.c                                                 =
//=-------------------------------------------------------------------------=
//=  Execute: genuniq                                                       =
//=-------------------------------------------------------------------------=
//=  Author: Ken Christensen                                                =
//=          University of South Florida                                    =
//=          WWW: http://www.csee.usf.edu/~christen                         =
//=          Email: christen@csee.usf.edu                                   =
//=-------------------------------------------------------------------------=
//=  History: KJC (05/14/08) - Genesis                                      =
//=           KJC (05/15/08) - Fixed probelm in shuffle                     =
//===========================================================================
//----- Include files -------------------------------------------------------
#include <stdio.h>             // Needed for printf()
#include <stdlib.h>            // Needed for malloc(), atoi(), and exit()

//----- Function prototypes -------------------------------------------------
int randInt(int seed);         // LCG RNG with x_n = 7^5*x_(n-1)mod(2^31 - 1)
int Generator31(void);         // Unique value RNG credited to Roy Hann

//===========================================================================
//=  Main program                                                           =
//===========================================================================
void main()
{
  FILE   *fp;                  // File pointer to output file
  char    file_name[256];      // Output file name string
  char    temp_string[256];    // Temporary string variable
  int     num;                 // Number of values to generate
  int    *z;                   // Array of shuffled unique integers
  int     temp;                // Temporary value
  int     i, j;                // Indexes

  // Output banner
  printf("---------------------------------------- genuniq.c ----- \n");
  printf("-  Program to generate unique random integers          - \n");
  printf("-------------------------------------------------------- \n");

  // Prompt for output filename and then create/open the file
  printf("Output file name ===================================> ");
  scanf("%s", file_name);
  fp = fopen(file_name, "w");
  if (fp == NULL)
  {
    printf("*** ERROR in creating output file (%s) \n", file_name);
    exit(1);
  }

  // Prompt for random number seed and then use it
  printf("Random number seed (greater than 0) ================> ");
  scanf("%s", temp_string);
  randInt((int) atoi(temp_string));

  // Prompt for number of values to generate
  printf("Number of unique values to generate ================> ");
  scanf("%s", temp_string);
  num = atoi(temp_string);

  // Malloc space for an array of num integers
  z = (int *) malloc(num * sizeof(int));
  if (z == NULL)
  {
    printf("*** ERROR - could not malloc space for array \n");
    exit(1);
  }

  // Create an array of num unique integers
  for (i=0; i<num; i++)
    z[i] = Generator31();

  // Shuffle the array of unique integers
  for (i=0; i<num; i++)
  {
    j = randInt(0) % num;
    temp = z[i];
    z[i] = z[j];
    z[j] = temp;
  }

  // Output message and generate values
  printf("-------------------------------------------------------- \n");
  printf("-  Generating samples to file                          - \n");
  printf("-------------------------------------------------------- \n");

  // Output the values to the file
  for (i=0; i<num; i++)
    fprintf(fp, "%d \n", z[i]);

  // Output message and close the output file
  printf("-------------------------------------------------------- \n");
  printf("-  Done!                                               - \n");
  printf("-------------------------------------------------------- \n");
  fclose(fp);
}

//=========================================================================
//= RNG of unique values from                                             =
//=   http://www.teradata.com/teradataforum/Topic10933-9-1.aspx#bm11020   =
//=========================================================================
int Generator31(void)
{
  static int n = 1;            // Start with n = 1

  // Generate the unique random value
  n = n >> 1 | ((n^n >> 3) & 1) << 30;

  // Return the unique random value
  return n;
}

//=========================================================================
//= Multiplicative LCG for generating uniform(0.0, 1.0) random numbers    =
//=   - x_n = 7^5*x_(n-1)mod(2^31 - 1)                                    =
//=   - With x seeded to 1 the 10000th x value should be 1043618065       =
//=   - From R. Jain, "The Art of Computer Systems Performance Analysis," =
//=     John Wiley & Sons, 1991. (Page 443, Figure 26.2)                  =
//=========================================================================
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 (seed is set to 1)
  long        x_div_q;         // x divided by q
  long        x_mod_q;         // x modulo q
  long        x_new;           // New x value

  // Seed the RNG
  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 integer value
  return(x);
}