al0.h Colin Ramsay (cram@itee.uq.edu.au) 20 Dec 00
ADVANCED COSET ENUMERATOR, Version 3.001
Copyright 2000 Centre for Discrete Mathematics and Computing, Department of Mathematics and Department of Computer Science & Electrical Engineering, The University of Queensland, QLD 4072. (http://staff.itee.uq.edu.au/havas)
This is the header file for Level 0 of ACE; that is, the core enumerator routines.
/****************************************************************** Stdio.h and stdlib.h will be included in all the source files, since all of them include this file.
******************************************************************/
#include <stdio.h> #include <stdlib.h>
/****************************************************************** At some time in the future, we may have to be careful as to the types we use. For the moment we only typedef logical variables, and stick with standard C types for the rest. The `default' environment is 32-bit Unix, although there are a couple of places where the code is 64-bit `compliant' to enable the 4G memory barrier to be breached. (Any possible `problem' areas are commented upon.) We also assume that we are in the C locale, and that we're using the ACSII character set.
******************************************************************/
typedefint Logic; #defineTRUE 1 #defineFALSE 0
/****************************************************************** Is it worth having this as a separate macro? Replace swapp by a global temp?
******************************************************************/
#define SWAP(i,j) { int swapp; swapp=i; i=j; j=swapp; }
/****************************************************************** Macro for access to coset table. i is coset, j is generator (as column number). colptr[j] stores the start address of the block of memory for column j. CT(i,j), with j = 1...ncol, indicates the action of the associated generator (or inverse) of column j on coset i. It contains the coset number if known, otherwise 0 (in column 1, -ve numbers indicate coincidences). Coset #1 is the subgroup. Note the special macros for cols 1/2 to maximise speed (and improve clarity), since these cols handle coincs & are heavily used.
Depending on the address/data memory model, how address arithmetic is performed, the size of an int, the number of columns, and how much (physical) memory is available, there will be some limit on how many rows the table can have. The table size, in bytes, can exceed 4G. However, since ints are (currently) used throughout, the number of rows is at most 2147483647 (ie, 2^31-1). In practice, arithmetic overflow problems, rounding effects, and guard bands will limit the number of cosets to less than this. We try, as far as possible, to postpone this point by performing some potentially troublesome calculations using floats.
******************************************************************/
extern FILE *fop, *fip; /* All i/o goes through these */
externdouble begintime; /* clock() at start of current interval */ externdouble endtime; /* clock() at end of current interval */ externdouble deltatime; /* duration of current interval */ externdouble totaltime; /* cumulative clock() time, current call */
/****************************************************************** The ETINT macro is used end the current timing interval. It updates the cumulative time for this run & the time of the current interval (ie, since the last begintime). It must be paired with the BTINT macro to set the start the next interval. The new begintime is the old endtime, so our timings will _include_ the time between the ETINT & the BTINT (this can be significant if, for example, hole monitoring is on)!
******************************************************************/
/****************************************************************** Variables to control the (progress-based) messaging feature. Such messages are enabled if msgctrl is set, and are printed every msgincr `actions'; where an action is a definition, a coincidence (possibly) or a stacked deduction (possibly). msgnext keeps track of how far away we are from the next message. Values of 1 for msgctrl are ok, if you want to see everything that happens. However, _lots_ of output can be produced for such small values. If msghol is set, messages include hole information; this feature is independant of the hlimit flag, and is time expensive.
******************************************************************/
/****************************************************************** If messaging is triggered & holes are required, print out the current hole %'age as part of the progress message.
******************************************************************/
/****************************************************************** Logic control variables for current enumeration
******************************************************************/
extern Logic mendel; /* If true, in R-style scan (& close) each relator at each cyclic position for each
coset, instead of just from 1st position */ extern Logic rfill; /* If true, fill rows after scanning */ extern Logic pcomp; /* If true, compress coinc paths */
/****************************************************************** The major user-settable parameters
******************************************************************/
externint maxrow; /* Max number of cosets permitted. May be less than the actual physical table size allocated,
but not more. Should be at least 2! */ externint rfactor; /* R-style `blocking factor' */ externint cfactor; /* C-style `blocking factor' */ externint comppc; /* As new cosets are required, they are defined sequentially until the table is exhausted, when compaction may be done. Comppc sets the percentage of dead cosets in the table before
compaction is allowed. */ externint nrinsgp; /* No. of relators `in' subgroup, for
C-style enumerations. */ externint lahead; /* If 0, don't do lookahead. If 1 (or 3), allow (cheap, R-style) lookahead from current position (or over entire table). If 2 (or 4), allow (expensive, C-style) lookahead over the entire table, a la ACE2 (or from current position). Note that, if mendel set, then cheap is expensive! Lookahead is 1-level, ie, we don't look at
consequences of consequences or stack deductions. */
/****************************************************************** If tlimit >= 0 then the total elapsed time is checked at the end of each pass through the enumerator's main loop, and if it's more than tlimit (in seconds) the run is stopped. Note that tlimit=0 does precisely one pass through the main loop, since 0 >= 0. If there is, e.g., a big collapse (so that the time round a loop becomes very long), then the run may run over tlimit by a large amount. However, we must ensure that when we exit due to too little time, the table is left in a consistent state, so early bail-out is not always possible. Another example is the CL phase, which can take considerable time.
If hlimit >= 0 then ditto for the % of unfilled holes in the coset table. The % of holes is calculated by going thro the table, so this can be a time-expensive option; we check on each pass thro the loop. The impact is minimised if rfactor/cfactor blocking factors are `large'. Note that the utility of this is under review, since the % of holes tends to be static or to drift down.
******************************************************************/
externint tlimit, hlimit;
/****************************************************************** Level 0 keeps track of the number of passes through the state- machine's main loop in lcount. If llimit > 0, then the enumerator will exit after (at most) llimit passes. You need to use this in conjunction with the machine's flow chart, else the results might surprise (annoy, frustrate) you!
******************************************************************/
externint llimit, lcount;
/****************************************************************** The numbers of: current active cosets; maximum number of cosets active at any time; total number of cosets defined.
******************************************************************/
externint nalive, maxcos, totcos;
/****************************************************************** ctail (chead) is the tail (head) of the coincidence queue; we add at tail & remove at head. During coincidence processing CT(high,2) (aka COL2(high)) is used to link the coincidence queue together. CT(high,1) (aka COL1(high)) contains minus the equivalent (lower numbered) coset (the minus sign flags a `redundant' coset). The queue is empty if chead = 0. Primary coincidence are always processed immediately, and processing continues until _all_ secondary coincidences have been resolved. We _may_ discard deductions in coincidence processing, but never coincidences. The only place where coincidences could be `discarded' is in table compaction; however, this is never called when the queue is non- empty, ie, during coincidence processing.
******************************************************************/
externint chead, ctail;
/****************************************************************** If pdefn>0, then gaps of length 1 found during relator scans in C-style are preferentially filled (subject to the fill-factor, discussed below). If pdefn=1, they are filled immediately, and if pdefn=2, the deduction is also made (of course, these are also put on the deduction stack too). If pdefn=3, then the gaps are noted in the preferred definition list (pdq). Provided a live such gap survives (and no coincidence occurs, which causes the pdq to be discarded) the next coset will be defined to fill the oldest gap of length 1. On certain examples, e.g., F(2,7), this can cause infinite looping unless CT filling is guaranteed. This can be ensured by insisting that at least some constant proportion of the coset table is always kept filled & `tested'. This is done using ffactor. Before defining a coset to fill a gap of length 1, the enumerator checks whether ffactor*knh is at least nextdf and, if not, fills rows in standard order. A good default value for ffactor (set by Level 1) is int((5(ncol+2))/4). Warning: using a ffactor with a large absolute value can cause infinite looping. However, in general, a `large' positive value for ffactor works well. Note: we'd `normally' expect that nextdf/knh ~ ncol+1 (ignoring coincidences, which confuse things), so the default value of ffactor `encourages' this ratio to grow a little.
Note: tests indicate that the effects of the various pdefn/ffactor combinations vary widely. It is not clear which values are good general defaults or, indeed, whether any of the combinations is _always_ `not too bad'.
******************************************************************/
externint pdefn; externfloat ffactor;
/****************************************************************** The preferred definition queue (pdq) is implemented as a ring, dropping earliest entries (see Havas, "Coset enumeration strategies", ISSAC'91). It's size _must_ be a power of 2, so that the NEXTPD macro can be fast (masking the ring index with 1...1 to cycle from pdsiz-1 back to 0). The row/col arrays store the coset number/generator values. Entries are added at botpd and removed at toppd. The list is empty if botpd = toppd; so, in fact, the list can store only pdsiz-1 values!
******************************************************************/
/****************************************************************** The deduction list is organised as a stack. Deductions may be discarded, and discards are flagged by disded, as they may impact the validity of a finite index. (If deductions are not processed, under some circumstances the result may be a multiple of the actual index.) We only `log' discards if we try to stack them & can't (ie, stack full) or if they're `potentially' meaningful (eg, if we _know_ the table has collapsed, and index=1, then stacked deductions are _not_ meaningful). The stack is empty if topded=-1, and dedsiz is the available stack space.
Note that if we define N.g = M, and thus M.G = N, we only stack N/g. When we unstack, we test both N/g (picking up M) & M/G. We ignore cosets that have become redundant, but we do nothing (too expensive) about duplicates (either direct or inverted); these will scan fast however, since `nothing' happens.
We test various stack-handling options by the dedmode parameter. 0 means do nothing (except discard individually if no space), 1 means purge redundancies off the top (on exiting _coinc()), 2 means compact out all redundancies (on exiting _coinc()), and 3 means throw away the entire stack if it overflows. Mode 4 is a fancy mode; every time the stack overflows we call a function to `process' it, on the basis that we're prepared to work _very_ hard not to throw anything away. The particular function used is subject to review; currently, we expand the space available for the stack and move the old stack, compressing it as it's moved by removing redundancies. In practice this works very well, and is the default dedn handling method; it means that we always process all deductions. In the presence of collapses, a judicious choice of dedsize & the use of Mode 0 will often be faster however.
Discussion: dedsiz is usually some `small' value, as the active stack is normally small and shrinks back to empty rapidly. Since the enumerator is `clever' enough to `notice' dropped/unprocessed deductions & take appropriate action when checking a finite result, it makes sense in some circumstances to drop excessive deductions. In particular, if we have a lot of coincidences in al0_coinc, and thus a big stack (esp. one that doesn't shrink quickly), it is much faster to ignore these and tidy up at the end (since most of the stack is redundant, duplicate or yields no info). This is somewhat similar to the adaptive flag of ACE1/2. (An alternative option would be to do a C-lookahead at the top of _cdefn() if ever dedns have been discarded, but this could be very expensive.)
******************************************************************/
/****************************************************************** Macro to save a deduction on the stack. Note the function call in mode 4, if the stack overflows; this can be v. expensive if the stack overflows repeatedly (ie, a big collapse). It's a question of which is faster; trying hard _not_ to discard deductions, or discarding them & having to run a checking phase at the end of an enumeration. In practice, _dedn() doubles the stack space at each call, so it's not actually called very often!
******************************************************************/
/****************************************************************** We note where generators occur in bases of relators, so that definitions can be applied at all essentially different positions (edp) in C-style definitions or in C-style lookahead. edpbeg[g] indexes array edp[], giving the first of the edps in all (noninvolutory) relators for that generator. The edp array stores pairs: the index in array relators where this generator occurs; the length of the relator. edpend[g] indexes the last edp pair for generator g. If there are no such positions edpbeg[g] < 0. Generators are in terms of column numbers, so noninvolutory generators have two sets of entries. Generators which are to be _treated_ as involutions have only one column & one set of entries. The edp of a relator xx (or x^2, or XX, or X^2) where x is to be treated as an involution is _not_ stored, since it yields no information in a C-style scan.
******************************************************************/
externint *edp, *edpbeg, *edpend;
/****************************************************************** Group generators (aka coset table columns):
******************************************************************/
externint ncol; /* Number of columns in CT. Involutions (usually) use only 1 column, noninvolutary
generators 2. */ externint **colptr; /* Array of pointers to CT columns */ externint *col1ptr, *col2ptr; /* Special pointers for cols 1 & 2 */ externint *invcol; /* Table mapping columns to their inverse
columns, length ncol+1. */
/****************************************************************** Group relators:
******************************************************************/
externint ndrel; /* Number of relators */ externint *relind; /* relind[i] is the start position of ith
relator in array relators[] */ externint *relexp; /* relexp[i] is exponent (ith rel'r) */ externint *rellen; /* rellen[i] is total length (ith rel'r) */ externint *relators; /* The relators, fully expanded and
duplicated for efficient scanning */
externint nsgpg; /* Number of subgroup generators */ externint *subggen; /* All the subgroup generators */ externint *subgindex; /* Start index of each generator */ externint *subglength; /* Length of each generator */
extern Logic sgdone; /* ?have they been applied to coset #1 */
/****************************************************************** knr is the coset at which an R-style scanning against relators is to commence; all previous (active) cosets trace complete cycles at all relators. If knr == nextdf _and_ the table in hole-free, then a valid index has been obtained. knh is the coset at which a search for an undefined coset table entry is to begin; all previous cosets have all entries in their row defined. If C-style definitions are being (or will be) made, all previous cosets have all entries in their row defined, and all consequences traced or definitions stacked. (In fact, _all_ non-zero entries in the table have been traced or stacked.) If knh == nextdf _and_ _all_ definitions have had their consequences processed, then a valid index has been obtained. Note that currently knh is only changed in C-style, since it is important that the property referred to above is preserved. This effectively overloads the meaning of knh; it should be replaced by separately maintained knh & knc variables. This would make R-style & C-style symmetric; much nicer! It would also allow us to differentiate between the definition strategy, the scanning strategy, and the termination condition.
nextdf is the next sequentially available coset. Normally 1 <= knr < nextdf and 1 <= knh < nextdf; the value of knr vis-a-vis knh is not fixed. If knr/knh hit nextdf, then we're done (modulo some other conditions). Note that 1 <= nalive < nextdf <= maxrow+1. If nextdf = maxrow+1 and we want to define a new coset, then we've overflowed; we lookahead/compact/abort.
******************************************************************/
externint knr, knh, nextdf;
/****************************************************************** Externally visible functions defined in enum.c. Note that it is not strictly necessary to make _apply() visible across files, since it's only called from within enum.c, but we do anyway, since a smart-arse Level 0 user might like to use it.
******************************************************************/
int al0_apply(int, int*, int*, Logic, Logic); int al0_enum(int, int);
/****************************************************************** Externally visible functions defined in coinc.c
******************************************************************/
int al0_coinc(int, int, Logic);
/****************************************************************** Externally visible functions defined in util0.c
******************************************************************/
/****************************************************************** During code development/testing and when experimenting with an enumeration's parameters, it is often helpful to monitor how many times a particular situation occurs. If the AL0_STAT (ie, statistics) flag is defined, a statistics gathering & processing package is compiled into the code. If the flag is not defined, none of the macros generate any code, and so there is no overhead. To add an item of interest, you have to add an "extern int x;" declaration below, add an "int x;" definition in enum.c, add "INCR(x);" statements where appropriate (or whatever other processing statements are required), and add "x" to the _statinit() & _statdump() functions.
******************************************************************/
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.
