Quelle tails.c Sprache: C

/****************************************************************************
**
*A  tails.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"

#define BOTH_TAILS 0
#define NEW_TAILS 1
#define COMPUTE_TAILS 2

/* introduce tails for the class work_class part of class pcp->cc */

/* end_weight is never used, and always equal to 1.
   We hijack it as follows: if end_weight<0, then we actually want to compute
   the lower central series up to class -end_weight, by adding p-powers but not
   commutators as tails. */
void tails(int type,
           int work_class,
           int start_weight,
           int end_weight,
           struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int structure = pcp->structure;
   register int class_end = pcp->clend;
   register int lastg = pcp->lastg;
   register int current_class = pcp->cc;
   register int nmr_at_start = pcp->lastg;
   register int final_class = work_class - 1;
   register int start = y[class_end + final_class - 1] + 1;
   register int end = y[class_end + final_class];
   register int f, ff;

   register int s, bound;

   register int value;
   register int p1;
   Logical equal = FALSE;

#include "access.h"

   /* recover desired l.c.s. class */
   int lcs_class;
   int lcs_degree[end+1];
   if (end_weight < 0) {
     int gen;
     lcs_class = -end_weight;
     end_weight = 1;
     /* compute lcs degrees of generators */
     for (gen = 1; gen <= end; gen++) {
       int pointer = y[pcp->structure+gen];
       if (pointer <= 0)
         lcs_degree[gen] = 0; /* pointer<=0 means a redundant generator. Ignore */
       else {
         int u = PART2(pointer), v = PART3(pointer);
         if (u == 0) /* generator */
           lcs_degree[gen] = 1;
         else if (v == 0) /* power relation */
           lcs_degree[gen] = lcs_degree[u];
         else /* commutator relation */
           lcs_degree[gen] = lcs_degree[u] + lcs_degree[v];
       }
     }
   } else
     lcs_class = 0;

   if (pcp->complete != 0 && !pcp->multiplicator)
      return;

   if (type == NEW_TAILS || type == BOTH_TAILS) {

      /* first, introduce left-normed commutators of class
         work_class as generators or pseudo-generators */

      for (f = start; f <= end; f++) {
        /* we're about to add a tail for (f,s) with s a generator. We
           only accept f less than the desired class */
        if (lcs_class && lcs_degree[f]>=lcs_class) continue;

         bound = MIN(f - 1, y[class_end + 1]);
         if (bound > 0) {
            p1 = y[pcp->ppcomm + f];
            for (s = 1; s <= bound; s++) {
               value = y[p1 + s];
               if (value == 0)
                  /* we are inserting generators or pseudo-generators with
                     old entry trivial; if we are inserting pseudo-generators
                     we do not insert one if (f, s) is defining */
                  create_tail(p1 + s, f, s, pcp);
               else if (value < 0)
                  /* old entry was non-trivial so we deallocate it
                     and insert pseudo-generator */
                  extend_tail(p1 + s, f, s, pcp);
               if (pcp->overflow)
                  return;
               lastg = pcp->lastg;
            }
         }
      }

#if defined(GROUP)
#ifndef EXPONENT_P
      /* now, introduce pth powers of final_class generators which
         are pth powers or correspond to defining generators */

      if (final_class == 1)
         ff = 1;
      else {
         ff = end;
         while (PART3(y[structure + ff]) == 0 && --ff >= start)
            ;
         if (ff != end)
            ++ff;
         else
            equal = TRUE;
      }

      if (!equal) {
         for (f = ff; f <= end; f++) {
            /* f is a pth power or corresponds to a defining generator;
               if we are inserting pseudo-generators, we do not insert
               one if f^p is defining */
            value = y[pcp->ppower + f];
            if (value == 0)
               /* we are inserting generators or pseudo-generators
                  with old entry trivial */
               create_tail(pcp->ppower + f, f, 0, pcp);
            else if (value < 0)
               /* old entry was non-trivial so we deallocate it
                  and insert pseudo-generator */
               extend_tail(pcp->ppower + f, f, 0, pcp);
            if (pcp->overflow)
               return;
            lastg = pcp->lastg;
         }
      }
#endif
#endif
   }

   if (type == COMPUTE_TAILS || type == BOTH_TAILS) {

      /* calculate pth powers of class final_class generators which
         are commutators by doing the appropriate collections */
      if (final_class != 1)
         calculate_tails(final_class, pcp);
      if (pcp->overflow)
         return;
   }

   pcp->submlg = pcp->subgrp - lastg;

   if (work_class == current_class) {
      /* note first pseudo-generator and number of actual generators */
      pcp->first_pseudo = lastg + 1;
      pcp->newgen = pcp->first_pseudo - pcp->ccbeg;
   }

   /* report on the number of new generators added */
   if ((pcp->fullop || pcp->diagn) && type != COMPUTE_TAILS)
      printf("The number of new generators introduced for weight %d is %d\n",
             work_class,
             pcp->lastg - nmr_at_start);
}

#if !defined(TAILS_FILTER)

/* calculate pth powers of class final_class generators which
   are commutators by doing the appropriate collections */

void calculate_tails(int final_class,
                     struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int structure = pcp->structure;
   register int class_end = pcp->clend;

   register int f;
   register int start = y[class_end + final_class - 1] + 1;
   register int end = y[class_end + final_class];

   register int s, s1, s2;
   register int start_class = 1;

   register int a, b;
   register int value;
   register int p1;

#include "access.h"

#if defined(GROUP)

   if (pcp->fullop || pcp->diagn)
      printf("Processing tails for generators of weight %d and %d\n",
             final_class,
             1);

   for (f = start; f <= end; f++) {

#ifdef DEBUG
      printf("Processing generator f = %d, Lused = %d\n", f, pcp->lused);
#endif
      value = y[structure + f];
      a = PART3(value);
      if (a == 0)
         break;
      b = PART2(value);

      /* f is the commutator (b, a);
         calculate the class current_class part of f^p by collecting
         (b^p) a = b^(p-1) (ba); by formal collection, we see that
         the class current_class part of f^p is obtained by subtracting
         (modulo p) the rhs of the above equation from the lhs */

      jacobi(b, b, a, pcp->ppower + f, pcp);
      if (pcp->overflow)
         return;
   }
#endif

   /* calculate the non left-normed commutators of class work_class
      in the order (work_class - 2, 2), (work_class - 3, 3) .. */

   class_end = pcp->clend;
   while (--final_class >= ++start_class) {

      if (pcp->fullop || pcp->diagn)
         printf("Processing tails for generators of weight %d and %d\n",
                final_class,
                start_class);

      start = y[class_end + final_class - 1] + 1;
      end = y[class_end + final_class];
      s1 = y[class_end + start_class - 1] + 1;

      for (f = start; f <= end; f++) {
#ifdef DEBUG
         printf("Processing generator f = %d, Lused = %d\n", f, pcp->lused);
#endif
         s2 = MIN(f - 1, y[class_end + start_class]);
         if (s2 - s1 < 0)
            continue;
         p1 = y[pcp->ppcomm + f];
         for (s = s1; s <= s2; s++) {
            /* insert the class current_class part on (f, s) */
            value = y[structure + s];
            b = PART2(value);
            a = PART3(value);
            if (a == 0)
               a = b;
            else if (pcp->metabelian && PART3(y[structure + f]) != 0)
               continue;

            /* s = (b, a); calculate the class current_class part
               of (f, (b, a)) by collecting (fb) a = f (ba) or the
               class current_class part of (f, (b^p)) by collecting
               (fb) b^(p - 1) = f (b^p);
               since we require only the class current_class part -
               the rest has been computed earlier -  we calculate it
               by subtracting (modulo p) the rhs of the above equation
               from the lhs (proof by formal collection) */

            jacobi(f, b, a, p1 + s, pcp);
            if (pcp->overflow)
               return;
         }
      }
   }
}

#endif

/* insert a new generator or pseudo-generator */

void create_tail(int address, int f, int s, struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int i;
   register int bound;
   register int lastg;

   register int lused = pcp->lused;
   register int structure = pcp->structure;
   register int current_class = pcp->cc;
   register int pointer;

#include "access.h"

   pcp->lastg++;
   lastg = pcp->lastg;
   y[address] = lastg;
   y[structure + lastg] = PACK3(0, f, s) + INSWT(current_class);

   if (pcp->nocset == 0)
      return;

   /* work out the number of occurrences of each defining generator
      in the new generator, storing this in a table above
      y[lused + current_class] -- the entry y[lused + current_class + gen]
      is the number of occurrences of defining generator gen */

   if (is_space_exhausted(current_class + pcp->ndgen, pcp))
      return;

   lused = pcp->lused;
   pointer = find_definition(lastg, lused, current_class, pcp);
   for (i = 1, bound = pcp->ndgen; i <= bound; i++)
      y[lused + current_class + i] = 0;
   for (i = pointer, bound = lused + current_class; i <= bound; i++)
      ++y[lused + current_class + y[i]];

   /* see that the number of occurrences of a defining generator
      passes some test that has been set up in option */
   if (is_genlim_exceeded(pcp))
      return;

   /* the test wasn't passed, so we discard the new generator */
   pcp->lastg--;
   y[address] = 0;
}

/* insert a new pseudo-generator, where the old
   entry was non-trivial and must be deallocated */

void extend_tail(int address, int f, int s, struct pcp_vars *pcp)
{
   register int *y = y_address;

   register int i;
   register int start;
   register int length;
   register int lastg;
   register int lused;
   register int current_class = pcp->cc;

#include "access.h"

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

   lused = pcp->lused;
   start = -y[address];
   length = y[start + 1];

   /* set up new header block with length increased by 1 */
   y[lused + 1] = y[start];
   y[lused + 2] = length + 1;

   /* set up pointer to new block */
   y[address] = -(lused + 1);

   /* deallocate old block by setting its pointer to 0 */
   y[start] = 0;

   /* copy old entry across */
   for (i = 1; i <= length; i++)
      y[lused + 2 + i] = y[start + i + 1];

   pcp->lused += length + 3;
   lused = pcp->lused;

   /* add pseudo-generator */
   pcp->lastg++;
   lastg = pcp->lastg;
   y[lused] = PACK2(1, lastg);
   y[pcp->structure + lastg] = PACK3(0, f, s) + INSWT(current_class);
}

quality87%

¤ Dauer der Verarbeitung: 0.13 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.