Quelle eliminate.c Sprache: C

/****************************************************************************
**
*A  eliminate.c                 ANUPQ source                   Eamonn O'Brien
**
*Y  Copyright 1995-2001,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
*Y  Copyright 1995-2001,  School of Mathematical Sciences, ANU,     Australia
**
*/

#include "pq_defs.h"
#include "pcp_vars.h"
#include "pq_functions.h"

/* eliminate all redundant generators to construct the consistent
   power commutator presentation for the group to class current_class;

   if middle_of_tails is TRUE, do not delete space set aside in
   setup; in this case, only deallocate redundant generators */

void eliminate(Logical middle_of_tails, struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int i;
   register int j;
   register int k;
   register int l;
   register int p1;
   register int ba;
   register int lg;
   register int length;
   register int bound;

   register int structure = pcp->structure;
   register int current_class = pcp->cc;
   register int lused = pcp->lused;
   register int prime = pcp->p;
   register int dgen = pcp->dgen;
   register int ndgen = pcp->ndgen;
   register int pointer;
   register int value;

#include "access.h"

   /* calculate new values for irredundant generators and set them up
      in a renumbering table of length pcp->lastg - pcp->ccbeg + 1
      which looks to compact like a normal exponent-generator string
      pointed to by y[dgen] */

   if (current_class != 1) {

      if (is_space_exhausted(pcp->lastg - pcp->ccbeg + 3, pcp))
         return;

      structure = pcp->structure;
      lused = pcp->lused;
      y[lused + 1] = dgen;
      y[dgen] = -(lused + 1);
      y[lused + 2] = pcp->lastg - pcp->ccbeg + 1;
      ba = lused + 3 - pcp->ccbeg;
      pcp->lused += pcp->lastg - pcp->ccbeg + 3;
      lused = pcp->lused;
      lg = pcp->ccbeg - 1;
      for (i = pcp->ccbeg, bound = pcp->lastg; i <= bound; i++) {
         y[ba + i] = 0;
         if (y[structure + i] > 0)
            y[ba + i] = ++lg;
      }

      /* update pcp->first_pseudo */
      bound = pcp->lastg;
      for (i = pcp->first_pseudo; i <= bound && y[structure + i] <= 0; i++)
         ;
      pcp->first_pseudo = (i > pcp->lastg) ? lg + 1 : y[ba + i];

      /* update the commutator tables */
      p1 = y[pcp->ppcomm + 2];
      for (i = 1, bound = pcp->ncomm; i <= bound; i++) {
         update(p1 + i, pcp);
         if (pcp->overflow)
            return;
      }

      /* update the power tables */
      for (i = 2, bound = pcp->ccbeg; i <= bound; i++) {
         /* fix (i - 1)^p */
         update(pcp->ppower + i - 1, pcp);
         if (pcp->overflow)
            return;
      }

      /* update the redundant defining generators and inverses */
      for (i = 1; i <= ndgen; i++) {
         update(dgen + i, pcp);
         if (pcp->overflow)
            return;
         update(dgen - i, pcp);
         if (pcp->overflow)
            return;
      }

      /* finally update and move structure information */

      if (middle_of_tails) {
         pointer = pcp->structure + pcp->ccbeg - 1;
         for (i = pcp->ccbeg; i <= pcp->lastg; ++i) {
            if ((value = y[pcp->structure + i]) > 0)
               y[++pointer] = value;
            else if (value < 0)
               y[-value] = 0;
         }
      } else {
         k = pcp->ppower;
         structure = pcp->structure;
         for (i = pcp->lastg; i >= pcp->ccbeg; i--) {
            if ((j = y[structure + i]) > 0) {
               y[k] = j;
               k--;
            } else if (j < 0) {
               /* deallocate equation for redundant generator i */
               p1 = -j;
               y[p1] = 0;
            }
         }

         for (; i > 0; i--)
            y[k--] = y[structure + i];
         if (pcp->subgrp != structure)
            delete_tables(0, pcp);
         pcp->structure = k;
         structure = pcp->structure;
         pcp->words = k;
         pcp->subgrp = k;
         pcp->submlg = pcp->subgrp - lg;
      }

      pcp->lastg = lg;
      y[pcp->clend + current_class] = pcp->lastg;

      /* deallocate the renumbering table */
      p1 = -y[dgen];
      y[p1] = 0;
      return;
   }

   /* class 1 */

   pcp->lastg = 0;
   for (i = 1; i <= ndgen; i++) {
      if ((j = y[structure + i]) == 0) {
         /* defining generator i is trivially redundant */
         y[dgen + i] = 0;
         if (y[dgen - i] < 0) {
            /* deallocate old inverse */
            p1 = -y[dgen - i];
            y[p1] = 0;
            /* set new inverse trivial */
            y[dgen - i] = 0;
         }
      } else if (j < 0) {
         /* defining generator i is redundant with value pointed
            to by -y[structure + i] */
         y[dgen + i] = y[structure + i];
         p1 = -y[dgen + i];
         length = y[p1 + 1];
         y[p1] = dgen + i;

         /* renumber value of defining generator i */
         for (k = 1; k <= length; k++) {
            l = FIELD2(y[p1 + k + 1]);
            y[p1 + k + 1] += y[dgen + l] - l;
         }

         if (y[dgen - i] < 0) {
            /* i inverse occurs in a defining relation, so recompute
               the inverse and set up header block for inverse */
            y[lused + 1] = dgen - i;
            y[lused + 2] = length;

            /* set up inverse */
            for (j = 1; j <= length; j++) {
               k = y[p1 + j + 1];
               y[lused + 2 + j] = PACK2(prime - FIELD1(k), FIELD2(k));
            }

            /* deallocate old inverse */
            p1 = -y[dgen - i];
            y[p1] = 0;
            y[dgen - i] = -(lused + 1);
            pcp->lused += length + 2;
            lused = pcp->lused;
         }
      } else {
         /* i is an irredundant generator */
         pcp->lastg++;
         y[dgen + i] = pcp->lastg;
         /* note that its weight is set to be 1 */
         y[structure + pcp->lastg] = PACK3(1, 0, i);

         /* check if inverse of i is required */
         if (y[dgen - i] < 0) {
            /* yes, so renumber previously set up inverse */
            p1 = -y[dgen - i];
            y[p1 + 2] += pcp->lastg - i;
         }
      }
   }

   if (pcp->lastg < 1) {
      text(7, prime, 0, 0, 0);
      pcp->complete = 1;
      pcp->cc = 0;
   } else {
      y[pcp->clend + 1] = pcp->lastg;
      pcp->submlg = pcp->subgrp - pcp->lastg;
   }
}

quality83%

¤ 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.