The main reason for creating a
DivMask is to permit a quick, coarse
test of divisibility between power products -- but before you read on, you
might like to consider using
PPWithMask instead, which offers
essentially the same advantages with a *much more convenient interface*.
We say that
DivMasks permit a "coarse" test because we accept as
responses definitely not divisible or possibly divisible (but
further checks must be conducted to decide for certain).
For example the radical of a PP .... (WORK-IN-PROGRESS)
a fairly low-level concept, and probably of little use to most normal
CoCoALib users. If you need to do conduct a great many divisibility tests
(between power products) and think you're interested, read on (assuming you
have already decided that
PPWithMask does not fulfill your needs).
DivMasks cannot be used to ascertain coprimality (see Bugs section).
DivMasks you must master two concepts. Firstly, the
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 following guiding principle:
(DivMask(t1) & DivMask(t2)) == DivMask(t1)
DivMask(t1)is a "subset" of
There are no other guarantees: in particular, the converse of the guiding principle does not hold in general.
You can create five different sorts of
WORK-IN-PROGRESS: explain what a DivMaskRule is
DivMaskRuleis required and you know you won't use it)
k-th exponent in the PP is strictly positive then the
k-th bit is set: at most a single bit is used for each indeterminate, indets with
index >= DivMask::ourMaskWidthare ignored completely.
k-th exponent in the PP is strictly positive then the
k%DivMask::ourMaskWidth-th bit is set: all indets are taken into account, and each bit is used for a set of indeterminates. This implementation is good when we have many indeterminates in supposedly sparse PPs. (So far I don't have good examples with more than 2*ourMaskWidth indeterminates)
ceiling(exponent/2). This implementation is good when we have few indeterminates with high exponents (e.g. Buchberger's algorithm). It is equivalent to
SingleBitWrapImplif the number of indets is bigger than
ceiling(sqrt(exponent)). Supposedly the implementation works well in all cases (e.g. few indets and high degrees, or many indets and low degrees) For indet x the first bit set has index
x%ourMaskWidth, and in general the k-th bit set has index
(x + k*hash2)%ourMaskWidth. (See code for definition of hash2)
DivMaskRule is used to set the bits in a
The possible function calls are:
DMR->myAssignFromExpv(mask, exps, NumIndets)-- sets mask according to PP with exponent vector exps. Currently the parameter
expsmust be of type
vector<SmallExponent_t>, but this may change. This function might be quite expensive and its cost depends on the
DivMaskRule, but this is not a problem if it is called much more rarely than
The value of a
DivMask object may be set any number of times (even using
DivMaskRules on each occasion). Any two
DivMasks may be
compared, but the result is meaningful only if both values were created
using the same
There are a few comparison functions on
DivMask objects -- these are
guaranteed to be very fast and independent of the
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
You can read the bits held inside a
DivMask object using this function:
bits(dm)-- gives read-only access to the bitset inside the
DivMask, the type of the result is
DivMask::mask_twhich is a typedef for a
DivMask is pretty simple: we don't use a naked
bitset to ensure that only a
DivMaskRule can set the value.
Use of bitwise-and for modular reduction restricts
being a power of 2. There are no member functions, and just one
friend function (giving read access to the bitset):
friend const mask_t bits(const DivMask& dm);
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
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 during debugging. The protected member
DivMaskRuleBase::myBits simply allows write access to the
bitset held inside a
DivMask value; I have to do it this way
because friendship is not inherited.
DivMaskRule is just a reference counting smart pointer to an
instance of 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.
DivMaskNullImpl is quite simple.
DivMaskSingleBitImpl is also very simple.
DivMaskSingleBitWrapImpl is implemented assuming that the mask
width is a power of 2. It is quite simple.
DivMaskEvenPowersImpl was (half) written by Anna while under the
influence of mind-altering drugs, I reckon.
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 as follows.
We consider each indeterminate in turn:
var be the index of the indeterminate, and
exp the exponent, then
the total number of bits to be set is
the first bit to be set will be in position
and subsequent bits will be in positions separated by multiples
of step (where step is
24*floor(var/ourMaskWidth)+13 -- this was chosen because
it happened to make
DivMaskHashingImpl perform well in the CoCoALib tests).
Publicly visible use of
SmallExponent_t is most unfortunate; how to fix it?
operator<= for DivMasks, to do the same as IsSubset??
ourMaskWidth be 32 or 64?
Surely most current processors are 64 bit now?
Is the restriction that
DivMask::ourMaskWidth be a power of 2 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
COPRIMALITY: Do we want
DivMasks 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
DivMaskHashing would be excluded).
Documentation is too sarcastic.