// semiaff.cc (c) Kris COOLSAET, Belgium
// ============================================================
// More info: http://turing.hogent.be/~kc/cds/part11.htm
//
// Computes a semi-affine CDS of a given PRIME order using a 
// linear recurrence of degree 2 with parameters (A,B).
// Checks whether the series has the correct period.
//
// usage:    semiaff order A B 
//
// history:
//   97/01/10    First version

#include <stdlib.h>
#include <iostream.h>
#include <iomanip.h>

// ------------------------------------------------------------
// USAGE
// ------------------------------------------------------------

void usage (char *progname)
{
  cerr << "usage: " << progname << " order A B\n";
  exit (1);
}

// ------------------------------------------------------------
// RECURRENCE
// ------------------------------------------------------------
// Generates elements of linear recurrence (A,B) modulo q. Stores
// indices of elements equal to 1 in given table. Stops at the 
// second occurrence of 0 1 in the series and returns the period.

int recurrence (int q, int A, int B, int *table)
{
  // put A,B in range 0..q-1
  A = (A % q); if (A < 0) A += q;
  B = (B % q); if (B < 0) B += q;

  // generate second and third element
  int prev = 1;
  int last = A;
  int cnt = 0;

  // generate sequence
  int pos;
  for (pos=0; prev != 0 || last != 1; pos++) {
    if (prev==1) table[cnt++] = pos;
    int tmp = (A*last + B*prev) % q;
    prev = last; last = tmp;
  }
  // return period
  return pos+1;
}

// ------------------------------------------------------------
// MAIN
// ------------------------------------------------------------

int main (int argc, char **argv)
{
  // check usage
  if (argc != 4) usage (argv[0]);
  argv++;

  // parse arguments
  int order = atoi(*argv++);
  int A = atoi(*argv++);
  int B = atoi(*argv++);

  int * table = new int [order];

  // do it
  int period = recurrence (order, A, B, table);

  if (period != order*order-1)
    cout << "Wrong period " << period 
         << " (should be " << order*order-1 << ")\n";
  else {
    cout << "Found difference set:\n";
    for (int i=0; i < order; i++)
      cout << setw(4) << table[i];
    cout << "  (" << period << ")\n";
  }

  // cleanup
  delete [] table;
  return 0;
}