A question about template recursion.

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!

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!

Last edited on

Topic archived. No new replies allowed.