Grosse Zahlen

Hallo

Ich habe folgendes Problem: Um eine Formel auszuwerten, brauche ich die Fakultät (Mathematik: n! = 12345*...*n). Dazu habe ich folgende Methode geschrieben (Pseudo-Code):

private int Fak(int n)
{
int y=1;

  for (int u=1; u≤n; u++)  
  {  
        y*=u;  
  }  

  return y;  

}

Da sich hier aber sehr schnell sehr grosse Zahlen ergeben, reicht die Kapazität eines int nicht weit und sogar ein long kommt sehr schnell an seine Grenzen (ca. bei 34!). Mein Taschenrechner berechnet aber Fakultäten von 100! und mehr (und der hat wahrscheinlich weniger Rechenleistung). Hat jemand eine Idee, wie ich dieses Problem lösen kann?

Danke im voraus

mfg Hitman

Stichworte:

UInt64 (ulong)
Decimal
Double

einfach mal suchen

leider habe ich das in c# noch nicht gemacht, aber für C++ gibt es BigInt.
google doch mal danach, solche Datentypen für sehr große Zahlen sind mittlerweile, gerade für kryptographie, eh sehr wichtig.

Wenn du schon fakultät programmierst, hast du bestimmt lust so ein bigint selber zu programmierenn das machst du indem du ein Array aus integer machst. Das gesamte array ist immer die binärdarstellung deiner Zahl.
Multiplizieren kannst du indem du das Malnehmen wie in der Grundschule nachprogrammierst. Teilen auch. Das ergebnis ist wieder ein Array aus Int.

Um die Zahl auszugeben rechnest du immer modulo 10 und der Rest ist eine Ziffer für den Bildschirm.

Du kannst auch anstatt ein array auf integer einen String verwenden, wo du als zeichen immer eine Zahl von 0-9 speicherst, dies wäre dann leichter zu debuggen.

Viel spass

Wenn du lust hast, können wir in diesem Forum noch weiter diskutieren, ich liebe solche Themen 🙂

Na gut, du hast es nicht anders gewollt 🙂

Das ist die Funktion, welche es auszuwerten gilt (k-te Besselfunktion):

Danke für die Antworten

PS: Double, ULong und Decimal sind soweit ich weiss auch nur 64 Bit, wobei ULong einfach den die ganze Bandbreite für die positiven Zahlen einsetzt, während Long je 32 Bit für positive und negative Zahlen verwendet. Kann mich aber auch täuschen...

mfg Hitman

oh, ich habe eigentlich mit der Programmierung von bigint gerechnet.... Für was ist eigentlich die Besselfunktion? Dies doch eine unendliche Reihe, gibts da nicht bessere Methoden es zu lösen? Taylor Reihen?

Nein, die Besselfunktion konvergiert ja irgendwann. Sobald der Unterschied zwischen zwei Schritten kleiner als ein vorgegebener Wert ist, breche ich die Berechnung ab. Ich brauche diese Funktion um den Faltungskern einer Welle zu berechnen. Soll am Schluss eine interaktive Wasseroberfläche geben, die Wellenringe bildet, wenn man etwas hineinschmeisst... Dürfte ziemlich lustig werden, bis ich dieses Ziel erreicht habe (relativ komplex, das Ganze).

Aber um auf deinen BigInt zurückzukommen: Gehe ich richtig in der Annahme, dass die Stringvariante mehr Speicherplatz benötigt? Wie viel belegt eigentlich ein Stringzeichen?

mfg Hitman

Unter http://svn.myrealbox.com/source/trunk/mcs/class/Mono.Security/ findest Du die BigInteger-Implementierung von Mono.

Ich geb dem Steffen recht, verwende lieber vordefinierte Bibliotheken, da sparst du die viel Zeit und viel Fehlersuche.

Windows verwendet doch Unicode, also dürftest du pro Stringzeichen 2 Byte Speicher verbrauchen. Für eine dezimalzahl brauchst du aber nur 4 bit (also die stringvariante ist sehr verschwenderisch).

Aber ich glaube, deine Zahlen werden eh nicht länger als 1000 Stellen werden, da kannst du ruhig die Stringvariante nehmen

Du programmierst doch Wellen, deren Amplituden sind doch nicht so groß. Gibts da nicht speichersparendere und vorallem auch schnellere Algorithmen als die Besselfunktion? Wenn ich mir das richtig vorstelle, berechnest du doch mit der funktion für ein gegebenes x und y ein z. Wenn der Wert von z zu gross ist, wirst du es wohl nie auf den bildschirm zeichnen können. Die OpenGL-Routinen nehmen alle auch nur ein double und der datentype wäre dann auch viel zu klein

Wenn du das ganze numerisch sauber rechnen willst (Mittelschulmethoden sind häufig weder effizient noch stabil) siehe:

http://www.library.cornell.edu/nr/bookcpdf/c6-5.pdf
http://www.library.cornell.edu/nr/bookcpdf/c6-6.pdf

Numerical Recipes ist übrigens ein sehr gutes Buch, lohnt sich jedenfalls zu beschaffen wenn man öfters mal nummerisch rechnet (aber die C++ version nehmen, nicht die C version... lässt sich auch meist praktisch 1:1 nach C# portieren)

(oder du wartest bis Math.NET Numerics die Funktion implementiert hat (bzw. stellst ein feature request hier bei mir) 😉 )

Habe den Ansatz aus dem Buch "Gems - Spieleprogrammierung, Band 4" und dort wird mit der Besselfunktion gearbeitet. Da das Buch von professionellen Spieleprogrammierern geschrieben wurde, gehe ich mal davon aus, dass es sich um einen der schnellsten Algorithmen für dieses Problem handelt. Ich lasse mich aber gern eines besseren belehren 🙂

Danke schon mal für die vielen Tipps

mfg Hitman

Hm, und wie implementieren sie diesen Algorithmus? Die müssen doch dafür auch bigint oder sowas ähnliches verwenden um genug große Datentypen zu verwenden

Nee, wie es scheint, gibt es in der math.c-Bibliothek eine Besselfunktion j0(), welche sie verwenden... habe den Source aber bis anhin noch nicht gefunden. Ausserdem gibt es da so einen Typen namen Abramowitz oder so ähnlich, der hat eine vereinfachte Funktion für das Problem erfunden. Diese konnte ich aber auch noch nicht finden, und nur deshalb sein Buch zu kaufen... na ja, ich weiss nicht recht.

Aber vielleicht hat ja jemand von euch dieses Buch und könnte mir die Formel zur Verfügung stellen?

mfg Hitman

Zu Überläufen kommt es auch nur wenn man naiv 1:1 die Formel abtippt (und so etwa versucht die Fakultät direkt auszurechnen) ...

Die BesselJ Formel ist in dieser Form zwar mathematisch schön, numerisch aber imo ungeeignet (siehe meine Links oben (dort findest fu übrigens auch code für J0..))

Hallo allesamt!

Mal davon abgesehen wie man das jetzt implementiert, aber gibt es nicht die Möglichkeit große Zahlen zu trennen?

Ich meine der C64 konnte damals schon Fließkommazahlen mit über 100 Stellen nach dem Komma ausrechenen (Klar, hat Stunden gedauert 😉, und da waren Integer und Real noch viel drastischer eingeschränkt.

Was ich meine ist, dass man große Zahlen einfach mathematisch trennt und separat berechnet.

Da muss man zwar dann auf Bitebene runterbrechen, aber das bekommt nach meiner Einschätzung Hitman II hin 😉

Ciao
Norman-Timo

Kann man. Das nennt sich dann Arbitrary Precision Integer und ist z.b. im oben u.a. von steffen erwähnten BigInt (ursprünglich von IBM) implementiert.

Gibt übrigens auch einen CP Artikel zum Thema: http://www.codeproject.com/csharp/biginteger.asp

wie bei so vielen sachen auch, gibt es auf www.codeproject.com eine
fertige bibliotek, die fast alles kann, was Du brauchst.

Und das auch noch im source.

http://www.codeproject.com/csharp/biginteger.asp

Der Wassereffekt ist ein ganz einfacher Algorithmus. Fakultäten und große Zahlen braucht man dafür nicht. Man braucht nicht mal Fließkommazahlen.

Diese Seite hier erklärt den Algorithmus im Detail:
The Water Effect Explained

Ich hatte das mal mit der Seite als Grundlage in Java nachprogrammiert, zum Testen der Geschwindigkeit von SWT (GUI von Ecplise). Läuft flüssig und sieht realistisch aus.

Hier noch eine Seite mit weiteren Implementierungen, zu finden im Abschnitt "Physical Models/Water":
efg's Simulation and Modelling Page

Gruss
Pulpapex

Wie schon gesagt, die Wasseroberfläche soll nicht nur realistisch aussehen, sie soll auch interaktiv sein, d.h. die Wellen sollen von Hindernissen zurückprallen und sich abhängig von eingetauchten Objekten entsprechend verhalten. Man sollte zum Beispiel mit einer Spielfigur durch das Wasser waten können. Und das schafft der oben erwähnte Algorithmus, soweit ich das beurteilen kann, nicht. Aber die Seite enthält trotzdem noch einige interessante Ansätze.

Danke nochmal für die zahlreiche Beteiligung. War mehr als ich erwartet hatte 🙂

mfg Hitman

Ist natürlich sehr einfach, der Algorithmus und physikalisch wahrscheinlich nicht besonders korrekt. Aber es sieht zumindest realistisch aus.

Gegenstände werden von Wellen umspült. Ein bewegter Körper zieht einen Wellenkeil hinter sich her. Ein Tropfen breitet sich kreisförmig mit mehreren Wellenbergen aus. Alles so wie man es kennt.

Was z.B. nicht modelliert ist, ist das Verhalten bei unterschiedlichen Wassertiefen. Dass sich Wellen im flachen Gewässer auftürmen usw. Überschlagende Brecher und Brandung natürlich auch nicht. Und wirklich bewegtes Wasser, wie Strudel und Strömungen auch nicht. Nur Wellen.