Quelle engel.c Sprache: C

/****************************************************************************
**
**    engel.c                         NQ                       Werner Nickel
**                                         nickel@mathematik.tu-darmstadt.de
*/

#include "nq.h"
#include "engel.h"
#include "presentation.h"
#include "glimt.h"

static  int     LeftEngel = 0, RightEngel = 0, Engel = 0;
static  int     RevEngel = 0;
static  int     NrEngelGens = 0;
static  int     NrWords;
static  int     Needed;
static  word    A;
int     SemigroupOnly  = 0;
int     SemigroupFirst = 0;
int     CheckFewInstances = 0;
int     ReverseOrder = 0;

static
void    Error(word v, word w, char type) {
printf("Overflow in collector computing [ ");
printWord(v, 'a');
if (type == 'e') printf(" , %d ", Engel);
if (type == 'l') printf(" , %d ", LeftEngel);
if (type == 'r') printf(" , %d ", RightEngel);
printWord(w, 'a');
printf(" ]\n");
}

word    EngelCommutator(word v, word w, int engel) {
long    n;
word    v1;

if (Class + 1 < engel) {
  v1 = (word)Allocate(sizeof(gpower));
  v1[0].g = EOW;
  v1[0].e = (expo)0;
  return v1;
}

/*
** If the current class reaches the weight of the engel condition,
** then we want to speed up the evaluation of the engel relations by
** evaluating each commutator only with the required precision.  The
** last commutator of an Engel-n commutator has to be evaluated in
** class (Class+1) quotient (i.e. the full group), the second last in
** the class Class quotient, etc.  The first commutator has to be
** evaluated in the class (Class+1-(n-1)) quotient.  See also the
** function SetupCommuteList() in addgen.c
*/

n = 1;
Class = Class - (engel - 1);

if ((v = Commutator(v, w)) == (word)0)
  return (word)0;

n++;
while (n <= engel) {
  Class++;

  if ((v1 = Commutator(v, w)) == (word)0)
   return (word)0;

  Free(v);
  v = v1;

  n++;
}
return v;
}

static
void    evalEngelRel(word v, word w) {
word    comm;
long    needed;

/*      printf( "evalEngelRel() called with : " );
        printWord( v, 'A' ); printf( "    " );
        printWord( w, 'A' ); putchar( '\n' ); */

NrWords++;

/* Calculate [ v, w, .., w ] */
if ((comm = EngelCommutator(v, w, Engel)) == (word)0) {
  Error(v, w, 'e');
  return;
}

needed = addRow(ExpVecWord(comm));
if (needed) {
  printf("# [ ");
  printWord(v, 'a');
  printf(", %d ", Engel);
  printWord(w, 'a');
  printf(" ]\n");
}
if (CheckFewInstances) Needed |= needed;
else                    Needed = 1;

Free(comm);
}

static
void    buildPairs(word u, long i, gen g, word v, long wt, long which) {
long    save_wt;

/* First we check if the Engel condition is trivially
   satisfied for weight reasons. The commutator
   [u, n v] is 1 if w(u) + n*w(v) > Class+1. */
if (which == 1 && i == 1 &&
         Wt(abs(u[0].g)) + Engel * Wt(abs(v[0].g)) > Class + 1)
  return;

if (wt == 0 && which == 1 && i > 0) {
  evalEngelRel(u, v);
  return;
}

/* Keep u and start to build v. */
if (i > 0 && which == 2) buildPairs(v, 0, 1, u, wt, 1);

if (g > NrPcGens) return;

save_wt = wt;
while (!EarlyStop &&
         g <= NrPcGens && Wt(g) <= Class + 1 - Engel && Wt(g) <= wt) {
  u[i].g   = g;
  u[i].e   = (expo)0;
  u[i + 1].g = EOW;
  while (!EarlyStop && Wt(g) <= wt) {
   u[i].e++;
   if (Exponent[g] > (expo)0 && Exponent[g] == u[i].e) break;
   wt -= Wt(g);
   buildPairs(u, i + 1, g + 1, v, wt, which);
   /* now build the same word with negative exponent */
   if (!EarlyStop && !SemigroupOnly && Exponent[g] == (expo)0) {
    u[i].g *= -1;
    buildPairs(u, i + 1, g + 1, v, wt, which);
    u[i].g *= -1;
   }
  }
  wt = save_wt;
  g++;
}
u[i].g = EOW;
u[i].e = (expo)0;
if (EarlyStop || SemigroupOnly || !SemigroupFirst) return;

while (!EarlyStop &&
         g <= NrPcGens && Wt(g) <= Class + 1 - Engel && Wt(g) <= wt) {
  u[i].g   = -g;
  u[i].e   = (expo)0;
  u[i + 1].g = EOW;
  while (!EarlyStop && Wt(g) <= wt) {
   u[i].e++;
   if (Exponent[g] > (expo)0 && Exponent[g] == u[i].e) break;
   wt -= Wt(g);
   buildPairs(u, i + 1, g + 1, v, wt, which);
   if (EarlyStop) return;
   /* now build the same word with negative exponent */
   if (!EarlyStop && !SemigroupOnly && Exponent[g] == (expo)0) {
    u[i].g *= -1;
    buildPairs(u, i + 1, g + 1, v, wt, which);
    u[i].g *= -1;
   }
  }
  wt = save_wt;
  g++;
}
u[i].g = EOW;
u[i].e = (expo)0;
}

static
void    evalEngel(void) {
word    u, v;
long    c;

u = (word)Allocate((NrPcGens + NrCenGens + 1) * sizeof(gpower));
v = (word)Allocate((NrPcGens + NrCenGens + 1) * sizeof(gpower));

/* For `production purposes' I don't want to run through       */
/* those classes that don't yield non-trivial instances of the */
/* Engel law. Therefore, we stop as soon as we ran through a   */
/* class that didn't yield any non-trivial instances. This is  */
/* done through the static variable Needed which is set by     */
/* evalEngelRel() as soon as a non-trivial instance has been   */
/* found if the flag CheckFewInstances (option -c) is set.     */
if (ReverseOrder)
  for (c = Class + 1; !EarlyStop && c >= 2; c--) {
   u[0].g = EOW;
   u[0].e = (expo)0;
   v[0].g = EOW;
   v[0].e = (expo)0;
   NrWords = 0;
   if (Verbose)
    printf("# Checking pairs of words of weight %ld\n", c);
   buildPairs(u, 0, 1, v, c, 2);
   if (Verbose) printf("# Checked %d words.\n", NrWords);
  }
else {
  Needed = 1;
  for (c = 2; !EarlyStop && Needed && c <= Class + 1; c++) {
   Needed = 0;
   u[0].g = EOW;
   u[0].e = (expo)0;
   v[0].g = EOW;
   v[0].e = (expo)0;
   NrWords = 0;
   if (Verbose)
    printf("# Checking pairs of words of weight %ld\n", c);
   buildPairs(u, 0, 1, v, c, 2);
   if (Verbose) printf("# Checked %d words.\n", NrWords);
  }
  for (; !EarlyStop && c <= Class + 1; c++)
   printf("# NOT checking pairs of words of weight %ld\n", c);
}
free(u);
free(v);
}

static
void    evalRightEngelRel(word w) {
word    comm;
long    n,  needed;

/*      printf( "evalRightEngelRel() called with : " );*/
/*      printWord( w, 'A' );*/
/*      putchar( '\n' );*/

NrWords++;
/* Calculate [ a, w, .., w ] */
if ((comm = EngelCommutator(A, w, RightEngel)) == (word)0) {
  Error(A, w, 'r');
  return;
}

needed = addRow(ExpVecWord(comm));
if (needed) {
  printf("# [ ");
  printWord(A, 'a');
  for (n = RightEngel - 1; n >= 0; n--) {
   printf(", ");
   printWord(w, 'a');
  }
  printf(" ]\n");
}
if (CheckFewInstances) Needed |= needed;
else                    Needed = 1;

Free(comm);
}

static
void    evalLeftEngelRel(word w) {
word    comm;
long    n,  needed;

/*      printf( "evalLeftEngelRel() called with : " );*/
/*      printWord( w, 'A' );*/
/*      putchar( '\n' );*/

NrWords++;
/* Calculate [ w, a, .., a ] */

if ((comm = EngelCommutator(w, A, LeftEngel)) == (word)0) {
  Error(w, A, 'l');
  return;
}

needed = addRow(ExpVecWord(comm));
if (needed) {
  printf("# [ ");
  printWord(w, 'a');
  for (n = LeftEngel - 1; n >= 0; n--) {
   printf(", ");
   printWord(A, 'a');
  }
  printf(" ]\n");
}
if (CheckFewInstances) Needed |= needed;
else                    Needed = 1;

Free(comm);
}

static
void    buildWord(word u, long i, gen g, long wt) {
long    save_wt;

if (wt == 0 && i > 0) {
  if (RightEngel) evalRightEngelRel(u);
  if (LeftEngel)  evalLeftEngelRel(u);
  return;
}

if (g > NrPcGens) return;

save_wt = wt;
while (!EarlyStop && g <= NrPcGens && Wt(g) <= wt) {
  u[i].g   = g;
  u[i].e   = (expo)0;
  u[i + 1].g = EOW;
  while (!EarlyStop && Wt(g) <= wt) {
   u[i].e++;
   if (Exponent[g] > (expo)0 && Exponent[g] == u[i].e) break;
   wt -= Wt(g);
   buildWord(u, i + 1, g + 1, wt);
   /* now build the same word with negative exponent */
   if (!EarlyStop && !SemigroupOnly &&
           !SemigroupFirst && Exponent[g] == (expo)0) {
    u[i].g *= -1;
    buildWord(u, i + 1, g + 1, wt);
    u[i].g *= -1;
   }
  }
  wt = save_wt;
  g++;
}
u[i].g = EOW;
u[i].e = (expo)0;
if (EarlyStop || SemigroupOnly || !SemigroupFirst) return;
while (!EarlyStop && g <= NrPcGens && Wt(g) <= wt) {
  u[i].g   = -g;
  u[i].e   = (expo)0;
  u[i + 1].g = EOW;
  while (!EarlyStop && Wt(g) <= wt) {
   u[i].e++;
   if (Exponent[g] > (expo)0 && Exponent[g] == u[i].e) break;
   wt -= Wt(g);
   buildWord(u, i + 1, g + 1, wt);
  }
  wt = save_wt;
  g++;
}
u[i].g = EOW;
u[i].e = (expo)0;
}

static
void    evalLREngel(void) {

word    u;
int     n;
long    cl;

A = (word)Allocate(2 * sizeof(gpower));
u = (word)Allocate((NrPcGens + NrCenGens + 1) * sizeof(gpower));

for (n = 1; !EarlyStop && n <= NrEngelGens; n++) {

  if (RevEngel) A[0].g = NumberOfAbstractGens() - n + 1;
  else           A[0].g = n;
  A[0].e = (expo)1;
  A[1].g = EOW;
  A[1].e = (expo)0;

  Needed = 1;
  for (cl = 2; !EarlyStop && Needed && cl <= Class + 1; cl++) {
   Needed = 0;
   u[0].g = EOW;
   u[0].e = (expo)0;
   NrWords = 0;
   if (Verbose) printf("# Checking words of weight %ld\n", cl - 1);
   buildWord(u, 0, 1, cl - 1);
   if (Verbose) printf("# Checked %d words.\n", NrWords);
  }
  for (; !EarlyStop && cl <= Class + 1; cl++)
   printf("# NOT checking words of weight %ld\n", cl);

}
free(u);
free(A);
}

void    EvalEngel(void) {

long    t = 0;

if (Verbose) t = RunTime();

if (LeftEngel || RightEngel) evalLREngel();
if (Engel) evalEngel();

if (Verbose)
  printf("# Evaluated Engel condition (%ld msec).\n", RunTime() - t);
}

void    InitEngel(int l, int r, int v, int e, int n) {
LeftEngel = l;
RightEngel = r;
RevEngel = v;

Engel = e;

NrEngelGens = n;
}

quality92%

¤ Dauer der Verarbeitung: 0.11 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.