Variable ist zu klein

[Jester]

Eine schöne Möglichkeit ist auch sich ne Abschätzung für n über k zu besorgen und dann noch eine Primzahl p, die größer als diese Schranke ist. Mann kann dann nämlich einfach alle Schritte modulo p rechnen, also immer den Rest bezüglich Division durch p. (Mathematiker würden sagen man projiziert auf Z/pZ)
Der Rest liegt dann zwischen 0 und p-1. Weil ja aber das Ergebnis sowieso < p ist, ist dieser Rest gerade das Ergebnis. Auf diese Art und Weise kann man auch noch für ziemlich große n rechnen, weil die Fakultät ja immer wieder mit mod p klein gehalten wird.

MfG Jester

[Jester]

Ich hab mich grad mal hingesetzt und noch ein bißchen rumgerechnet.
Ohne große Klimmzüge komme ich mit dieser Version wohl bis n=34.

MfG Jester

[User231]

Kannste mal Code posten dann wieß ich auch wat du mit Abchätzung meins. Bin net so gut in Mathe.

[Walli]

Also ich benutze immer folgende Funktion

template<typename T>
  T Binomial(unsigned n, unsigned k)
{
  if(k > n) return 0;
  if(k == n) return 1;

  T rval = 1;
  for(unsigned i = n; i != k; --i)
    rval *= i;
  for(unsigned i = n - k; i != 1; --i)
    rval /= i;

  return rval;
}

[Jester]

Hab den Code grad nicht greifbar. Kommt heute abend (nacht) irgendwann oder morgen früh.

MfG Jester

[Michael E.]

Man könnte ja auch eine zu große Zahl durch 65535 teilen, den Ganzzahlwert in einer unsigned _int64 und den Rest in einer unsigned int-Variable speichern. Zur Ausgabe mit cout rechnet man dann rückwärts

[Walli]

*knock* *knock*. Ich habe doch eine funktionierende Lösung gepostet. Wenn du die so aufrufst...

unsigned long long x = Binomial<unsigned long long>(n, k);
unsigned __int64 y = Binomial<unsigned __int64>(n, k);

...dann solltest du relativ hohe Werte erhalten können. Deine Idee mit dem dividieren funktioniert auch nur begrenzt und ist viel aufwändiger (NR sux ).

[Michael E.]

MaSTaH schrieb:

unsigned long long x = Binomial<unsigned long long>(n, k);

unsigned long long funktioniert bei mir nicht

unsigned __int64 y = Binomial<unsigned __int64>(n, k);

Mit der Variante kommst du bis 20!. Wenn du es aber machst, wie ich beschrieben hab (bloß mit zwei unsigned _int64), dann kommt man bis 34!.

(NR sux ).

Was heißt das???

[Krösus]

Für die Praxis: Einfach logarithmisch rechnen mit double-Werten. Damit kommt man sehr weit!
ln(k!) = Sum(i=1..k){ln(i)}

#include <math.h>
double LogFak(int k)
{
	double dLogSum = 0;
	while(k > 1)
	{
		dLogSum += log((double) k);
		--k;
	}
	return dLogSum;
}

[Krösus]

#define MERKE_ERSTE 1000 //Zum Beschleunigen die ersten paar Werte merken
double LogFak(int k)
{
	static int siValid = 1; //Index, bis zu dem Array-Inhalt gueltig ist
	static double sadLogFak[MERKE_ERSTE] = { 0 };
	if(k <= siValid)
		return sadLogFak[k];
	double dLogSum = saLogFak[siValid];
	int i = siValid + 1;
	while(i < MERKE_ERSTE)
	{
		dLogSum += log((double) i);
		sadLogFak[i] = dLogSum;
		++i;
	}
	siValid = i - 1;
	while(i <= k)
	{
		dLogSum += log((double) i);
		++i;
	}
	return dLogSum;
}

[Michael E.]

Sorry, kann noch keinen Logarithmus. Kannst du mir mal zeigen, was ich mit dem return-Wert anfangen soll und wieso der return-Wert bei 1 bis 999 gleich ist (wenn #define MAX_WERT 10000, dann sind sogar alle return-Werte bis 9999 gleich) .

[Walli]

CME386 schrieb:

unsigned long long funktioniert bei mir nicht

Kann auch nicht jeder Compiler. Nur gcc, VC++ (>7)...

CME386 schrieb:

Mit der Variante kommst du bis 20!. Wenn du es aber machst, wie ich beschrieben hab (bloß mit zwei unsigned _int64), dann kommt man bis 34!

Wieso Fakultät? Ich denke du willst 'nen Binomialkoeffizienten? Meine Variante kürzt schon vor dem berechnen des Bruches.

CME386 schrieb:

Was heißt das???

"Neue Rechtschreibung" (NR) suckt. -> wg. aufwändig

[Michael E.]

Hast Recht, MaSTaH,
ich hatte es eilig und hab deinen Code falsch gelesen. Liegt wohl daran, dass ich erst gestern Abend mit Templates angefangen hab. Aber jetzt seh ich, dass du Recht hast.

[Walli]

Ist nur ein Funktionstemplate, damit man den Rückgabetyp bestimmen kann. Nix besonderes.