CoCoA » CoCoALib

The real candidates are (B) and (C) -- I interpret these as meaning 16 bits and 32 bits.

Option (A) would limit exponents to 255; this is fine for many computations (esp. with many indeterminates), but is too low for general use.

Options (D) and (E) are necessary only if exponents reach 2^32 or higher. I think it is extremely unlikely that such high exponents will ever occur in general use. CoCoALib does also offer PPMonoidEvZZ for unlimited exponents (presumably with a significant speed and space penalty).

The real question is how likely is one to encounter degrees greater than 2^16, and how onerous is the speed/space penalty of 32-bit exponents.

Regarding the space penalty, let me give an example. Imagine we are computing in a polynomial ring with 6 indeterminates and coefficients in a small finite field. I shall assume use of the most compact representation, namely DistMPolyInlFpPP. Assuming that the representation of each summand contains no "holes" (i.e. unused chunks of memory), with 16-bit exponents each summand occupies 4+6*2+8=24 bytes of memory, whereas with 32-bit exponents each summand occupies 4+6*4+8=36 bytes of memory. So the space penalty is at most 50% when using 32-bit exponents compared to 16-bit exponents. Of course, the (relative) penalty will be greater if there are more indeterminates, and less if there are fewer; but in any case the relative penalty will never reach 100%.

Note that I have chosen the setting which most favours the smaller exponents; with any other representation, the (relative) space penalty would be much less, probably to be point of becoming negligible.

I ran the (old) benchmark set (inside src/server/).

There was no real difference in speed between a compilation using (B) and one using (C).
In one case (B) was about 3% faster; there were a few cases where the relative speed difference was about 2%, but in general the difference was only about 1%.

After looking through the CoCoAServer source code, it seems that in the computations modulo 32003 the polynomial ring used was indeed a RingDistrMPolyInlFpPP -- i.e. the situation which should exhibit the most evident difference in computation times.

At this point I propose: we make (C) the definition in the standard distribution, adding somewhere in the documentation (where exactly?) that if there are mild problems of space, one can try recompiling using definition (B); or if the exponent limit of 4*10^9 is too low then one can use definition (D).

JAA has modified config.H so that SmallExponent_t is now unsigned int.

Waiting for confirmation from Anna that the change does not incur any significant speed penalty. If she confirms, we can close this issue.

Anna and John discussed the matter (in the light of Soeger+Bruns's experience).

The current proposal is to leave the default as unsigned int which favours safety over speed/compactness. Clear documentation must be added (where??) explaining how and why someone might want to change the default.

Added a comment in the newly organized installation guides (see INSTALL-advanced.txt). There is no perfect answer to this issue.

Closing this issue.