große Zahlen bei Fakultätsberechnung

314159265358979 schrieb:

Hacker schrieb:

314159265358979 schrieb:

Gibt da noch unsigned long long

Ist das nicht nur auf manchen Systemen erlaubt? Könnte schwören, Ideones GCC 4.3.1 (glaub die haben LAMP) hat mich da mal böse überrascht.

Ist seit C++11 Standard.

Mmhh, danke!

Da Fließkommaberechnung scheinbar kein Problem für den TE darstellt, wäre

double bincoeff(int n, int k) {
  return tgamma(n + 1) / tgamma(k + 1) / tgamma(n - k + 1);
}

eine einfache Möglichkeit.

ruhig_brauner

Hätte doch noch ne Frage.

Wie sorgt man für ne Eingabewiederhohlung, wenn z.B. keine Zahlen sonder Buchstaben oder keine ganzen Zahlen eingegeben werden?

Also wenn z.B. nur mit y oder n geantwortet werden soll, ist das ja kein Problem. Bei einstelligen Zahlen würde ich auch wissen, wie man die Eingabe von Buchstaben vermeidet. Aber bei 0.52 oder 30 habe ich keine Ahnung

ruhig_brauner schrieb:

Wie sorgt man für ne Eingabewiederhohlung, wenn z.B. keine Zahlen sonder Buchstaben oder keine ganzen Zahlen eingegeben werden?

int ganzzahl;
	cout << "Bitte eine Ganzzahl eingeben: ";
	while( !(cin>>ganzzahl) )
	{
		cin.clear();
        cin.ignore(numeric_limits<streamsize>::max(),'\n'); // #include <limits>
        cout << "Bitte eine Ganzzahl eingeben: ";
	}

Michael E.

Hacker schrieb:

Integral: Kann nur Ganze Zahlen Speichern (hoffe du kannst Mathe )

Integrale sind Nudeln. Keine Ahnung, was man alles in Mathe können muss, um was mit ganzen Zahlen anfangen zu können.

Ich hab auch noch nen Vorschlag:

\begin{align*} n! = 2^{\sum_{i=1}^n \log_2 i} \end{align*}

Was die zeilenweise Verarbeitung von Benutzereingaben angeht, da habe ich noch eine alte Funktionsvorlage rumliegen, die unter Fehlerbehandlungsgesichtspunkten robuster ist als die ignore-Variante:

#include <iostream>
#include <sstream>
#include <string>
#include <stdexcept>

struct malformed_user_input : public std::runtime_error {
  inline malformed_user_input(std::string const &msg) : std::runtime_error(msg) { }
  virtual ~malformed_user_input() throw() { }
};

struct stream_broken : public std::runtime_error {
  inline stream_broken(std::string const &msg) : std::runtime_error(msg) { }
  virtual ~stream_broken() throw() { }
};

template<typename result_t>
result_t &cli_read_ref(result_t          &dest,
                       std::string const &prompt,
                       unsigned           max_tries,
                       std::istream      &in  = std::cin,
                       std::ostream      &out = std::cout) {
  std::istringstream parser;
  std::string line;
  unsigned tries = 0;

  do {
    parser.clear();

    if(tries < max_tries) {
      ++tries;
    } else {
      throw malformed_user_input("cli_read_ref: More than 'max_tries' parse failures");
    }

    out << prompt << std::flush;
    if(!out) {
      throw stream_broken("cli_read_ref: Cannot write to ouput stream");
    }

    if(!std::getline(in, line)) {
      throw stream_broken("cli_read_ref: Cannot read from input stream");
    }

    parser.str(line);
    parser >> dest;
  } while(!parser);

  return dest;
}

template<typename result_t>
result_t cli_read(std::string const &prompt,
                  unsigned           max_tries,
                  std::istream      &in  = std::cin,
                  std::ostream      &out = std::cout) {
  result_t result;
  return cli_read_ref(result, prompt, max_tries, in, out);
}

// Anwendungsbeispiel:

int main() {
  // Lies einen int ein; drei Versuche.
  int x = cli_read<int>("Zahl: ", 3);

  std::cout << 2 * x << std::endl;
}

Hintergrund ist, dass, wenn mal etwas tiefer liegendes mit std::cin nicht stimmen sollte, die cin.clear()-cin.ignore()-cin>>-Variante in einer Endlosschleife endet. Das kann beispielsweise passieren, wenn stdin in eine Datei umgeleitet wird, deren Inhalt als Benutzereingabe nicht funktioniert - irgendwann ist halt eof, und dann bringt cin.clear() einen nicht weiter.

Caster

http://de.wikipedia.org/wiki/Stirling-Formel

wikipedia.de schrieb:

Die Stirling-Formel ist eine mathematische Formel, mit der man für große Fakultäten Näherungswerte berechnen kann.

314159265358979

Hast du das selbst geschrieben seldon?

ruhig_brauner schrieb:

Dann hätte ich nochmal ne andere Frage, an Leute, die beruflich mit C++ arbeiten. Macht das Spaß? (Mich würde mal die rein subjektive Antwort interessieren. Will auch kein "kommt auf den Bereich an" hören. )

macht sex spaß?
glaubst du prostituierte haben spaß?

überlege dreimal bevor du ein hobby zum beruf machst...

Michael E. schrieb:

Hacker schrieb:

Integral: Kann nur Ganze Zahlen Speichern (hoffe du kannst Mathe )

Integrale sind Nudeln. Keine Ahnung, was man alles in Mathe können muss, um was mit ganzen Zahlen anfangen zu können.

Ich hab auch noch nen Vorschlag:
\begin{align*} n! = 2^{\sum_{i=1}^n \log_2 i} \end{align*}

Damit kann wieder ich nichts anfangen. Aber nicht jeder weiß, wie die Menge der Ganzen Zahlen definiert ist.

Michael E.

Nach ner Definition der ganzen Zahlen hat keiner gefragt. Aber um zu wissen, was ganze Zahlen im umgangssprachlichen Sinn sind, braucht man nicht "Mathe zu können".

Worauf ich hinaus will: Niemand sagt im Deutschen Integral für Ganzzahl.

Hacker, das mit der Formel hat der nur als Jux gemeint. Da steht auch nur 2*3*4*...*n

Michael E. schrieb:

Nach ner Definition der ganzen Zahlen hat keiner gefragt. Aber um zu wissen, was ganze Zahlen im umgangssprachlichen Sinn sind, braucht man nicht "Mathe zu können".

Zahlenmengen sind ja auch nur "Teilgebiet der Mathematik".
Egal, du hast Recht, aber ich will mich fachlich ausdrücken.

314159265358979 schrieb:

Hast du das selbst geschrieben seldon?

Ja, die Grundfassung ist aber lange her und hieß anders (read_type, wenn ich das richtig im Kopf habe). Du kannst das Ding gerne benutzen, wenn du es für irgendwas gebrauchen kannst. Ich habe für mich festgestellt, dass ich im Laufe der Zeit immer weniger Verwendung dafür hatte, aber eine Weile hat es mir gute Dienste geleistet (Performance ist ja an dieser Stelle von nachrangiger Bedeutung).

Michael E.

gastgast schrieb:

Hacker, das mit der Formel hat der nur als Jux gemeint. Da steht auch nur 2*3*4*...*n

Natürlich ist das dasselbe, sonst hätte ichs wohl nicht geschrieben. Aber es war kein Jux. Denn in vielen Fällen, hier auch, kann man mit dem Logarithmus der Fakultät rechnen, sodass man mit deutlich größeren Zahlen zurechtkommt.

PhilippHToner

Also eigentlich kann man bei den Binominalkoeffs numerisch sehr gut kürzen!

n über k = n! / ( k!*(n-k)!): mit n >= k

Für n > 2k ist der zweite Faktor im Nenner größer, ansonsten, der erste Faktor.

Und den größeren Faktor rechnest du sofort mit n! entgegen, dann sparst du dir schon mal 2*k, bzw 2*(n-k) Multiplikationen, weil du es sowohl für n! als auch für den größeren Faktor nicht berechnen musst.

Beispiel: 100 über 3

100! / (3! * (100-3)!) => n > 2k also über (100-3)! kürzen

100!/97! * 1/3! = 100*99*98 * 1/(1*2*3) = 161700
so kann man es sogar fast im Kopf rechnen.

Anders hat der numerische Wert von 100! 158 Stellen vor dem Komma
Da müsstest dann von Java BigInt benutzen !

@Michael: Die Idee ist prinzipiell nicht ganz blöde, aber man kann die Berechnung des Binomialkoeffizienten so aufziehen, dass kein Zwischenergebnis größer ist als das Endergebnis:

unsigned long bincoeff(int n, int k) {
  if(k > n - k) {
    return bincoeff(n, n - k);
  }

  unsigned long result = 1ul;
  for(int i = 1; i <= k; ++i) {
    if((n - k) % i == 0) {
      result *= (n - k) / i + 1;
    } else {
      result /= i;
      result *= n - k + i; // Merke: n - k + i > i
    }
  }

  return result;
}

...womit die Notwendigkeit für den Logarithmus-Trick verschwindet, denn wenn das Endergebnis nicht mehr in den Zieldatentyp passt, hat man noch ein ganz anderes Problem.

Michael E.

seldon schrieb:

man kann die Berechnung des Binomialkoeffizienten so aufziehen, dass kein Zwischenergebnis größer ist als das Endergebnis

Ich weiß. Aber Fakultäten braucht man nicht nur für Binomialkoeffizienten

Kentatschdis

Soweit ich weiss, kann man zu grosse Zahlen auch mit einer verkettetn Liste darstellen.
Erste Element ist die Einerstelle, zweites Element die Zehnerstelle usw. Man muss sich halt eine Klasse schreiben und die Operatoren für *, /, + usw mitprogrammieren.

Ist zwar ein wenig aufwendig, aber man hat das Problem der zu grossen Zahlen gelöst.
Ich könnte mir vorstellen, dass es eine LinkedList Bibliothek gibt, die man wahrscheinlich benutzen könnte. Wir haben die LinkedList damals komplett selber geschrieben, aber ich weiss auch nicht, wie fit du in C++ bist. Man muss sich mit Zeigern usw auskennen.

PhilippHToner

Kentatschdis schrieb:

Soweit ich weiss, kann man zu grosse Zahlen auch mit einer verkettetn Liste darstellen.
Erste Element ist die Einerstelle, zweites Element die Zehnerstelle usw. Man muss sich halt eine Klasse schreiben und die Operatoren für *, /, + usw mitprogrammieren.

Ist zwar ein wenig aufwendig, aber man hat das Problem der zu grossen Zahlen gelöst.
Ich könnte mir vorstellen, dass es eine LinkedList Bibliothek gibt, die man wahrscheinlich benutzen könnte. Wir haben die LinkedList damals komplett selber geschrieben, aber ich weiss auch nicht, wie fit du in C++ bist. Man muss sich mit Zeigern usw auskennen.

Das halte ich für Käse. Das ist ein absoluter Workaround der keinen Spass macht und völliger Unnütz. Wenn ich wirklich eine stabile Laufzeit haben will und bei großen Zahlen die Darstellung mit der Zeit eh sehr vage wird, kann ich gleich die diskrete Gammafunktion implementieren http://de.wikipedia.org/wiki/Gammafunktion.