//  Swarm library. Copyright (C) 1996 Santa Fe Institute.
// This library is distributed without any warranty; 
// without even the implied warranty of merchantability 
// or fitness for a particular purpose.
// See file LICENSE for details and terms of copying.

/*
Name:            PMMLCG2gen.m
Description:     Prime Modulus Multiplicative Linear Congruential Generator
Library:         random
Original Author: Nelson Minar
Date:            1996-09-09
Modified by:     Sven Thommesen
Date:            1997-01-15
*/

/*
123456789|123456789|123456789|123456789|123456789|123456789|123456789|123456789|
*/

// PMMLCG2: Prime Modulus Multiplicative Linear Congruential generator
//   X_n+1 = (a * X_n ) mod m ;  (m prime)
// Should have period m; all bits are safe.

// Nelson's comments about PMMLCG:

// This algorithm is taken from "Random Number Generators: Good Ones
// Are Hard To Find", Park & Miller (CACM 1988). The authors claim
// this to be a 'minimally acceptable' or 'minimally sufficient'
// random number generator.

// With m prime, PMMLCG is better than a standard LCG, but the math is
// slower since the modulus is not 2^32.
// With this generator, the low order bits do not have small cycles.
// Also, it is fairly easy to guarantee a period of length m.

// As far as speed goes: for each iteration, we do
// two integer multiplies, a divide, and a mod.
// For gcc 2.6.2 on a Sparc 20/61 this takes about twice as long as LCG.
// But if we compile with "-mv8" (telling gcc to emit IMUL and IDIV
// instructions instead of using the libraries), it's only 26% slower.

#import <collections.h>
#import <random/PMMLCG2gen.h>

@implementation PMMLCG2

// This struct is used by getState and setState
// to pass our state data to/from other objects:

typedef struct {
// Generator identification:
  unsigned magic;
// RandomNumberGenerator data:
  unsigned stateSize;
  unsigned unsignedMax;
  unsigned initialSeed;
  unsigned currentCount;
// generator specific data:
  int a;
  int m;
  int q;
  int r;
  unsigned state;
} state_struct_t;

-resetState {				// Override RandomNumberGenerator method

// This method called from setStateFromSeed in the superclass

// If initialSeed needs to be tested for sanity, do it here:
   // seed==4x+1? seed isOdd?

// Load the state vector from the starting seed:

  state = initialSeed;

  return self;
}


-initState {				// Override RandomNumberGenerator method

// This method called from createBegin in the superclass

// The raw generator returns [1,m-1] from which we subtract 1, so:
   unsignedMax = PMMLCG2MODULUS - 2;

// State size for getState and setState:
   stateSize = sizeof(state_struct_t);

// Set the 'personality' of this generator:

  a = PMMLCG2MULTIPLIER;
  m = PMMLCG2MODULUS;
  q = m / a;
  r = m % a;

// The state vector is allocated as an instance variable.
// It is initialized in -resetState above.

   return self;
}


// ----- protocol RandomNumberGenerator: -----

-(unsigned) getUnsignedSample {		// Override RandomNumberGenerator method
  int high, low, test;

// Generate the next 'random' value from the state.

// Algorithm for PMMLCG:
//   new = (a * old ) mod m

// The split of the math into q and r ensures that we don't overflow.

// NOTE: no check is made that the state has been properly initialized.
// Responsibility for doing so rests with the RandomNumberGenerator class.

// Update count of variates delivered:

  currentCount++;

// Calculate next variate:

  high = state / q;
  low = state % q;
  test = a*low - r*high;
  if (test > 0)
    state = test;
  else
    state = test + m;

  return state - 1;	// coerce so minimum value is 0
}

// ----- protocol InternalState: -----

-(void) getState: (void *) stateBuf {	// Override RandomNumberGenerator method
   state_struct_t * internalState;

// Recast the caller's pointer:
internalState = (state_struct_t *) (stateBuf) ;

// Fill the external buffer with current values:
  // Generator identification:
  internalState->magic = PMMLCG2MAGIC;
  // RandomNumberGenerator variables:
  internalState->unsignedMax = unsignedMax;
  internalState->stateSize = stateSize;
  internalState->initialSeed = initialSeed;
  internalState->currentCount = currentCount;
  // generator specific variables:
  internalState->a = a;
  internalState->m = m;
  internalState->q = q;
  internalState->r = r;
  internalState->state = state;

  // nothing returned from a (void) function
}

-(void) setState: (void *) stateBuf {	// Override RandomNumberGenerator method
   state_struct_t * internalState;

// Recast the caller's pointer:
internalState = (state_struct_t *) (stateBuf) ;

// TEST the integrity of the external data:
if (     (internalState->magic     != PMMLCG2MAGIC)
      || (internalState->stateSize != stateSize)
      || (internalState->a         != a)
      || (internalState->m         != m) 
   )
[InvalidCombination raiseEvent:
 "PMMLCG2 generator: your are passing bad data to setState!\n %u %u %u %u\n",
  internalState->magic, internalState->stateSize, 
  internalState->a, internalState->m ];

// Place external data into internal variables:
  // RandomNumberGenerator variables:
    // stateSize = internalState->stateSize;
    // unsignedMax = internalState->unsignedMax;
  initialSeed = internalState->initialSeed;
  currentCount = internalState->currentCount;
  // generator specific variables:
    // a = internalState->a;
    // c = internalState->c;
    // q = internalState->q;		// or m / a;
    // r = internalState->r;		// or m % a;
  state = internalState->state;

  // nothing returned from a (void) function
}

// ----- temporary methods: -----

- (void) describe: outStream {				// Extend RandomNumberGenerator method
  char buffer[200];
  //  int i;

  (void)sprintf(buffer,"PMMLCG2 describe: outStream: \n");
  (void)sprintf(buffer,"            a = %d\n", a);
  (void)sprintf(buffer,"            m = %d\n", m);
  (void)sprintf(buffer,"            q = %d\n", q);
  (void)sprintf(buffer,"            r = %d\n", r);
  (void)sprintf(buffer,"        state = %u\n", state);

  [super describe: outStream];			// Print RandomNumberGenerator data
  [outStream catC: buffer];
  [outStream catC: "\n"];

  //  return self;
}

-(int) verifySelf {
   const unsigned testValue = 399268536U;
   unsigned bitbucket;
   int i;

   [self setStateFromSeed: 1];

   for (i = 0; i < 10000; i++)
     bitbucket = [self getUnsignedSample];

   if (bitbucket == testValue) {
     printf(" PMMLCG2: Verify passed. Actual value = Expected value = %u\n",
       testValue);
     return 1;
   } else {
     printf(" PMMLCG2: Verify failed! Actual value = %u, Expected value = %u\n",
       testValue, bitbucket);
     return 0;
   } 

}

@end
