
#include <DivMask.H>
Collaboration diagram for CoCoA::DivMaskRule:
Public Member Functions  
DivMaskRule (const DivMaskRuleBase *DMRPtr)  
const DivMaskRuleBase *  operator> () const 
Allow const member fns to be called.  
bool  operator== (const DivMaskRule &DMR) const 
Private Attributes  
SmartPtrIRC< const DivMaskRuleBase >  mySmartPtr 
Copyright (c) 2005 John Abbott Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2; with no Invariant Sections, no FrontCover Texts, and no BackCover Texts. A copy of the licence is included in the file COPYING in this directory. User documentation for files DivMask.H and DivMask.C ==================================================== The main reason for creating a [DivMask] is to permit a quick, coarse test of divisibility between power products. The test is coarse because we accept as responses "definitely not divisible" or "possibly". This is a fairly lowlevel concept, and probably of little use to most normal CoCoALib users. If you need to do conduct a great many divisibility tests and think you're interested, read on. Note: currently [DivMask]s cannot be used to ascertain coprimality (see Bugs section). To use [DivMasks]s you must master two concepts. Firstly, the [DivMask] itself is simply a bitset wrapped up in a class. The size of the bitset is determined at compile time. There are various rules for how to set the bits in the bitset, but they all satisfy the guiding principle: if t1 divides t2 then (DivMask(t1) & DivMask(t2)) == DivMask(t1) [i.e. DivMask(t1) is a "subset" of DivMask(t2)] There are no other guarantees: in particular, the converse of the guiding principle does not hold in general. Here is a code snippet to show how [DivMask]s can be used (but it is easier to use [PPWithMask]): DivMaskRule DMR = NewDivMaskEvenPowers(); PPMonoidElem PP1 ... PPMonoidElem PP2 ... ... const size_t nvars = NumIndets(owner(PP1)); vector<SmallExponent_t> expv(nvars); DivMask dm1; DivMask dm2; exponents(expv, PP1); DMR>myAssignFromExpv(dm1, &expv[0], nvars); exponents(expv, PP2); DMR>myAssignFromExpv(dm2, &expv[0], nvars); if (!IsSubset(dm1, dm2)) { /* PP1 does not divide PP2 */ } else { /* PP1 might divide PP2, we do not know for sure */ } You can read the bits held inside a [DivMask] object using this function: bits(dm)  gives readonly access to the bitset inside the [DivMask], the type of the result is [DivMask::mask_t] which is a typedef for a [std::bitset]. There are a few comparison functions on [DivMask] objects: dm1 == dm2  true iff the bitsets are equal dm1 != dm2  false iff the bitsets are equal IsSubset(dm1, dm2)  true if every bit set in dm1 is set in dm2 The type [DivMaskRule] is used to set the bits in a [DivMask] object. The possible function calls are: DMR>myAssignFromExpv(mask, exps, NumIndets)  sets mask according to PP  with exponent vector exps Currently [exps] must be of type [vector<SmallExponent_t>], but this may change. The value of a [DivMask] object may be set any number of times (even using different [DivMaskRule]s on each occasion). Any two [DivMask]s may be compared, but the result is meaningful only if both values were created using the same [DivMaskRule]. You can create five different sorts of rule: DivMaskRule DMR = NewDivMaskNull(); no bit is ever set (relatively fast, but otherwise pretty useless). DivMaskRule DMR = NewDivMaskSingleBit(); if the kth indet appears in the PP then the kth bit is set (indets with index >= DivMask::MaskWidth are ignored completely). DivMaskRule DMR = NewDivMaskSingleBitWrap(); if the kth indet appears in the PP then the Kth bit is set where K = k%DivMask::MaskWidth. DivMaskRule DMR = NewDivMaskEvenPowers(); unlike the above rules, this rule may set several bits for a PP divisible by a "high" power of an indeterminate. For instance, with a mask width of 32 and 4 indets, up to 8 bits can be set for each indet; the actual number of bits set is ceiling(exponent/2). With many indets this rule behaves like SingleBit. DivMaskRule DMR = NewDivMaskHashing(); this rule uses a hashing scheme to allow many bits to be set for each indet even when there are many indets. The number of bits set for an indet with exponent exp is ceiling(sqrt(exp)). Maintainer documentation for files DivMask.H and DivMask.C ========================================================== The class [DivMask] is pretty simple: we don't use a naked [bitset] to ensure that only a [DivMaskRule] can set the value. Use of bitwiseand for modular reduction restricts [MaskWidth] to being a power of 2. There are no member functions, and just one friend function: friend const mask_t bits(const DivMask& dm); The class [DivMaskRuleBase] is an abstract base class with an intrusive reference count: every concrete divmask rule must be derived from this class. The virtual member function [myAssignFromExpv] must be defined in each concrete divmask rule class: it should set the bits in the [DivMask] argument according to the exponents specified in the other two arguments. The virtual member function [myOutput] simply prints the name of the divmask rule  it might be useful durig debugging. The protected member function [myBits] simply allows write access to the [bitset] held inside a [DivMask]; I have to do it this way because friendship is not inherited. The type [DivMaskRule] is just a reference counting smart pointer to a concrete divmask rule class. The entire declarations and definitions of the concrete classes are in the .C file. There is no need for them to be visible in the .H file. The class [DivMaskNullImpl] is quite simple. The class [DivMaskSingleBitImpl] is also very simple. The class [DivMaskSingleBitWrapImpl] is implemented assuming that the mask width is a power of 2. It is quite simple. The class [DivMaskEvenPowersImpl] was (half) written by Anna while under the influence of mindaltering drugs, I reckon. The class [DivMaskHashingImpl] is a bit involved, especially regarding the choice of bits to set. I'm sure the heuristic can be improved (e.g. by actually trying it on some real cases :) Currently the heuristic works like this: let var be the index of the indeterminate, and exp the exponent; the first bit to be set for var will be in position (5*var)%MaskWidth and subsequent bits (for var) will be in positions separated by multiples of step [where step is 2*(var/MaskWidth)+3]. Bugs, Shortcomings, and other ideas =================================== Publicly visible use of [SmallExponent_t] is most unfortunate; how to fix it? Is the restriction on [DivMask::MaskWidth] reasonable? Would we really lose that much speed if any value were allowed? Chances are that the only interesting values are 32, 64 or 128 (which are indeed all powers of 2). COPRIMALITY Do we want [DivMask]s to permit a swift coprimality check? Presumably the idea would be that two disjoint DivMask values would imply that the corresponding PPs must be coprime. Another possibility is that the DivMask values are disjoint iff the PPs are coprime; this second possibility would exclude some ideas for implementing DivMasks (for instance [DivMaskSingleBitWrap] and [DivMaskHashing] would be excluded). Documentation too sarcastic. === Old logs === Revision 1.2 2006/08/07 21:23:25 cocoa Removed almost all publicly visible references to SmallExponent_t; changed to long in all PPMonoid functions and SparsePolyRing functions. DivMask remains to sorted out. Revision 1.3 2006/01/18 16:15:16 cocoa Cleaned up DivMask considerably; everything still works, so I'm checking in (and then going home). Revision 1.2 2006/01/17 18:08:01 cocoa Added new DivMask type: DivMaskHashingImpl. Updated DivMask documentation. Revision 1.2 2005/04/19 14:06:05 cocoa Added GPL and GFDL licence stuff.
Definition at line 72 of file DivMask.H.



Allow const member fns to be called.
Definition at line 77 of file DivMask.H. References mySmartPtr. 

Definition at line 78 of file DivMask.H. References mySmartPtr. 

Definition at line 80 of file DivMask.H. Referenced by operator>(), and operator==(). 