3. Template Meta Programmierung: Quadratwurzel (use of undefined type error)

Template Meta Programmierung: Quadratwurzel (use of undefined type error)

  • D

    Ich habe mich mal wieder ein bisschen mit der Template Programmierung in C++ beschäftigt. Dabei hab ich versucht die Quadratwurzel einer natürlichen Zahl (Natural) wie folgt zu ermitteln:

    typedef unsigned int natural_value_type;

	template <typename NaturalHolder>
	struct Natural
	{
		typedef natural_value_type value_type;
		static const value_type value = NaturalHolder::value;
	};

	template <natural_value_type Value>
	struct N
	{
		typedef natural_value_type value_type;
		static const value_type value = Value;
	};

	template <typename NaturalHolder>
	struct SquareRoot;

	template <natural_value_type Value>
	struct SquareRoot< Natural< N< Value * Value > > >
	{
		typedef natural_value_type value_type;
		static const value_type value = Value;
	};

    Wenn ich jetzt versuche den Quadratwurzeltypen zu instanzieren, bekomme ich die Fehlermeldung

    error C2027: use of undefined type 'tsm::natural::SquareRoot<NaturalHolder>'
1>        with
1>        [
1>            NaturalHolder=tsm::natural::Natural<tsm::natural::N<1>>
1>        ]
1>        .\main.cpp(13) : see reference to class template instantiation 'tsm::natural::Natural<NaturalHolder>' being compiled
1>        with
1>        [
1>            NaturalHolder=tsm::natural::SquareRoot<tsm::natural::Natural<tsm::natural::N<1>>>
1>        ]

    Instanzierung erfolgt folgendermaßen

    typedef Natural< SquareRoot< Natural< N<1*1> > > >	var;
var instance;

    Ich verwende MS Visual C++ 2008 Express Edition.

    Ich hatte schon vermutet, dass eine solche Instanzierung fehlschlagen könnte (die Lösung kam mir einfach zu einfach vor). Als Alternative könnte ich natürlich das Newton-Verfahren implementieren, allerdings besteht bei mir noch eine kleine Hoffnung, dass jemand hier im Forum, einen eleganten Weg (vllt ähnlich wie mein erster Versuch, also direkt über partielle Spezialisierung) kennt.

    Ich freue mich über jeden Ratschlag und Tipp, selbst, wenn der nur beinhaltet, dass das so in C++ nicht machbar ist.

    Gruß
    Don06

    0
  • O

    das Problem ist folgende Definition:

    N< Value * Value >

    und folgender Aufruf:

    N<1*1>

    Die Fehlermeldung sagt übrigens ganz genau was abgeht:

    tsm::natural::Natural<tsm::natural::N<1>>

    N<1*1> = N<1>

    Der Trick mit dem Newton Verfahren wird unter umständen auch nicht funktionieren, da manche Compiler probleme mit der ganzzahldivision bei konstanten ausdrücken haben.

    Was funktionieren kann ist ein Bisektionsverfahren, da reicht aber eine einfache spezialisierung nicht aus.

    0
  • W

    Hallo Don06,

    nach einigen Probieren ist es mir mit dem VS9 (VS 2008) und dem Heron-Verfahren gelungen. Meine Lösung sieht so aus:

    #include <iostream>

namespace sqrt_detail
{
    template< unsigned int A, unsigned int X0, unsigned int AX >
    struct HeronStep
    {
        static const unsigned int x1 = (X0 + AX)/2;
        static const unsigned int value = HeronStep< A, x1, A/x1 >::value;
    };
    template< unsigned int A, unsigned int X0 >
    struct HeronStep< A, X0, X0 >
    {
        static const unsigned int value = X0;
    };
}

template< unsigned A >
struct SquareRoot
{
    static const unsigned int value = sqrt_detail::HeronStep< A, 2, A/2 >::value;
};

int main()
{
    using namespace std;
    cout << SquareRoot< 16 >::value << endl;
    return 0;
}

    Der VC8 schluckt das so nicht, da er die partielle Spezialisierung nicht beherrscht. Das ist doch ein Anlass für ein Update - oder.

    Mit dem Comeau C/C++ 4.3.10.1 compiliert es ebenfalls.

    Gruß
    Werner

    0
  • G

    *hier stand mist.*

    0
  • D

    otze schrieb:

    Der Trick mit dem Newton Verfahren wird unter umständen auch nicht funktionieren, da manche Compiler probleme mit der ganzzahldivision bei konstanten ausdrücken haben.

    Was funktionieren kann ist ein Bisektionsverfahren, da reicht aber eine einfache spezialisierung nicht aus.

    Der Kompiler von Visual Studio C++ 2008 EE hat mit der Division, soweit ich das sehe, keine Probleme. Ich habe dennoch, allerdings nur aus Spass, eine Variante geschrieben, die ohne Division die ganzzahlige Quadratwurzel einer Zahl zieht. Dabei wird die entsprechende Wurzel "gesucht". Der Algorithmus sieht in C++ so aus:

    unsigned int square_root(unsigned int x)
{
	static const std::size_t START_BIT = (sizeof (x) * CHAR_BIT / 2) - 1;

	unsigned int result = 1 << START_BIT;
	for (int bit_pos = START_BIT; bit_pos >= 0; --bit_pos)
	{
		if (x < result * result)
			result &= ~(1 << (bit_pos));
		if (bit_pos != 0)
			result |= 1 << (bit_pos - 1);
	}
	return result;
}

    Das ganze dann auf Templates umgemünzt:

    namespace sqrt_detail
{	
	template <unsigned int CurrentBit, unsigned int X>
	struct FindSqrt
	{
		static const unsigned int previous = FindSqrt< CurrentBit + 1, X >::value;

		static const unsigned int new_bit = 1 << (CurrentBit - 1);
		static const unsigned int delete_bit = (X < previous * previous) ?
			~(1 << CurrentBit) : ~0;

		static const unsigned int value = (previous | new_bit) & delete_bit;
		static const unsigned int result = FindSqrt< CurrentBit - 1, X >::result;
	};

	static const unsigned int UINT_BITS = sizeof (unsigned int) * CHAR_BIT;
	static const unsigned int START_BIT = (UINT_BITS >> 1);

	template <unsigned int X>	
	struct FindSqrt< START_BIT, X >
	{
		static const unsigned int value = 1 << (START_BIT - 1);
		static const unsigned int result = FindSqrt< START_BIT - 1, X >::result;
	};

	template <unsigned int X>
	struct FindSqrt< 0, X >
	{
		static const unsigned int previous = FindSqrt <1, X>::value;
		static const unsigned int delete_bit = (X < previous * previous) ? ~1 : ~0;
		static const unsigned int result = previous & delete_bit;
	};
}

template <unsigned int X>
struct SquareRoot
{
	static const unsigned int result = 
		sqrt_detail::FindSqrt< sqrt_detail::START_BIT, X >::result;
};

    Der Code selbst könnte wohl einen Preis in Obfuscated C++ gewinnen, wenn man nicht an dem Namen erkennen könnte, was er bezwecken soll. Ich werde daher, denke ich, Werner Salomons Variante bevorzugen. Hier nochmal ein Dankeschön für deine Bemühungen.

    Gruß
    Don06

    0
  • B

    Dann will ich einfach nochmal was hinterherschieben, hatte auch kurz rumprobiert (TMP ist schon interessant..). Im VS2005 stürzt dann aber der Optimierungscompiler ab und ich bekomme einen internen Compilerfehler. Naja, kann mir jemand sagen, ob/was ich hier falsch gemacht hab?:

    template<int i, int root> struct SquareRootEx
{
	static const int value = (root*root>=i)? root : SquareRootEx<i,root+1>::value;
};

template<int i> struct SquareRoot
{
	static const int value = SquareRootEx<i,1>::value;
};

int main()
{
	std::cout << SquareRoot<49>::value << std::endl;
}

    So wie ich Templates verstehe, dürfte nur bis root==7 aufgelöst/instantiiert werden, der Compiler instantiiert aber anscheinend bis 494 und stürzt dann ab.

    0
  • ?

    Badestrand schrieb:

    static const int value = (root*root>=i)? root : SquareRootEx<i,root+1>::value;

    Der Compiler wertet hier immer alle Ausdrücke aus, daher instanziert er, bis ihm die Luft ausgeht.
    Versuche die Abbruchbedingung über ne Spezialisierung hinzubekommen.

    0
  • C
    Mod

    Badestrand schrieb:

    So wie ich Templates verstehe, dürfte nur bis root==7 aufgelöst/instantiiert werden,

    Ein verständlicher Irrtum. Wenn du die Instantiierungskette unterbrechen willst, musst du Spezialisierung einsetzen. ?: wertet zwar nur entweder den 2. oder 3. Operanden aus, aber Auswertung eines Ausdrucks ist nicht identisch mit Instantiierung. Die Instantiierung ist schon deshalb notwendig, um den Typ des Ausdrucks herauszufinden. Wenn mich mein Gedächtnis nicht täuscht, soll das im nächsten Standard etwas anders gehandhabt werden.

    0
  • ?

    camper schrieb:

    ?: wertet zwar nur entweder den 2. oder 3. Operanden aus, aber Auswertung eines Ausdrucks ist nicht identisch mit Instantiierung.

    Somit ist meine Wortwahl von vorhin nicht ganz richtig ...

    Edit: Irgendwie hab ichs heute mit dem zitieren ...

    0
  • D

    Naja, es wurde ja bereits alles gesagt. Dann hier mal eine funktionierende Lösung.

    template<int i, int root, bool found = root * root >= i> 
struct SquareRootEx;

template<int i, int root> 
struct SquareRootEx <i, root, true>
{ 
    static const int value = root; 
}; 

template<int i, int root> 
struct SquareRootEx <i, root, false>
{ 
    static const int value = SquareRootEx<i,root+1>::value; 
}; 

template<int i> struct SquareRoot 
{ 
    static const int value = SquareRootEx<i,1>::value; 
};
    0
  • B

    Hey cool, danke euch 🙂 👍 Im Nachhinein und mit den Erklärungen leuchtet's ein, aber vorhin hab ich mir 'nen Wolf gegrübelt.. 😃

    0
Anmelden zum Antworten