// proj.cc (c) Kris COOLSAET, Belgium
// ============================================================
// More info: http://turing.hogent.be/~kc/cds/part12.htm
//
// Computes a projective CDS of a given PRIME order using a 
// linear recurrence of degree 3 with parameters (A,B,C).
//
// Checks whether the series has the correct period (cheats
// a little).
//
// usage:    proj order A B C
//
// 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 C\n";
  exit (1);
}

// ------------------------------------------------------------
// RECURRENCE
// ------------------------------------------------------------
// Generates elements of linear recurrence (A,B,C) modulo q. Stores
// indices of elements equal to 0 in given table. Stops at the 
// second occurrence of 0 0 in the series and returns the period.
//
// This is cheating a little, for really we need to continue up to
// the second occurence of 0 0 1. 
// Please, would someone prove that this is still correct ?

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

  // init elements
  int pprev = 0;  
  int prev  = 1;
  int last  = A;
  int cnt = 1;
  table[0] = 0;

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

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

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

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

  int * table = new int [order+1];

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

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

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