quotient aus fakultäten (im datentypbereich belassen)

DarthZiu

dr_ceran schrieb:

int N=10.2;
	while(N!=0)

Also für einen int-Wert eine 10,2 einzugeben finde ich schonmal ein bisschen seltsam.

camper

das erwartete ergebnis mag vielleicht im darstellbaren bereich von double liegen, aber das gilt ja nicht unbedingt für alle zwischenergebnisse. was wäre denn fak(171) ? ... sobald du eine unendlichkeit an irgendeiner stelle hast, bekommst du sie nicht mehr durch einfache rechenoperationen weg (das ist ja auch der sinn dabei). wenn du also - ohne auf grössere datentypen auszuweichen - mit gtrösseren N rechnen willst, müsstest du darüber nachdenken, evtl. statt jede fakultät einzeln zu berechnen, diese bereits mit der folgenden division zu kombinieren. eine andere möglichkeit wäre, für fak(N) nur für die zwischenrechnung einen vorfaktor von 2^-1023 zu wählen, und ihn zum schluss wieder eliminieren. dann erfolgt der überlauf erst etwas später.

Gast221212

Was erhoffst du dir davon:

return 000

Die Zahl 0 oder den String "000"?

camper

eine weitere möglichkeit wäre, alle zahlen auf einen bereich von 1bis 2 zu normieren und die normierungsfaktoren (2er potenzen) separat zu verechnen. etwa so:

double fak(int c, int& norm)
{
    double f = 1;
    norm = 0;
    for( int i = 2; i <= c; ++i )
    {
        f *= i;
        while( f >= 2 )
        {
            f /= 2;
            ++norm;
        }
    }
    return f;
}

die gesuchte zahl wäre hier also f*2^norm. mit norm kann man dann ganz normal (entsprechen potenzgesetzen) weiter rechnen; erst ganz zum schluss ist es sinnvoll, es mit der mantisse f zu kombinieren. andere faktoren als 2 sind denkbar um den rechenaufwand zu reduzieren. hier nur zur veranschaulichung der idee.

dr_ceran

@camper:
genau das ist es fak(171)= infinity...
dein lösungsansatz sieht vielversprechend aus...
nochmals vielen dank für die hilfe
sorry wegen der seltsamen fehler im code, aber es war spät und ich hab zich was probiert und nich alles wieder verändert

groovemaster

Gast221212 schrieb:

Was erhoffst du dir davon:
return 000

Wenigstens ein oktales Literal im Code?

dr_ceran

@camper:
hab jetzt mit deiner idee bzgl. der normierung ein wenig rumprobiert, und wenns nur um eine fakultät geht is das natürlich gold wert auch wenns um einen quotienten zweier fakultäten geht...
das problem is aber, dass ja in meiner fkt folgender term auftaucht...

(fak(N))/(fak(x)*fak(y)*fak(z))

d.h. hier wird die normierung wieder zum fallstrick...
die idee ist daher denk ich vielleicht im "dynamischen" berechnen dieses quotienten zu finden, also quasi die einzelnen fakultäten wachsen lassen und nach jedem wachstumsschritt das produkt speichern, danach nur noch die hinzukommenden faktoren (die also bei jeder einzelnen fakultät dazukämen) wieder als quotient errechnen und dem alten produkt auffaktorisieren....
dann is man denk ich ständig im "grünen" bereich...
falls jemand zu dieser idee (da die ja vielleicht nich neu ist) den code schon hat dann bitte hier posten...
ansonsten werd ich mich jetzt mal selbst versuchen

camper

ist doch simpel (Potenzgesetze): multiplikation wird zur addition der exponenten, division zu subtraktion etc.; also
$\frac{N!}{x!y!z!}=\frac{N!_{normiert}2^{norm\_N}}{x!\_{normiert}2^{norm\_x}y!\_{normiert}2^{norm\_y}z!\_{normiert}2^{norm_z}}$

$=\frac{N!_{normiert}}{x!_{normiert}y!_{normiert}z!_{normiert}}2^{norm\_N-norm\_x-norm\_y-norm\_z}$

dr_ceran

@camper:
genau so geht`s, so leid es mir tut, eben nich...=)
wenn du das mal probierst so kommt bei dem quotient von zwei fakultäten (mit ausreichend hohen N) noch was ordentliches raus...logisch, da sich dann die normierungen gerade rauskürzen...
aber im nenner hast du nochmal die normierung^2 und das überschreitet den double bereich gerade wieder....
aber meine idee sieht momentan ganz vielversprechend aus, wenns fertig is werd ich es posten...
solltest du lust haben, kannst du ja deinen ansatz mal ausbauen, vielleicht hab ich nur was nich verstanden... wenn deine lösung bei N=300 immer noch nich infinity ausgibt, dann hast dus und ich verneige mich in erfurcht

camper

#include <iostream>

typedef double real;

real fak(int c, int& norm)
{
	real f = 1.0;
	norm = 0;
	for( int i = 2; i <= c; ++i )
	{
		f *= i;
		while( f >= 4294967296.0 )
		{
			++norm;
			f /= 4294967296.0;
		}
	}
    return f;
}

real combine(real f, int norm)
{
	if( norm < 0 )
	{
		while( norm++ ) f /= 4294967296.0;
	}
	else
	{
		while( norm-- ) f *= 4294967296.0;
	}
	return f;
}

real zustaende( int m, int N )
{
    int x = 0, y = 0, z = 0;
    if( m == 0 ) y = N;
    if( m < 0 )
    {
		x = -m;
	    y = N + m;
    }
    if( m > 0 )
    {
        z = m;
	    y = N - m;
    }
	real summe = 0.0;
    if( m >= -N && m <= N )
    {
        for( int i = 0; i < ( ( N - abs( m ) ) / 2 ) + 1; ++i )
        {
			int normN, normx, normy, normz;
			real fakN = fak( N, normN );
			real fakX = fak( x, normx );
			real fakY = fak( y, normy );
			real fakZ = fak( z, normz );
			summe += combine( fakN / ( fakX * fakY * fakZ ), normN - ( normx + normy + normz ) );
            ++x;
			y -= 2;
			++z;
        }
    }
    return summe;
}

int main()
{
	int N = 1;
	while( N != 0 )
    {
		std::cout<< "Teilchenzahl eingeben:";
    	std::cin >> N;
	    for( int i = -N; i <= N; ++i )
    	{
        	std::cout << "m = " << i << "  :\t" << zustaende( i, N ) << std::endl;
    	}
    }
    return EXIT_SUCCESS;
}

funktioniert bis einschliesslich N=649. wenn du g++'s long double benutzt, geht es noch ein ganzes stück weiter - allerdings ist die normierungsfunktion recht ineffizient und das macht sich dann bemerkbar habe hier bereits eine grössere potenz genommen, um es nicht bei kleinen zahlen schon zum problem werden zu lassen. es sollten aber unbedingt 2er potenzen sein, alles andere würde zusätzliche rundungsfehler produzieren.

dr_ceran

@camper:
kopfschüttelnd betrachtete ich deinen code, und fragte mich, wie ich es mir erlauben konnte an deiner idee zu zweifeln
in meiner beschränktheit übersah ich doch glatt die möglichkeit, die normierungen klein zu wählen, dafür häufiger auszuführen und zu zählen, um sie dann ganz ähnlich immer im datentypbereich bleibend wieder zu entfernen....
wunderschön kann ich da nur sagen...
der code gefällt mir sehr gut...
hab wieder ne menge gelernt...
und darum nochmals danke für deine rege anteilnahme an meinem problem (und vor allem dessen lösung )

Jester

Was willst Du eigentlich genau ausrechnen? Wenn Dein Endergebnis platz in nem unsigned long long hat, dann kannst Du auch mit denen Rechnen, indem Du modulo einer ausreichend großen Primzahl rechnest. Das dürfte um einiges Effizienter sein als mit den doubles.

MfG Jester

camper

@Jester: die zahlen werden recht gross für grosse N, da reicht auch long long recht schnell nicht mehr aus. natürlich muss man sich überlegen, wieweit man das ausbauen will, bis man erkennt, das man mit einer echten bignum-bibliothek besser bedient ist.
P.S. wieso muss es eigentlich eine primzahl sein?

ich tippe mal das es um atomphysik geht. aber das ist geraten.

Jester

Ich weiß, daß die Fakultät wächst, aber das ist nicht so wichtig. Mir geht es um das Endergebnis. 100 über 5 ist zum Beispiel im Vergleich zu der riesigen 100! garnicht so groß. Wie gesagt es kommt nur auf die Größe des Endergebnisses an, nicht auf die der Zwischenschritte. Allein davon hängt es ab was nötig ist.

MfG Jester

camper

ich bezog mich auch auf das endergebnis. bereits für N=43 passt es nicht mehr für alle m in den unsigned long long bereich. bei N=650 steigt er wie gesgt bei double aus. bei long double treten ab N=10343 überläufe auf.

dr_ceran

@camper:
es handelt sich um theoretische physik (genauer statistik/thermodynamik)
ich deutete es schon im ersten post an...
man hat eine bestimmte anzahl an teilchen im magnetfeld, welche nicht wechselwirken... diese können einen spin von -1,0,1 aufweisen (genauer gesagt die projektion eines spins auf die z-achse, wie es in der th.physik üblich ist)
nun wird eben mit dem programm berechnet wie groß die mikrokanonische(kein energie-und teilchenaustausch) zustandssumme zu einem bestimmten energiewert wird... das m was im code vorkommt ist hier der entscheidende teil der energie, der dann noch mit zwei festen größen multipliziert wird um zu energie zu gelangen
dieses m ist für N teilchen die summe aus deren spinprojektionen, kann also bei N=1 auch nur 1,0,-1 sein....
d.h. es wird also die zahl der möglichkeiten gesucht um mit einer festen anzahl an teilchen auf den jeweiligen energiewert bzw m zu kommen...
viele grüße