long double reicht nicht aus

[Gast]

Wollte mir in VS 2005 ein kleines Programm machen, mit dem ich große Fakultäten berechnen kann.

Für Werte bis knapp 200 geht das auch ganz gut, nur dann geht dem grössten Datentyp long double wohl auch der Speicher aus.

Wie kann ich z.b. die fakultät von 100.000 berechnen, was brauche ich da?
denn im windows taschenrechner geht das problemlos!

[Markus89]

Wieso benutzt du double? Du brauchst doch keine Kommazahlen. Benutze doch einen 64bit Integer oder sowas.

[Trap]

Da brauchst du bignums. Gibt es für C/C++ in GMP (http://gmplib.org/).

Scheme, Lisp, Haskell, Java und andere moderne Sprachen haben es fertig eingebaut (mehr oder weniger geschickt).

[Gast]

welchen?

_int64 8 none –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

der reicht auch nicht aus :(
das is ja ne zahl mit hunderttausenden stellen oder so die da rauskommt

[RMC]

du kannst jede beliebige Arithmetik selber durchführen, mit Arrays..müssen nur groß genug sein.

[Monger]

Wie schon gesagt: für Fakultät solltest du selbstverständlich Ganzzahlentypen verwenden, und keine Gleitkommatypen.

In Java (und afaik auch in .NET) gibt es die BigInteger Klasse für im Prinzip beliebig große Zahlenkonstrukte, aber Vorsicht: schweinelangsam! Nur benutzen wenn es wirklich gar nicht anders geht!

[Gast]

Da brauchst du bignums. Gibt es für C/C++ in GMP (http://gmplib.org/).

Scheme, Lisp, Haskell, Java und andere moderne Sprachen haben es fertig eingebaut (mehr oder weniger geschickt).

das is doch nur für linux :(

[Coda]

Nein, ist es nicht.

[aths]

Wollte mir in VS 2005 ein kleines Programm machen, mit dem ich große Fakultäten berechnen kann.

Für Werte bis knapp 200 geht das auch ganz gut, nur dann geht dem grössten Datentyp long double wohl auch der Speicher aus.

Wie kann ich z.b. die fakultät von 100.000 berechnen, was brauche ich da?
denn im windows taschenrechner geht das problemlos!Dafür hatte ich mir mal eine String-Arithmetik geschrieben: Strings mit Integers multiplizieren, wobei die Multiplikation auf Additionen (genauer gesagt, jeweils Verdopplungen) abgebildet wurde.

[Gast]

das is doch nur für linux :(MSys ist dein Freund. So eine Art Unix-Emulator für Windows. Geht aber glaube ich nur mit dem MinGW Compiler. Das Programm zeigt dir eine unix-artige Kommandozeile an, auf der du dann diesen

./configure
make
make install

Kram eingeben kannst. Allerdings mußt du aufpassen, unter Unix würden da irgendwelche Sachen in irgendwelche Unix-Verzeichnisse (/usr/local/hastenichgesehen/...) kopieren, die unter Windows natürlich nicht existieren. Da mußt du dann noch manuell Hand anlegen, und diverse .h Files und libs in die entsprechenden Verzeichnisse deines MinGW-Compilers kopieren.

[HellHorse]

Ich kann mich nur den beiden Vorrednern anschliessen GMP (http://gmplib.org/). Gibt Bindings für Java, Python, Perl, Smalltalk, .... Ende der Diskussion.

aus dem lustigen Tachenrechner-Thread

#include <stdlib.h>
#include <stdio.h>
#include "gmp.h"

int factorial(unsigned long int op) {
mpz_t result;
mpz_init(result);
mpz_fac_ui(result, op);
mpz_out_str(stdout, 10, result);
mpz_clear(result);
return 0;
}

int main(int argc, char *argv[]) {
if (argc != 2) {
return EXIT_FAILURE;
}
long op = atol(argv[1]);
if (op < 0) {
return EXIT_FAILURE;
}
return factorial(op) == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
}

macht 100000! in etwa 0.3s.

[Monger]

Gibt Bindings für Java, Python, Perl, Smalltalk

Das hört sich jetzt noobish an, aber... was meinst du mit Binding? Gibt es irgendwo ne fertige Library für Java, oder muss ich irgendeinen hässlichen Umweg gehen, um die C++ Quellen da ranzuflanschen?

Ich hab auf die GMP Seite geschaut, hab aber bezüglich Java nichts finden können.


macht 100000! in etwa 0.3s.
Ich bin in Mathe ja ganz schlecht, aber wie kommen diese unglaublichen Ergebnisse zustande?!?
Ich kann mir grad überhaupt nicht vorstellen, wie man eine solche Multiplikation so dermaßen dramatisch optimieren kann.

[Trap]

Ich bin in Mathe ja ganz schlecht, aber wie kommen diese unglaublichen Ergebnisse zustande?!?
Ich kann mir grad überhaupt nicht vorstellen, wie man eine solche Multiplikation so dermaßen dramatisch optimieren kann.
Das ist eine Spezialfunktion für Fakultätsberechnung, die wird nicht stumpf alles aufmultiplizieren.

Ist sogar dokumentiert: http://gmplib.org/manual/Factorial-Algorithm.html#Factorial-Algorithm

[rotalever]

MSys ist dein Freund. So eine Art Unix-Emulator für Windows. Geht aber glaube ich nur mit dem MinGW Compiler. [...].
GMP kann man auch mit MS Visual C++ nutzen. Da gibt es irgendwo eine Internetseite, wo die das erklären, keine Ahnung mehr wo.

[HellHorse]

Das hört sich jetzt noobish an, aber... was meinst du mit Binding? Gibt es irgendwo ne fertige Library für Java, oder muss ich irgendeinen hässlichen Umweg gehen, um die C++ Quellen da ranzuflanschen?
Ist etwas mühsam. BigInteger in Kaffe und kissme verwenden ist, dort wäre es also super einfach. Bloss sind die halt discontinued (wurden mit Classpath gemerged). Für Classpath gibts ein RFC und einen Patch aber es wurde noch nicht integriert.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28664
http://www.nabble.com/-cp-patches--RFC:-PR-Classpath-28664---GMP-based-BigInteger-(bis)-t2717030.html

Die C API ist aber eigentlich ganz ok für eine C API. Wenn du nur etwas Arithmetik damit machen willst, lässt sich damit leben.