Binomialkoeffizient in C

[Nago]

Hi leute,

Wenn in C eine Funktion zur Berechnung eines Bk implementieren will nutze ich folgende Formel:

(n-k+i)/i (von i =1 bis K)

Jetzt gehört es zu meiner Aufgabe an zu geben für welches größtmögliche n noch korrekte ergebnisse geliefert werden.
Da ich mit solchen Fragen immer probleme habe dacht ich, ich frage mal den Rat der Weisen.
Ich gehe natürlich stark davon aus, das es mit den verwendeten Datentypen zusammenhängt. Also nehmen wir jetzt einfach mal an ich
nehme Integer.

Wie geh ich daran. Wie gesagt schätz ich mal ich muss mir angucken welchen Zahlenbereich int abdeckt, aber was dann? durch die multiplikationen und Divisonen ändert sich die größe ja ständig (schleife halt).

Solche Aufgaben gab es schon öfter, kann man sich irgendwie eine Funktion Schreiben, die sowas ausgibt, wenn so eine grenze erreicht wird?

[jabu]

Um uns seitenlange Abhandlungen mit zweifelhafter Treffsicherheit zu ersparen, müsste man schon etwas mehr über die Voraussetzungen wissen:

Wie lautet die ursprüngliche Aufgabenstellung (inkl. Definitionsbereiche, versteht sich)?
Ist diese Formel zwingend zur Implementierung vorgegeben (wäre völlig in Ordnung, aber nicht dass noch ein mathematischer Schritt erwartet wird)?
Soll es eher um C gehen (oder um Mathe)?
Müssen die Ergebnisse in jedem Fall hundertprozentig genau sein (oder sind kleinere Abweichungen erlaubt)?

Schon mal ein kleiner Wink: Ist der Quotient denn in jedem Fall als Ganzzahl darstellbar (weil du von Integer sprichst)?
Noch einer: Eine "natürliche" Grenze für (n) liegt bei ... (wir wollen dich nicht um deine Erkenntnis bringen ;)). Wenn man es also mathematisch betrachtet, dann kann man sich manche Überprüfung zur Laufzeit ersparen!
Anders wäre der Fall gelagert, wenn aufgrund bestimmter (k) bei bestimmten Algorithmen dann doch größere (n) erlaubt sind, sodass für jeden Einzelfall eine Berechnung angestellt werden müsste. Wenn es jedoch genügt, genau ein maximales (n) zu bestimmen, welches bei allen (k) hält, wobei der Algorithmus vorgegeben ist, läuft es auf eine einfache formale Lösung hinaus (wobei man die schon für den jeweiligen Wertebereich ausrechnen müsste, aber man wüsste es vorher).

(Das mit der "natürlichen" Grenze ist nicht ganz wörtlich gemeint, daher in Anführungszeichen, denn der verwendete Algorithmus hat logischerweise einen Einfluss. Von geschickten Optimierungen (Kürzen etc.) müsste man also absehen. Nimmt man aber die üblichen Formeln bzw. Algorithmen zum Vorbild und lässt (k) mal gedanklich hin- und herwandern, müsste eigentlich etwas bezüglich (n) auffallen.)

Nur eine Idee am Rande: Man könnte Zähler und Nenner separat halten, damit das in Integer geht. Das ähnelt dann stark einer anderen Formel, welche nicht ganz unbekannt ist (wobei sich wieder die Frage stellt, ob das noch im Sinne der Aufgabenstellung wäre)... Ganzzahlen hätten dann auch den Vorteil der Präzision. Dafür käme es bei den Einzelprodukten schnell zum Overflow.


Solche Aufgaben gab es schon öfter, kann man sich irgendwie eine Funktion Schreiben, die sowas ausgibt, wenn so eine grenze erreicht wird?
Wenn du eine portable Möglichkeit suchst, um Overflows zu erkennen, dann müssen die Überprüfungen unabhängig von der eigentlichen Berechnung erfolgen, was in der Regel bzw. zur Sicherheit bedeutet, dass du sie vorher vornimmst. Viele Tipps zu Overflows sind fehlerhaft, weshalb man nicht einfach irgendwas aus dem Web übernehmen sollte. Hier kannst du dich in erprobte Konzepte einlesen:
https://www.securecoding.cert.org/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow
Dann müsstest du noch aufpassen, dass dein Compiler die Überprüfungen nicht einfach wegoptimiert. Wenn es zur Übersetzungszeit so aussieht, als könnte der Fall nie eintreten oder als habe er keinerlei Auswirkungen, dann kann das schon mal passieren. Was in einem Debug-Build noch abgefangen wird - und demzufolge auffällt, kann also in einem Release-Build unentdeckt bleiben - bis es sich eines Tages mit voller Wucht auswirkt. Tests sind daher unerlässlich. Das ist aber ein Kapitel für sich, womit wir hier zu weit vom Thema abdriften würden.

[Nago]

Danke für deinen ausfürlichen Beitrag.
Also es geht bei der Aufgabe ums Programmieren, nicht um die Mathematik im eigentlichen Sinne.
Es soll ein programm in C geschrieben werden, das für 2 natürliche Zahlen a und b den Bk iterativ berechnet. (für möglichst große a)
Und es soll darauf geachtet werden, dass bei der Standardformel aufgrund der Fakultät, der Darstellungsbereich der Datentypen schnell erschöpft ist und man deswegen eine andere Funktion verwenden soll. Daher die oben angegebene. Da dort bei jedem Schleifendurchlauf auch dividiert wird wachsen, die Zahlen nicht so schnell. Und gemäß Wikipedia ist das daher auch die formel nach der zB Taschenrechner das machen.

Bis hierhin ist die Aufgabe kein Problem.
Aber dann soll man noch angeben, bis zu welchem a das geschriebene Programm noch korrekte Werte liefert. Und das war dann auch schon die ganze Aufgabe.

[jabu]

[...]
Danke für die Klarstellung, so ergibt das endlich einen Sinn für mich! :)

[Lehona]

Die Formel oben macht so keinen Sinn, willst du aus den einzelnen Ausdrücken die Summe bilden oder das Produkt? Ggf. mal einen Wikipediaartikel zu dieser Formel oder einfach eine Implementierung von dir in C verlinken, damit das besser zu verstehen ist.

Ansonsten: Das einfachste ist Ausprobieren. Wenn du signed Integer verwendest, könntest du mal gucken, wann die Summe oder das Produkt negativ wird - dann hast du dir vermutlich einen Overflow eingefangen.

[ojas]

... willst du aus den einzelnen Ausdrücken die Summe bilden oder das Produkt?

Produkt.


Ggf. mal einen Wikipediaartikel zu dieser Formel ... verlinken, ...

http://de.wikipedia.org/wiki/Binomialkoeffizient#Algorithmus_zur_effizienten_Berechnung

Das Zwischenergebnis wird mit (n - k + i) multipliziert und dann durch i dividiert. Eine Multiplikation mit (n - k + i)/i ist nicht praktikabel, weil (n - k + i)/i nicht unbedingt eine ganze Zahl ist.

Das schlimmste was dabei passieren kann ist, dass ein Zwischenergebnis mit n multipliziert wird. Das passiert auch tatsächlich, nämlich wenn i=k ist.

Da das Zwischenergebnis mit n multipliziert wird, darf es nicht größer als max/n sein, wobei max die größte Zahl ist, die mit dem von dir verwendeten Datentyp darstellbar ist.

Passende Werte für max findest du in <limits.h> (http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/limits.h.html), z.B. ULONG_MAX für unsigned long.

Der schlechteste Zeitpunkt für diese Multiplikation ist der, wenn das Zwischenergebnis möglichst groß ist. Das ist der Fall wenn k=n/2 ist. Das Zwischenergebnis ist zu diesem Zeitpunkt Binom(n, n/2)/2.

Mit einem CAS kannst du für konkrete Werte von max herausfinden, wann Binom(n,n/2)/2 > max/n ist.


Solche Aufgaben gab es schon öfter, kann man sich irgendwie eine Funktion Schreiben, die sowas ausgibt, wenn so eine grenze erreicht wird?

Arithmetik auf vorzeichenlosen Datentypen ist in jedem Fall wohldefiniert: Es gilt a∘b == (a∘b) % (max+1) für alle Rechenarten ∘. Du darfst also die Rechnung durchführen und anschließend das Ergebnis auf Plausibilität prüfen.

Arithmetik auf vorzeichenbehafteten Datentypen ist nur dann wohldefiniert, wenn das mathematische Ergebnis auch von dem Datentyp darstellbar ist. Hier musst du also schon vor der Operation sicherstellen, dass die Operanden zu einem darstellbarem Ergebnis führen. Für die Multiplikation zweier positiver Zahlen a*b kannst du z.B. prüfen, ob max/b ≤ a ist.

[Nago]

Also erstmal vielen danke für Anmerkungen und Hinweise, die haben mir geholfen ein paar Fehler in meiner Implementierung zu finden. (zb Multiplikation und Divison zu trennen).
Die Sache mit dem größtmöglichenn hab ich leider immernoch noch nicht raus, trotz der Hinweise von Ojas. Hab jetzt Unsigned long long int benutzt.
Morgen um 4 ist abgabe, werde mich vorher nochmal damit befassen. Aber vielen dank bis hierhin.^^

[ojas]

Es gibt keine Formel, die es erlaubt, mit konstanter Anzahl von Rechenoperationen Binomialkoeffizienten zu bestimmen. Die Anzahl der Rechenoperationen hängt von den Zahlen ab, dessen Binomialkoeffizienten du berechnen möchtest. Das hat zur Folge, dass die Ungleichung Binom(n, n/2) < m nicht nach n umgestellt werden kann. Du musst also auf einem anderen Weg bestimmen, wie groß dein n sein darf. Das kannst du vor der Kompilierung oder während der Berechnung machen.

Bestimmung wärend der Berechnung hat den Nachteil, dass du erst spät merkst, wenn dein n zu groß war. Vorteil ist aber, dass du erkennen kannst, dass dein k klein genug ist und so z.B. Binom(n, k) berechnet werden kann obwohl Binom(n, n/2) nicht mehr berechnet werden könnte.

Bei Bestimmung vor der Kompilierung musst du darauf achten, dass die größe von Datentypen platformabhängig ist. Zum Beispiel ist es üblich, dass ein long unter 64bit Windows 32 Bit hat, während es auf 64bit Linux 64 Bit hat.

Mit der Stirlingformel (http://de.wikipedia.org/wiki/Stirlingformel) kannst du die Fakultät schätzen, und damit auch den Binomialkoeffizienten. Das erleichtert die Bestimmung vor der Kompilierung.

[Multithread]

Gibt doch sicher bibliotheken für C für Datentypen über 64Bit:dnuhr:
zb. https://gmplib.org/
Wäre doch ne alternative für mehr genauigkeit^2^


In C# gibt es sowas nativ Bigint (https://msdn.microsoft.com/en-us/library/system.numerics.biginteger%28v=vs.110%29.aspx)