Operator überladen für Zahlen und nicht speziell für double

[Andreas_L]

Hi,
sieht im Moment so aus als würde es funktionieren
Also schonmal vielen Dank!!

Mal ne Frage zu einem Code:

template<typename T, typename U>
polynom<T> operator* (const polynom<T>& lhs, const U& rhs)
{
  polynom<T> ret_val(lhs);
  lhs *= rhs;
  return lhs;
}

Musst du nicht ret_val *= rhs nehmen, sonst überschreibst du doch einen Faktor oder nicht?

Kann man das folgende wirklich so kompilieren - greifst du nicht auf private Variablen zu?

template<typename U>
  explicit polynom(const polynom<U>& other)
  : coeff(other.coeff.size())
  {
    coeff_container::const_iterator j(other.coeff.begin());
    for(coeff_container::const i(coeff.begin()), e(coeff.end()); i != e; ++i, ++j)
      *i = static_cast<value_type>(*j);
  }

Viele Grüße

Andreas

[Andreas_L]

Bei mir ist leider noch ein kleines Problem aufgetaucht.

In der Polynomklasse sind u.a. folgende Methoden deklariert:

CPolynom(unsigned short Grad);
CPolynom(void);
CPolynom& operator=(CPolynom& AnderesPolynom); 
template<typename U> 
CPolynom& operator=(const U& Zahl);

Jetzt habe ich eine Matrix als Template aufgebaut, deren Einträge nun also die Polynome enthalten soll. In einer Zeile steht dabei:

template <class Datentyp>
Datentyp CMatrix<Datentyp>::Determinante_Rekursiv()
{
/*....*/
Datentyp Unterdeterminante = 0;
/*...*/
}

Wobei für Datentyp ja das Polynom verwendet wird.
Jetzt hätte ich gedacht, dass von den oberen Operatoren der Zuweisungsoperator CPolynom& operator=(const U& Zahl); verwendet wird. Stattdessen wird aber der Konstruktor aufgerufen, wobei die 0 im als Grad des Polynoms übergeben wird.
Warum macht er das und was kann man dagegen machen - schließlich wird so die Unterdeterminante nicht ordnungsgemäß eingerichtet.

Vielen Dank und viele Grüße

Andreas

[unskilled]

Andreas_L schrieb:

template<typename T, typename U>
polynom<T> operator* (const polynom<T>& lhs, const U& rhs)
{
  polynom<T> ret_val(lhs);
  lhs *= rhs;
  return lhs;
}

Musst du nicht ret_val *= rhs nehmen, sonst überschreibst du doch einen Faktor oder nicht?

Ja, natürlich - flüchtigkeitsfehler 4tw :>

Andreas_L schrieb:

Kann man das folgende wirklich so kompilieren - greifst du nicht auf private Variablen zu?

template<typename U>
  explicit polynom(const polynom<U>& other)
  : coeff(other.coeff.size())
  {
    coeff_container::const_iterator j(other.coeff.begin());
    for(coeff_container::const i(coeff.begin()), e(coeff.end()); i != e; ++i, ++j)
      *i = static_cast<value_type>(*j);
  }

Nein - welche sollen hier private sein?

den letzten post versteh ich nicht - ist mir zu verworren ;o)

und was soll ne determinante oder ne matrix mit nem polynom zu tun haben?
vll sagst du mal, was du genau haben möchtest... (noch mal den post vorm abschicken durchlesen und gedanken zu ordnen kann auch sinn machen!)
CPolynom& operator=(CPolynom& AnderesPolynom); hier fehlt z.bsp. nen const

template<typename U> 
CPolynom& operator=(const U& Zahl);

Sinn?
Polynom = 4; und jetzt? Oo

bb

[Sebastian Pizer]

Andreas_L schrieb:

... Jetzt soll man das Polynom auch mit einer "normalen Zahl" multiplizieren können (short, int, Long, double, float) - hab die Methoden aber bisher nur für double implementiert und gemerkt, dass mein Compiler die Zahlen nicht einfach entsprechend castet ...

Ok, ich rate mal. Dein Code sieht in etwa so aus:

template<typename T>
poly<T> operator*(poly<T> const& p, T factor)
{
  ...
}

und Du wunderst Dich, dass Du ein poly<double> nicht mit einem int multiplizieren kannst, richtig?

Nun, das liegt an der "Template Argument Deduction". Es gibt hier zwei "deduzierbare" Kontexte, nämlich beide Parameter. Der Compiler vergleicht poly<double> mit poly<T> und kommt zum Ergebnis T=double. Dann vergleicht er für den zweiten Parameter int mit T und kommt zum Ergebnis T=int. Da das ein Widerspruch zum ersten Ergebnis ist, schlägt die "Deduktion" fehl und das Template wird ignoriert.

Mir fallen 3 Möglichkeiten ein, wie man das umgehen könnte.

1. So, wie es unskilled gezeigt hat, einen weiteren Template-Parameter einführen. Das könnte aber auch zu Code-Bloat führen (viele fast gleiche Funktionen).

2. Verwendung eines nicht-deduzierbaren Kontexts für den zweiten Parameter. Eine Konvertierung wird dann zugelassen.

template<typename T> struct identity {typedef T type;};

template<typename T>
poly<T> operator*(poly<T> const& p,
  typename identity<T>::type factor)
{
  ...
}

3. Verwendung einer nicht-Template, inline, friend Funktion.

template<typename T>
class poly
{
  ...
  friend poly operator*(poly const& p, T factor)
  {
    ...
  }
  ...
};

Für jeden Typ poly<T> wird somit die Funktion poly<T> operator*(poly<T> const&,T) bereitgestellt, welche durch ADL gefunden werden kann.

[Andreas_L]

ok ich versuchs mal - für mich war das an sich klar^^

Nein - welche sollen hier private sein?

Du hast doch coeff als private deklariert - greifst nun aber einfach darauf zu:

other.coeff.begin());

CPolynom& operator=(CPolynom& AnderesPolynom); hier fehlt z.bsp. nen const

Zum const - das hab ich extra weggelassen weil es da irgendwie Probleme gab: Ich hab beim Polynom auch den []-Operator überladen um auf die Koeffizienten zugreifen zu können. Wenn ich jetzt aber oben ein const reinschreibe konnte ich den []-Operator nicht mehr ohne Compilerfehler verwenden.

und was soll ne determinante oder ne matrix mit nem polynom zu tun haben?
vll sagst du mal, was du genau haben möchtest...

Ich weiß nicht ob du das kennst: Man kann für eine Matrix Eigenwerte und Eigenvektoren ausrechnen. Um die Eigenwerte zu bestimmen brauche ich die Determinante:
Ich muss meine Matrix minus x* Einheitsmatrix nehmen - d.h. auf der Diagonalen steht jeweils nun zusätzlich ein -x. Von der resultierenden Matrix muss ich die Determinante ausrechnen. Das gibt dann ein Polynom n-ten Grades, wenn die Matrix eine nxn-Matrix ist. Die Nullstellen dieses Polynoms sind meine gesuchten Eigenwerte.

Sinn?
Polynom = 4; und jetzt? Oo

Die Methode "Determinante" war urpsrünglich einfach nur für double geschrieben worden. Jetzt wollte ich aber nicht einfach alles neu schreiben sondern hab mir gedacht ich mache ein Template daraus. Das Polynom muss auf 0 gesetzt werden (d.h. einfach ein Polynom 0-ten Grades wobei der übrig gebliebene Koeffizient 0 ist), da später += verwendet wird (sonst habe ich ja ein nicht initialisiertes Polynom auf das ich addiere).

Ist das jetzt etwas klarer geworden - unabhängig davon ob du das mit Eigenwerten kennst oder nicht?

Was muss ich denn dann jetzt machen, damit der Zuweisungsoperator und nicht der Konstruktor verwendet wird?

Viele Grüße

Andreas

Sry Sebastian - war schon am formulieren als du deines abgeschickt hast. Muss zugeben das ich das Polynom gar nicht so variabel bisher gehalten hab. Bisher hab ich einfach double vorgeschrieben ohne Template. Kann das sein, dass deine zweite Möglichkeit dann nicht funktioniert (hab versucht das auf meinen Fall (kein Template) zu übertragen):

template<typename T> struct identity {typedef T type;}; 
CPolynom operator*(typename identity<double>::type & Zahl, CPolynom& Polynom);

aber da erhalte ich nur den Fehler "error C2899: Der Typname kann nicht außerhalb einer Vorlagendeklaration verwendet werden".

[unskilled]

Mir war gerad langweilig - keine Ahnung, ob es dir hilft - aber so meinte ich das ganze und so wie es aussieht, klappt es auch ganz gut^^

Das mit dem Code-Bloat verstehe ich hier nicht ganz (mir ist bekannt, was das heißt - nur seh ich nicht, wo/wieso)...

Ansonsten gefällt mir nur die Warnung wegen der Addition unterschiedlicher Typen nicht so wirklich sind (logischerweise) gleich 3 Warnungen wegen einer Zeile

der op+= sieht vll ein wenig chaotisch aus, aber soweit ich weiß, ist resize nicht exceptionsafe -> brauchen kurzzeitig nen anderes array - und dann können wir auch gleich darauf arbeiten. das kann man aber definitv noch hübscher schreiben(z.bsp. mittels reserve + push_back statt des zusätzlichen iterators, etc.)

die test-ausgabe ist nicht gerade sehr c++ig oder elegant - aber um es richtig zu machen, fehlte mir dann doch die muse^^

#include <iterator>
#include <numeric>
#include <vector>

template<typename T>
struct polynom
{
	typedef T value_type;
	typedef std::size_t size_type;

	polynom()
	{}

	/* copy-ctor and assignment operator works fine for us */

	explicit polynom(size_type highest_exponent, value_type coeff = value_type())
	:	coeff( static_cast<coeff_container::size_type>(highest_exponent), coeff )
	{}

	template<typename U>
	explicit polynom(const polynom<U>& other)
	:	coeff( other.coeff.size() )
	{
		typename polynom<U>::coeff_container::const_iterator j(other.coeff.begin());
		for(coeff_container::iterator i(coeff.begin()), e(coeff.end()); i != e; ++i, ++j)
			*i = static_cast<value_type>(*j);
	}

	size_type get_max_coeff() const
	{
		return static_cast<size_type>(coeff.size());
	}

	value_type& get_coefficient(size_type exponent)
	{
		coeff_container::iterator i = coeff.begin();
		std::advance( i, static_cast<coeff_container::size_type>(exponent) );
		return *i;
	}
	const value_type& get_coefficient(size_type exponent) const
	{
		coeff_container::const_iterator i = coeff.begin();
		std::advance( i, static_cast<coeff_container::size_type>(exponent) );
		return *i;
	}

	template<typename U>
	polynom& operator+= (const polynom<U>& other)
	{
		if(coeff.size() < other.coeff.size())
		{
			coeff_container tmp(other.coeff.size());

			typename polynom<U>::coeff_container::const_iterator
				longer_i(other.coeff.begin()),
				longer_e(other.coeff.end());

			coeff_container::const_iterator shorter_i(coeff.begin()), shorter_e(coeff.end());

			coeff_container::iterator dest(tmp.begin());
			for(; shorter_i != shorter_e; ++shorter_i, ++ longer_i, ++dest)
				*dest = *shorter_i + *longer_i;

			for(; longer_i != longer_e; ++longer_i, ++dest)
				*dest = *longer_i;

			using std::swap;
			swap(coeff, tmp);
		}
		else
		{
			typename polynom<U>::coeff_container::const_iterator i(other.coeff.begin()), e(other.coeff.end());
			for(coeff_container::iterator dest(coeff.begin()); i != e; ++i, ++dest)
				*dest += *i;
		}

		return *this;
	}

	template<typename U>
	polynom& operator+= (U skalar)
	{
		if(coeff.empty())
			coeff.push_back(skalar);
		else
			coeff.front() += skalar;

		return *this;
	}

private:
	typedef std::vector<value_type> coeff_container;
	coeff_container coeff;

	template<typename> friend struct polynom;
};

template<typename T, typename U>
polynom<T> operator+ (const polynom<T>& lhs, const U& rhs)
{
	polynom<T> ret_val(lhs);
	ret_val += rhs;
	return ret_val;
}

#include <iostream>

int main()
{
	polynom<int> a;           /* - */
	polynom<float> b(3, 2.f); /* 2 + 2x + 2x² */
	polynom<double> c(4, 3.); /* 3 + 3x + 3x² + 3x³*/

	polynom<int> a_copy(a);
	polynom<int> b_copy(b);
	polynom<float> b_plus_c( b + polynom<float>(c) );
	polynom<float> b_plus_b( b + b );
	polynom<float> c_plus_b( polynom<float>(c) + b );

	a = a + 3;
	a = a + polynom<int>(b);

	std::cout << "a: (5 / 2 / 2)" << "\r\n";
	for(polynom<int>::size_type i(0), e(a.get_max_coeff()); i != e; ++i)
		std::cout << a.get_coefficient(i) << " *x^" << i << "\r\n";
	std::cout << std::endl;

	std::cout << "a_copy: (empty)" << "\r\n";
	for(polynom<int>::size_type i(0), e(a_copy.get_max_coeff()); i != e; ++i)
		std::cout << a_copy.get_coefficient(i) << " *x^" << i << "\r\n";
	std::cout << std::endl;

	std::cout << "b: (2 / 2 / 2)" << "\r\n";
	for(polynom<float>::size_type i(0), e(b.get_max_coeff()); i != e; ++i)
		std::cout << b.get_coefficient(i) << " *x^" << i << "\r\n";
	std::cout << std::endl;

	std::cout << "b_copy: (2 / 2 / 2)" << "\r\n";
	for(polynom<float>::size_type i(0), e(b_copy.get_max_coeff()); i != e; ++i)
		std::cout << b_copy.get_coefficient(i) << " *x^" << i << "\r\n";
	std::cout << std::endl;

	std::cout << "c: (3 / 3 / 3 / 3)" << "\r\n";
	for(polynom<double>::size_type i(0), e(c.get_max_coeff()); i != e; ++i)
		std::cout << c.get_coefficient(i) << " *x^" << i << "\r\n";
	std::cout << std::endl;

	std::cout << "b_plus_c: (5 / 5 / 5 / 3)" << "\r\n";
	for(polynom<float>::size_type i(0), e(b_plus_c.get_max_coeff()); i != e; ++i)
		std::cout << b_plus_c.get_coefficient(i) << " *x^" << i << "\r\n";
	std::cout << std::endl;

	std::cout << "b_plus_b: (4 / 4 / 4)" << "\r\n";
	for(polynom<float>::size_type i(0), e(b_plus_b.get_max_coeff()); i != e; ++i)
		std::cout << b_plus_b.get_coefficient(i) << " *x^" << i << "\r\n";
	std::cout << std::endl;

	std::cout << "c_plus_b: (5 / 5 / 5 / 3)" << "\r\n";
	for(polynom<float>::size_type i(0), e(c_plus_b.get_max_coeff()); i != e; ++i)
		std::cout << c_plus_b.get_coefficient(i) << " *x^" << i << "\r\n";
	std::cout << std::endl;

	polynom<int> warn_me_pls;
	warn_me_pls += polynom<float>();
}

Jz zu deinen Fragen:

Du hast doch coeff als private deklariert - greifst nun aber einfach darauf zu

Jopp, friend vergessen - dabei war ich mir so sicher, dass ich es hingeschrieben hatte

hab beim Polynom auch den []-Operator überladen um auf die Koeffizienten zugreifen zu können.

ich hoffe einen []op const und einen non-const!?

Ich weiß nicht ob du das kennst: [Eigenwerte, ...]

Jopp - aber ich wüsste nicht, was das hier interessieren sollte bei deinem Problem - es ging dir ja nur darum, ob assignment-op oder copy-ctor aufgerufen werden - da ist die aufgabe doch völlig nebensächlich... (und da du lieber die aufgabe beschrieben hast anstatt nen stück aussagekräftigen code und genaue beschreibung zu posten, weiß ich auch noch immer nicht, wo dein problem liegt)

aber da erhalte ich nur den Fehler

Klingt so, als ob dein polynom kein template ist und du das typename trotzdem mitgeschrieben hast - das wäre nur bei templates wichtig...

bb

[Sebastian Pizer]

Andreas_L schrieb:

...

Verrat doch erstmal, was Du überhaupt machen willst (nicht wie, sondern was).

Sag dann, was Du Dir für eine Lösung überlegt hast (Ansatz)

Zeig dann ein bissel Code. (Implementierung)

Wenn's darum geht Eigenwerte zu bestimmen, dafür gibt es ganz andere Algorithmen, die sich nicht mit Polynomen rumärgern. Eigenwerte über Nullstellen zu berechnen ist der falsche Ansatz -- zumindest wenn Du Matritzen mit mehr als 2x2 Elementen arbeitest. Das Nullstellen-Problem ist viel schwieriger. Im Gegenteil: Es gibt Nullstellen-Löser, die das Problem auf ein Eigenwertproblem reduzieren.

Eigenwerte einer Matrix "vernünftig" berechnen ist aber trotzdem noch nicht so einfach. Da nimmt man am besten eine Numerik-Bibliothek, die das kann. Du solltest auch wissen, dass es für versch Matrixtypen versch spezialisierte Algorithmen gibt. Eigenwerte für symmetrische Matrizen zu berechnen, kann man Normalsterblichen noch zumuten. Alles andere ist schwarze Magie, die man auch nach einem Mathematikstudium wieder vergessen hat -- es sei denn, man hat sich auf so etwas spezialisiert. (!!!)

Gruß,
SP

[Andreas_L]

Hallo, erstmal vielen Dank für eure Bemühungen.

Wenn's darum geht Eigenwerte zu bestimmen, dafür gibt es ganz andere Algorithmen, die sich nicht mit Polynomen rumärgern. Eigenwerte über Nullstellen zu berechnen ist der falsche Ansatz -- zumindest wenn Du Matritzen mit mehr als 2x2 Elementen arbeitest. Das Nullstellen-Problem ist viel schwieriger. Im Gegenteil: Es gibt Nullstellen-Löser, die das Problem auf ein Eigenwertproblem reduzieren.

Eigenwerte einer Matrix "vernünftig" berechnen ist aber trotzdem noch nicht so einfach. Da nimmt man am besten eine Numerik-Bibliothek, die das kann. Du solltest auch wissen, dass es für versch Matrixtypen versch spezialisierte Algorithmen gibt. Eigenwerte für symmetrische Matrizen zu berechnen, kann man Normalsterblichen noch zumuten. Alles andere ist schwarze Magie, die man auch nach einem Mathematikstudium wieder vergessen hat -- es sei denn, man hat sich auf so etwas spezialisiert. (!!!)

Ich weiß das das für große Matrizen eine riesige Laufzeit verursacht. Ich hab nur gerade diese Möglichkeit im Studium gelernt und möchte die gerne umsetzen und zwar hobbymäßig um damit Differentialgleichungssysteme zu lösen. Ich hab bei Wikipedia auch Alternativen gelesen, die für große Matrizen sehr viel schneller sind, aber die verstehe ich ja noch nicht - ich möchte einfach mal das Programmtechnisch umsetzen, was ich bisher gelernt habe.

Und nun zum Code - ich hab kein Template fürs Polynom genommen und auch keinen Vector für die Koeffizienten - deshalb sieht mein Code etwas anders aus:

Die Klassenübersicht fürs Polynom:

class CPolynom
{
protected:
	unsigned short	m_iGrad;				//Grad des Polynoms
	double*			m_pKoeffizienten;		//Koeffizienten des Polynoms - Koeffizienten[n] entspricht dem Koeffizienten vor x^n.

public:
	CPolynom(unsigned short Grad);
	CPolynom(void);
	double& operator[](unsigned short i);

	~CPolynom(void);

	CPolynom(CPolynom& AnderesPolynom); 
	CPolynom& operator=(CPolynom& AnderesPolynom); 

	template<typename U> 
	CPolynom& operator=(const U& Zahl); 

	CPolynom& operator+=(CPolynom& AnderesPolynom);
	CPolynom& operator-=(CPolynom& AnderesPolynom);

	template<typename U> 
	CPolynom& operator*=(const U& Zahl);
	CPolynom& operator*=(CPolynom& AnderesPolynom);
	template<typename U> 
	CPolynom& operator/=(const U& Zahl);
	template<typename U> 
	bool operator==(const U& Zahl);

	unsigned short GetGrad();					//Liefert den Grad des Polynoms
	void Koeffizienten_leeren();				//Alle Koeffizienten auf 0 setzen

};

CPolynom operator-(CPolynom& Minuend, CPolynom& Subtrahend);
CPolynom operator+(CPolynom& summand1, CPolynom& summand2);
template<typename U> 
CPolynom operator*(U& Zahl, CPolynom& Polynom);
template<typename U> 
CPolynom operator*(CPolynom& Polynom, U& Zahl);
template<typename U> 
CPolynom operator/(CPolynom& Polynom, U& Zahl);
CPolynom operator*(CPolynom& Polynom1, CPolynom& Polynom2);

std::ostream& operator<<(std::ostream& stream, CPolynom& obj);

ich hoffe einen []op const und einen non-const!?

Bisher nicht - wollte es erstmal erreichen das es funktioniert - danach kommt "Kosmetik".
Ich weiß nicht genau welche Methoden euch interessieren - ich poste mal ein paar:

CPolynom::CPolynom(unsigned short Grad)
{
	assert(Grad >= 0);

	m_iGrad = Grad;
	m_pKoeffizienten = new double[Grad+1];
}

CPolynom::CPolynom()
{
	m_iGrad = 0;
	m_pKoeffizienten = new double[1];
	m_pKoeffizienten[0] = 0.0;
}	

CPolynom::~CPolynom(void)
{
	delete[] m_pKoeffizienten;
}
template<typename U> 
CPolynom& CPolynom::operator=(const U& Zahl)
{
	if(m_iGrad != 0)
	{
		delete[] m_pKoeffizienten;
		m_iGrad = 0;
		m_pKoeffizienten = new double[m_iGrad+1];
	}

	m_pKoeffizienten[0] = Zahl;

	return *this;
}

Die Additionsmethode sieht bei mir etwas anders aus - schließlich will ich ein Array haben, dass vor dem X mit dem höchsten Exponenten einen Koeffizienten != 0 hat - sonst wäre die Gradangabe ja auch falsch.

CPolynom& CPolynom::operator+=(CPolynom& AnderesPolynom)
{
	if(m_iGrad == AnderesPolynom.GetGrad()) //Wenn z.B. 3x^2+2x + (-3x^2-2x) gerechnet wird ist der Grad der Funktion danach nciht mehr 2
	{
		unsigned short counter = 0;

		for(short i = m_iGrad; i >= 0; i--)
		{
			if(AnderesPolynom[i] == -m_pKoeffizienten[i]) counter++;
			else break;
		}

		if(counter == 0)
		{
			for(unsigned short i = 0; i <= m_iGrad; i++)
			{
				m_pKoeffizienten[i]+=AnderesPolynom[i];
			}
		}
		else
		{
			double* Neuekoeffizienten =  new double[m_iGrad+1-counter];

			for(unsigned short i = 0; i <= m_iGrad-counter; i++)
			{
				Neuekoeffizienten[i] = m_pKoeffizienten[i]+AnderesPolynom[i];
			}
			delete[] m_pKoeffizienten;
			m_pKoeffizienten = Neuekoeffizienten;
			m_iGrad -= counter;
		}
	}
	else if(m_iGrad > AnderesPolynom.GetGrad())
	{
		for(unsigned short i = 0; i <= AnderesPolynom.GetGrad(); i++)
		{
			m_pKoeffizienten[i]+=AnderesPolynom[i];
		}
	}
	else //AnderesPolynom.GetGrad() > m_iGrad
	{
		double* Neuekoeffizienten =  new double[AnderesPolynom.GetGrad()+1];

		for(unsigned short i = 0; i <= m_iGrad; i++)
		{
			Neuekoeffizienten[i] = m_pKoeffizienten[i]+AnderesPolynom[i];
		}
		for(unsigned short i = m_iGrad+1; i <= AnderesPolynom.GetGrad(); i++)
		{
			Neuekoeffizienten[i] = AnderesPolynom[i];
		}
		delete[] m_pKoeffizienten;
		m_pKoeffizienten = Neuekoeffizienten;
		m_iGrad = AnderesPolynom.GetGrad();
	}

	return *this;
}

So und nun die problematische Methode, in der die Determinante berechnet wird:

template <class Datentyp>
Datentyp CMatrix<Datentyp>::Determinante_Rekursiv()
{

	unsigned short List_Groesse = m_Matrix_Ersatz.size();

	if(List_Groesse == 2) //für den Rekursionsabbruch bei 2
	{
		std::list<Datentyp*>::iterator Iter1 = m_Matrix_Ersatz.begin();
		std::list<Datentyp*>::iterator Iter2 = Iter1; Iter2++;
		return ((*Iter1)[m_iDimension-2]*(*Iter2)[m_iDimension-1]-(*Iter1)[m_iDimension-1]*(*Iter2)[m_iDimension-2]);
	}

	Datentyp Unterdeterminante = 0;
	Datentyp* Zeile;	//aktuell herausgenommene Zeile

	if(List_Groesse & 1) //ungerade - durch das Verändern der Matrix ergibt sich immer das passende Vorzeichen.
	{
		for(unsigned int index = 0; index < List_Groesse; index++)
		{
			Zeile = m_Matrix_Ersatz.front();
			m_Matrix_Ersatz.pop_front();
			Unterdeterminante += Zeile[m_iDimension-List_Groesse]*Determinante_Rekursiv();;
			m_Matrix_Ersatz.push_back(Zeile);
		}

	}//end of if
	else //gerade - hier ändert das Verändern der Matrix an der Determinante nichts, deshalb wird das Vorzeichen benötigt.
	{	
		short Vorzeichen = 1;
		for(unsigned int index = 0; index < List_Groesse; index++)
		{
			Zeile = m_Matrix_Ersatz.front();
			m_Matrix_Ersatz.pop_front();
			Unterdeterminante += Vorzeichen*Zeile[m_iDimension-List_Groesse]*Determinante_Rekursiv();
			m_Matrix_Ersatz.push_back(Zeile);

			Vorzeichen *= -1;
		}
	}//end of else

	return Unterdeterminante;
}//end of Determinante_Rekursiv

Sie mag vielleicht etwas komisch aussehen: Die Determinante wird nach Spalten entwickelt. Jetzt fand ich das aber sehr ineffizient jedesmal für die Unterdeterminante die Teilmatrix zu kopieren, deshalb hab ich die Zeilen in einer Liste angeordnet, wobei ich dann eben immer entsprechend die Zeile für die Berechnung der Unterdeterminante herausnehmen kann.
Der Code funktioniert für double - das hab ich ausprobiert, allerdings gibts probleme bei

Datentyp Unterdeterminante = 0;

für die Polynome, da hier nicht mein Zuweisungsoperator sondern der Konstruktor des Polynoms mit dem Wert 0 für Grad aufgerufen wird.

Hab ich was wichtiges vergessen zu sagen?

Viele Grüße

Andreas

[Sebastian Pizer]

Andreas_L schrieb:

Ich weiß das das für große Matrizen eine riesige Laufzeit verursacht.

Nicht nur das. Nullstellen von Polynomen höheren Grades auszurechnen ist auch numerisch sehr schlecht, besonders bei mehrfachen Nullstellen (ganz ganz böse!).

Andreas_L schrieb:

Ich hab nur gerade diese Möglichkeit im Studium gelernt und möchte die gerne umsetzen und zwar hobbymäßig

Wieso? Kannst Du jetzt nicht mehr lernen?

Andreas_L schrieb:

um damit Differentialgleichungssysteme zu lösen. Ich hab bei Wikipedia auch Alternativen gelesen, die für große Matrizen sehr viel schneller sind,

schneller und überhaupt numerisch viel besser (Genauigkeit!).

Andreas_L schrieb:

Die Klassenübersicht fürs Polynom:

...

Nimm std::vector<double> für die Koeffizienten. Dann brauchst Du Dich auch nicht mehr so sehr um die Speicherverwaltung kümmern. Du brauchst dann keinen eigenen Kopierkonstruktor, Zuweisung, Destruktor. Du machst es Dir echt unnötig schwer.

Lass das mit den Templates sein. Typparameter U brauchst Du doch nicht. Nimm doch einfach double.

Andreas_L schrieb:

CPolynom& CPolynom::operator+=(CPolynom& AnderesPolynom)
{
  ...
}

Viel zu kompliziert! Du hast auch ein const beim Parameter vergessen. Es kann doch soooo schön einfach sein:

class Polynom
{
  std::vector<double> koeffs; // p(x) = Summe_i koeffs[i]*x^i
public:
  ...
  double operator()(double x) const;
  ...
  Polynom& operator+=(Polynom const& p);
  ...
};

double Polynom::operator()(double x) const
{
  double acc = 0;  // "Akkumulator"
  for (int i=koeffs.size(); i-- >0;) {
    acc = acc * x + koeffs[i];
  }
  return acc;
}

Polynom& Polynom::operator+=(Polynom const& p)
{
  koeffs.resize( std::max(koeffs.size(),p.koeffs.size()) , 0.0 );
  for (int i=0, e=p.koeffs.size(); i<e; ++i) {
    koeffs[i] += p.koeffs[i];
  }
  while (koeffs.size()>0u && koeffs.back()==0) {
    koeffs.pop_back();
  }
}

Andreas_L schrieb:

So und nun die problematische Methode, in der die Determinante berechnet wird:

...

Das ist so ziemlich das schlechteste, was man machen kann, um Determinanten zu berechnen. Ich finde immer noch den Ansatz über die Determinante mit Polynomen sehr schlecht -- nur dass das klar ist. Aber Determinanten berechnet man ganz anders. Wenn man die wirklich berechnen will, transformiert man die Matrix in eine Dreiecksmatrix, merkt sich dabei, wie viele Zeilen- bzw. Spaltenvertauschungen man gemacht (k), berechnet das Produkt der Diagonalen und multipliziert dieses mit (-1)^k. Fertig. Das geht ratzfatz in O(n^3). Mit "transfomieren" meine ich die Operationen, die man auch für's Lösen eines Gleichungssystems durchführen würde, also zB Zeilen vertauschen und ein Vielfaches einer Zeile auf eine andere addieren. Ersteres negiert die Determinante. Leteres verändert die Determinante nicht. Die Determinante einer Dreiecksmatrix ist gleich dem Produkt der Elemente der Diagonalen, wenn ich mich nicht irre.

BTW: Es sollen schon Leute aus'm Job gefeuert worden sein, weil sie Determinanten von Matrizen über die Zeilen/Spaltenentwicklung berechnet haben -- sagte zumindest mein Numerik-Professor.

Edit: Stopp mal ... Du hast ja dann Polynome in der Matrix stehen. Dann macht das mit den Dreiecksmatrizen nicht viel Sinn. Du bräuchtest dann nämlich eine Division von Polynomen. Solche Polynome ergeben allerdings keinen algebraischen Körper. Wow! Willst Du nicht doch lieber das Eigenwertproblem richtig lösen lassen?

Andreas_L schrieb:

Sie mag vielleicht etwas komisch aussehen: Die Determinante wird nach Spalten entwickelt. Jetzt fand ich das aber sehr ineffizient jedesmal für die Unterdeterminante die Teilmatrix zu kopieren, deshalb hab ich die Zeilen in einer Liste angeordnet, wobei ich dann eben immer entsprechend die Zeile für die Berechnung der Unterdeterminante herausnehmen kann.
Der Code funktioniert für double - das hab ich ausprobiert, allerdings gibts probleme bei

Datentyp Unterdeterminante = 0;

für die Polynome, da hier nicht mein Zuweisungsoperator sondern der Konstruktor des Polynoms mit dem Wert 0 für Grad aufgerufen wird.

Logisch. Es ist ja auch eine Initialisierung und keine Zuweisung. Wenn Du Polynom so definierst

class Polynom
{
  std::vector<double> koeffs;
public:
  ...
  // Schneller Default-Ctor (Nullpolynom)
  Polynom() {}

  // Konvertierungskonstruktor double->Polynom
  Polynom(double c) : koeffs(1) { koeffs[0]=c; }
  ...
};

dann klappt auch folgendes:

Polynom p = Polynom();
Polynom p = 0;          // <--sogar auch das hier

Fazit: Es lohnt sich, das Problem zu erklären, was man lösen will -- besonders dann, wenn einem viel bessere Lösungswege aufgezeigt werden.

Gruß,
SP

[Andreas_L]

Hi Sebastian, vielen Dank für deine Erklärungen.

Ich hab nur gerade diese Möglichkeit im Studium gelernt und möchte die gerne umsetzen und zwar hobbymäßig

Wieso? Kannst Du jetzt nicht mehr lernen?

Ja schon - aber wenn ich mich noch in die Numeric reinknie brauche ich noch viel mehr Zeit, die ich nicht habe - ich studiere nämlich auch kein Informatik oder Mathematik sondern Physik und hab deshalb mit Numeric zumindest im Moment noch gar nichts zutun. Klar ist das schon sehr interessant zu verstehen wie diese numerischen Lösungen funktionieren - aber ich bin schon zufrieden wenn ich ein Programm schreiben kann, mit dem ich kleinere DGL-Sysmte lösen kann

Lass das mit den Templates sein. Typparameter U brauchst Du doch nicht. Nimm doch einfach double.

Wie darf ich das verstehen - schließlich war das ja mein Problem warum ich überhaupt zuerst ein Post erstellt habe. Wenn ich einfach nur double nehme gibts ja Probleme wenn ich das Polynom mit nem short multipliziere.

Edit: Stopp mal ... Du hast ja dann Polynome in der Matrix stehen. Dann macht das mit den Dreiecksmatrizen nicht viel Sinn. Du bräuchtest dann nämlich eine Division von Polynomen. Solche Polynome ergeben allerdings keinen algebraischen Körper. Wow! Willst Du nicht doch lieber das Eigenwertproblem richtig lösen lassen?

Genau deshalb hab ich die langsame Methode gewählt - weil ich nicht wusste wie ich mit der Division durch Polynome umgehen soll.

Polynom& Polynom::operator+=(Polynom const& p)
{
  koeffs.resize( std::max(koeffs.size(),p.koeffs.size()) , 0.0 );
  for (int i=0, e=koeffs.size(); i<e; ++i) {
    koeffs[i] += p.koeffs[i];
  }
  while (koeffs.size()>0u && koeffs.back()==0) {
    koeffs.pop_back();
  }
}

Stimmt, ist wirklich wesentlich kürzer - aber mich stört dabei, dass der Vector erst vergrößert und dann nach und nach immer wieder verkleinert wird. Muss der Vector dann nicht häufig seinen ganzen Speicherbereich kopieren um sich der neuen Größe anzupassen? Bei mir ist nur eine Neuanpassung notwendig.

Logisch. Es ist ja auch eine Initialisierung und keine Zuweisung. Wenn Du Polynom so definierst...

Ok so funktionierts, aber wie kann ich das verstehen - warum ist das keine Zuweisung?
Wenn ich das so mache gibts aber ein weiteres Problem meiner Ansicht nach:
Ich wollte ja bisher einmal im Konstruktor den Grad übergeben bekommen, damit das Polynom initialisiert wird und dann über den []-Operator gefüllt werden kann. Jetzt hätte ich dann aber 2 Konstruktoren, die beide Zahlen annehmen. Zwar ist das einmal double und einmal short aber kann das nicht zu Problemen führen - sodass der falsche Konstruktor aufgerufen wird?
Sobald doch schon einer schreibt Polynom(3) würde doch der short-Konstruktor aufgerufen - obwohl es an sich auch eine Initialisierung mit 3 als Wert (double Konstruktor) vom Programmierer gemeint sein könnte.

Viele Grüße

Andreas

[Sebastian Pizer]

Andreas_L schrieb:

Hi Sebastian, vielen Dank für deine Erklärungen.

Wieso? Kannst Du jetzt nicht mehr lernen?

Ja schon - aber wenn ich mich noch in die Numeric reinknie brauche ich noch viel mehr Zeit, die ich nicht habe

Deswegen nimmt man sich dafür auch eine Bibliothek, wie zB GSL oder so etwas in der Richtung.

Andreas_L schrieb:

Lass das mit den Templates sein. Typparameter U brauchst Du doch nicht. Nimm doch einfach double.

Wie darf ich das verstehen - schließlich war das ja mein Problem warum ich überhaupt zuerst ein Post erstellt habe. Wenn ich einfach nur double nehme gibts ja Probleme wenn ich das Polynom mit nem short multipliziere.

Ich weiß nicht, was Du für ein Problem hattest. Du hast es nicht gezeigt und ich habe anscheinend falsch geraten. Jedenfalls macht bei Deiner Polynom-Version es keinen Sinn, Den Typ von "skalaren Operanden" zu parameterisieren, wo Du doch double Werte für die Koeffizienten des Polynoms speicherst.

Andreas_L schrieb:

Edit: Stopp mal ... Du hast ja dann Polynome in der Matrix stehen. [...]

Genau deshalb hab ich die langsame Methode gewählt - weil ich nicht wusste wie ich mit der Division durch Polynome umgehen soll.

Dann ist ja gut, dass ich das mit den schlauen Numerik-Bibliotheken jetzt schon bestimmt 3mal erwähnt habe.

Andreas_L schrieb:

Polynom& Polynom::operator+=(Polynom const& p)
{
  koeffs.resize( std::max(koeffs.size(),p.koeffs.size()) , 0.0 );
  for (int i=0, e=koeffs.size(); i<e; ++i) {
    koeffs[i] += p.koeffs[i];
  }
  while (koeffs.size()>0u && koeffs.back()==0) {
    koeffs.pop_back();
  }
}

Stimmt, ist wirklich wesentlich kürzer - aber mich stört dabei, dass der Vector erst vergrößert und dann nach und nach immer wieder verkleinert wird. Muss der Vector dann nicht häufig seinen ganzen Speicherbereich kopieren um sich der neuen Größe anzupassen? Bei mir ist nur eine Neuanpassung notwendig.

1. Dass koeffs.back()==0 zutrifft ist höchst unwahrscheinlich, findest Du nicht? Ich habe die letzte Schleife nur Dir zuliebe eingefügt.
2. pop_back() kostet fast nichts. Die Komplexitätsgarantie ist O(1). Da wird nichts umkopiert.

Andreas_L schrieb:

Logisch. Es ist ja auch eine Initialisierung und keine Zuweisung. Wenn Du Polynom so definierst...

Ok so funktionierts, aber wie kann ich das verstehen - warum ist das keine Zuweisung?

Typ Variable = Initialisierer;
nennt sich "copy initialization" und kann in schlauen Büchern nachgelesen werden. Eine Zuweisung kann nur schon existierenden Objekten etwas zuweisen. Es wird hier auch nirgens ein Default-Konstructor aufgerufen, falls Du das denkst. Das sind die Regeln und das ist gut so (tm).

Andreas_L schrieb:

Wenn ich das so mache gibts aber ein weiteres Problem meiner Ansicht nach:
Ich wollte ja bisher einmal im Konstruktor den Grad übergeben bekommen, damit das Polynom initialisiert wird und dann über den []-Operator gefüllt werden kann. Jetzt hätte ich dann aber 2 Konstruktoren, die beide Zahlen annehmen. Zwar ist das einmal double und einmal short aber kann das nicht zu Problemen führen - sodass der falsche Konstruktor aufgerufen wird?

Ja, da musst Du dich schon entscheiden. Bedenke, dass wenn Du eine implizite Konvertierung von double->Polynom hast, und nur die Operationen + - * auf Polynomen implementierst, dass Du dann auch automatisch mit Skalaren rechnen kannst. Also, bei "meinpolynom * meindouble" würde dann meindouble zu polynom konvertiert und dann mit dem ersten multipliziert. Toll wa? -- Natürlich kann man mit extra Overloads für double noch etwas Geschwindigkeit rausholen...

Andreas_L schrieb:

Sobald doch schon einer schreibt Polynom(3) würde doch der short-Konstruktor aufgerufen - obwohl es an sich auch eine Initialisierung mit 3 als Wert (double Konstruktor) vom Programmierer gemeint sein könnte.

Ja, is Käse. Aber ich weiß jetzt auch, was Dein ürsprüngliches Problem war. Du hattest ja schon einen Konvertierungkonstruktor short ---> CPolynom, der gar keiner hätte sein dürfen! Deswegen gibt es in C++ auch das Schlüsselwort explicit .

Gruß,
SP

[Andreas_L]

Hi Sebastian,

nochmals danke für deine Erklärungen

Dann ist ja gut, dass ich das mit den schlauen Numerik-Bibliotheken jetzt schon bestimmt 3mal erwähnt habe.

Ja klar - aber die Sache ist doch das ich das freiwillig hobbymäßig selbst implementieren will um dabei auch besser zu lernen wie man mit so Problemen umgeht. Z.B. war mir bis heute noch nicht die Bedeutung von "explicit" bewusst, bzw. ich hab nie einen Sinn in diesem Schlüsselwort gesehen.

Es gibt wahrscheinlich auch Bibliotheken, die mir direkt die Eigenwerte ausgeben (oder gleich die DGL lösen) - aber dann kann ich auch direkt ein fertiges Matheprogramm nehmen, dann brauche ich nichts selber machen.

Es ist zwar nicht so produktiv aber ich mache das ja auch nicht um am Ende ein Programm zu haben das ich dauernd verwenden will - ich mache das eigentlich nur um während des Programmierens zu lernen.

Viele Grüße

Andreas

[drakon]

Das ist so ziemlich das schlechteste, was man machen kann, um Determinanten zu berechnen. Ich finde immer noch den Ansatz über die Determinante mit Polynomen sehr schlecht -- nur dass das klar ist. Aber Determinanten berechnet man ganz anders. Wenn man die wirklich berechnen will, transformiert man die Matrix in eine Dreiecksmatrix, merkt sich dabei, wie viele Zeilen- bzw. Spaltenvertauschungen man gemacht (k), berechnet das Produkt der Diagonalen und multipliziert dieses mit (-1)^k. Fertig. Das geht ratzfatz in O(n^3). Mit "transfomieren" meine ich die Operationen, die man auch für's Lösen eines Gleichungssystems durchführen würde, also zB Zeilen vertauschen und ein Vielfaches einer Zeile auf eine andere addieren. Ersteres negiert die Determinante. Leteres verändert die Determinante nicht. Die Determinante einer Dreiecksmatrix ist gleich dem Produkt der Elemente der Diagonalen, wenn ich mich nicht irre.

Jap, du irrst nicht. Ist afaik die effizienteste Methode.
Habe mal nachgeschaut und die Methode soll 1/3n^3 Additionen und Multiplikationen bringen und die nach der üblichen Definition der Determinante (über Permutationen) hat n! Additionen und (n-1)n! Multiplikationen, was sehr extrem wird.

BTW: Es sollen schon Leute aus'm Job gefeuert worden sein, weil sie Determinanten von Matrizen über die Zeilen/Spaltenentwicklung berechnet haben -- sagte zumindest mein Numerik-Professor.

Glaube ich gerne. - Habe das mal für ne Übung in Matlab (resp. Octave) implementiert. Ich will mir gar nicht vorstellen, was da für Rekursionen zu Stande kommen für ne 100x100 Matrix.
Vor allem ist die Methode über die Dreiecksmatrix wahrscheinlich sogar einfacher zu implementieren.

[Sebastian Pizer]

Sebastian Pizer schrieb:

class Polynom
{
  std::vector<double> koeffs; // p(x) = Summe_i koeffs[i]*x^i
public:
  ...
  Polynom& operator+=(Polynom const& p);
  ...
};

Polynom& Polynom::operator+=(Polynom const& p)
{
  koeffs.resize( std::max(koeffs.size(),p.koeffs.size()) , 0.0 );
  for (int i=0, e=koeffs.size(); i<e; ++i) {
    koeffs[i] += p.koeffs[i];
  }
  while (koeffs.size()>0u && koeffs.back()==0) {
    koeffs.pop_back();
  }
}

Ich merke gerade, hier ist noch ein Bug drin. Falls p.koeffs.size() < koeffs.size() greift die erste Schleife auf nicht vorhandene Elemente in p.koeffs zu. Es müsste e=p.koeffs.size(); bei der for-Schleife heißen.

Andreas_L schrieb:

Ja klar - aber die Sache ist doch das ich das freiwillig hobbymäßig selbst implementieren will um dabei auch besser zu lernen wie man mit so Problemen umgeht.

Eigenwerte für Matrizen größer als 2x2 Elemente berechnen ist nichts, was man selbst programmieren können muss, echt nicht! Reine Zeitverschwendung. Das solltest Du als Baustein einfach benutzen können, mehr nicht. Wenn Du den Anspruch hast, die Algorithmen verstehen zu wollen, solltest Du dir das eine oder andere schlaue Numerik-Buch holen. Sei gewarnt.

Gruß,
SP