I start an evening class in C++ OOP in October and thought I’d brush up on my limited programming skills. I chose to write a couple of classes that will let me do arithmetic over finite fields mod p.
With the bother of getting this working I now have two important classes, a simple integer mod p class (Zp) and a second class for polynomials of varying degree in the integral domain over Zp, (Zp[x])
I have functions for long division and a couple ofquick-ish routines for checking for irreducible polynomials, and I would like to extend this to the problem of polynomials over field extensions.
In basic form, with any polynomial in the domain Zp[x] that is irreducible I can form another field F(x) by doing arithmetic modulo this polynomial. I would like to know whether extending this process an unknown (at compile time) number of times is possible using c++ templates. I have done a little basic reading on templates but even thinking about precoding in say, four or five layers of this process in typedefs“just in case” – (which would keep the degrees of polynomials small, also!) causes anguish – Though Is using the template long-hand for all foreseen types at compile time the only way to efficiently get the depth of recursion?
Let me put it another way.
I would need a polynomial class, say, IDPoly, which would need an array of “fieldElement types” ( my coefficients) which depend on a “shallower” IDPoly class with a separate reference to a single IDPoly (A) as an irreducible (in a Field class) made from another (less recurred)IDPoly (B)over a smaller field , and so on and so on. etc,. I would need to separate fieldElement and IDpoly because (exact) division is not defined for the IDPoly type.
The base condition would terminate in the “Field” type: - terminating with the IDPoly being an array of int modulo p, and its irreducible of type IDPoly, an “int” , would simply be a prime number. (this would be done by specialisation or overriding the usual template)
I apologise for the scrappy outline of the quack code below. (I know that the stuff in the angle brackets is wrong, but I aim to show how this links together) This question is a conceptual one because coding all this for nothing would be a huge waste of time.
So I would have:
Template<class FieldElement>
class IDPoly
{
//array of fieldElement, and functions for arithmetic and Remainder on longdivision, testing for irrreducibles etc.
}
//as well as
Template<class Field, class IDPoly>
class FieldElement
{
//single member is a polynomial of form IDPoly for arithmetic modulo the irreducible polynomial in class “Field”, all standard arithmetic defined and valid here, to use as coefficients in recurred IDPoly
}
//And finally
Template<class IDPoly>
class Field
{
//an irreducible polynomial in IDPoly form.
}
//I would also specialise Field by using
template<>
Field<int>
{
Int itsIrreducible; //(a prime number)
}
An IDPoly with a degree of zero and only one coefficient is a good place to start with integers mod p.
So apologies, but onto the question proper.
I understand from a little light reading that instead of preparing many layers of recursion (more than I need) I may simply use template template parameters and drop the type in the angle brackets for the template template parameter. then I only need to use the keyword "typename" and dont have to qualify the types as <int> or whatever.
So I can specialise my other templates to templates like
template<template <typename> class myClass1, template <typename,typename> class myClass2 >
class myClass3
{
…
};
is it possible to additionally (and seperately) specialise these to my three classes,
template<template <> class IDPoly<FieldElement>, template <> class Field<IDPoly> >
class FieldElement
{
...
}
so if I partially specialise my classes in this manner, is the termination condition of
Template<>
class Field<int>
enough to let the compiler know the types at compile time? Or should I find some other way to go forward? I would have to declare my variables in a recursive manner if this is enough.
I doubt I’ll ever need more than my base of <int> and three layers over the top, ever. I just will find coding in the typedef’s for these nesting templates hard enough, without the debug info I would have to decode with errors I make as well.
Please bear in mind I’m no expert, a simple yes or no as an answer would be great but could anyone help me with an alternative? A simple tree list structure looks ok but I am not sure of the overhead I would acquire using the polynomial arithmetic in such a case. Also I have already tried multidimensional arrays, but as the polynomials in my classes are now sparse without zero coefficients (to save memory) this has become a nightmare.
Any good suggestions would be more than appreciated!