Binomialkoeffizient umkehren / Suche guten Algorithmus

Hallo miteinander,

ich brauche als Bestandteil eines größeren Algorithmus eine vernünftige Berechnungsmethode um den Parameter n eines Binomialkoeffizienten Z = Bin(n,k) zu berechnen.

Genauer:
* Bekannt sind Z und N.
* Gesucht ist ein K, sodass Z = Bin(N+K-1, N-1).
* Wenn es keine exakte Lösung gibt, dann soll dass K gewählt werden, das am nächsten dran ist, im Zweifel das nächstgrößere.

Bis jetzt habe ich folgende einfache aber rechenintensive Methode genommen:
1. Als Startwert für K habe ich einen anderen Parameter gewählt, der ungefähr in der Nähe sein dürfte.
2. Ich habe solange K um 1 erhöht, bis der Binomialkoeffizient > Z war. Und den Wert gespeichert.
3. Ich habe solange K um 1 erniedrigt, bis der Binomialkoeffizient < Z war.
4. Die bessere Näherung habe ich genommen.

Ich habe das Gefühl, dass das ganze wesentlich effizienter gestaltet werden könnte, ich weiß nur nicht wie. Eine binäre Suche scheidet ja aus, weil der Binomialkoeffizient nicht monoton in seinem Argument n ist.

Hat jemand eine Idee?

PeterTheMaster

n aus z=bin(n,k) bestimmen: weniger rechenintensiv, als einfach durchprobieren gehts schon. zuerst sicherstellen, dass k=min(k,n-k) (macht die produkte bisschen kleiner, spart multiplikationen).
dann z*k! = n*(n-1)...(n-k+1) verwenden, linke seite ausrechnen, rechts irgendwie anfangen, z.b. mit n ca. k-te wurzel aus linke seite. wenn zu klein (bei diesem anfang nicht der fall) eben links nen faktor ran, rechts einen weg, wenn zu gross andersrum. das waere meine ad hoc methode.

Hm, ja ich habe jetzt eine dieser Regeln eingebaut. Den zweiten Tipp mit dem z*k! = n*(n-1)...(n-k+1) habe ich aber nicht verstanden. Hier ist es so wie ich es jetzt habe. Immerhin schon kompakt und ich bin die Überläufe los, die ich vorher hatte.
Nicht wundern, es ist in einer ganz fiesen Programmiersprache Aber sie ist immerhin leserlich.

Dim current, last As Double
Dim n As Integer = k

' In Einerschritten aufwärts
current = 1.0
while current < Z
	n += 1
	last = current
	current += binomial(CUInt(n-1), CUInt(k-1))
End While

' Wahl der besseren Näherung
' Jetzt ist current >= Zustandszahl und last < Zustandszahl
If Z-last < current-Z Then
	n -= 1
End If

PeterTheMaster

was genau verstehste denn da nicht? du suchst k auf einander folgende zahlen, kennst aber nur ihr geometrisches mittel. also nimmste erstmal dieses her und bastelst daraus dein produkt, wenn das zu hoch ist, dividierst durch den hoechsten faktor und multiplizierst mit nem neuen kleinsten, sonst andersrum. das ganze sollte in etwa k/2 schritten fertig sein, auf jeden fall in k. wenn du dich genauer mit dem zusammenhang zwischen geometrischem und arithmetischem mittel beschaeftigst, kannst du sicherlich einen ziemlich guten startwert ermitteln, so dass nur noch wirklich wenig schritte noetig sind.

Wirdbald

z*k! = n*(n-1)...(n-k+1) verwenden, linke seite ausrechnen

Hm, wenn das ist wie er schreibt, dass die Zahlen so groß sind, dass er Probleme mit Überläufen hat, dann kann das hier doch keine Lösung sein, weil die Fakultät ja eher noch größere Zahlen liefert als ein Binomialkoeffizient, oder?

PeterTheMaster

na das ist doch nu wirklich eine sache der implementation, nicht des problem loesens. zieht man den faktor halt mit auf die rechte seite, von mir aus das z auch gleich mit, dann wird eben 1 anvisiert. dann sind die zahlen halt nicht um 1 voneinander entfernt, sondern um das entsprechende.