Berechnen Sie die Inverse der Fakultät

30

Schreiben Sie den kürzesten Code, der eine reelle Zahl größer als 1 als Eingabe akzeptiert und dessen positive Inverse Factorial ausgibt. Mit anderen Worten, es beantwortet die Frage "Welche Fakultät ist gleich dieser Zahl?". Verwenden Sie die Gamma-Funktion, um die Definition für Fakultät auf eine beliebige reelle Zahl zu erweitern, wie hier beschrieben .

Beispielsweise:

input=6 output=3 
input=10 output=3.390077654

weil 3! = 6und3.390077654! = 10

Regeln

  • Es ist verboten, eingebaute Fakultätsfunktionen oder Gammafunktionen oder Funktionen zu verwenden, die auf diesen Funktionen beruhen.
  • Das Programm sollte in der Lage sein, es mit 5 Dezimalstellen zu berechnen, mit der theoretischen Fähigkeit, es mit einer beliebigen Genauigkeit zu berechnen. (Es sollte eine Zahl enthalten, die beliebig groß oder klein gemacht werden kann, um eine beliebige Genauigkeit zu erhalten.)
  • Jede Sprache ist erlaubt, der kürzeste Code in Zeichen gewinnt.

Ich habe ein funktionierendes Beispiel hier . Guck mal.

Jens Renders
quelle
2
Dies könnte einige weitere Testfälle verwenden, insbesondere um null und negative Eingaben abzudecken.
Peter Taylor
Ich habe geändert, dass die Eingabe größer als 1 sein sollte, da es sonst mehrere Antworten geben könnte.
Jens Renders
1
Es kann ohnehin mehrere Antworten geben, es sei denn, Sie fügen eine Anforderung hinzu, dass die Ausgabe größer als 1 sein muss.
Peter Taylor
Ihr Arbeitsbeispiel ergibt 3.99999 bei Eingabe von 24. Ist eine solche Lösung akzeptabel?
Rubik
ja, weil dies als 4 bis 5 Dezimalstellen richtig gesehen werden kann
Jens Renders

Antworten:

13

Javascript (116)

Schwarze Magie hier! Gibt ein Ergebnis in wenigen Millisekunden .
Nur elementare mathematische Funktionen verwendet: ln, pow,exponential

x=9;n=prompt(M=Math);for(i=1e4;i--;)x+=(n/M.exp(-x)/M.pow(x,x-.5)/2.5066/(1+1/12/x+1/288/x/x)-1)/M.log(x);alert(x-1)

Schade LaTeX ist nicht auf codegolf unterstützt , aber im Grunde genommen, ich codiert ein newtonLöser für f(y)=gamma(y)-n=0und x=y-1(da x!ist gamma(x+1)) und Näherungswerte für Gamma und digamma Funktionen.

Die Gamma-Approximation ist die Stirling-Approximation. Die
Digamma-Approximation verwendet die Euler-Maclaurin-Formel.
Die Digamma-Funktion ist die Ableitung der Gamma-Funktion geteilt durch die Gamma-Funktion:f'(y)=gamma(y)*digamma(y)

Ungolfed:

n = parseInt(prompt());
x = 9; //first guess, whatever but not too high (<500 seems good)

//10000 iterations
for(i=0;i<10000;i++) {

  //approximation for digamma
  d=Math.log(x);

  //approximation for gamma
  g=Math.exp(-x)*Math.pow(x,x-0.5)*Math.sqrt(Math.PI*2)*(1+1/12/x+1/288/x/x);

  //uncomment if more precision is needed
  //d=Math.log(x)-1/2/x-1/12/x/x+120/x/x/x/x;
  //g=Math.exp(-x)*Math.pow(x,x-0.5)*Math.sqrt(Math.PI*2)*(1+1/12/x+1/288/x/x-139/51840/x/x/x);

  //classic newton, gamma derivative is gamma*digamma
  x-=(g-n)/(g*d);
}

alert(x-1);

Testfälle:

10 => 3.390062988090518
120 => 4.99999939151027
720 => 6.00000187248195
40320 => 8.000003557030217
3628800 => 10.000003941731514
Michael M.
quelle
Sehr nette Antwort, obwohl es nicht die erforderliche Präzision erfüllt und es funktioniert nur für Zahlen unter 706
Jens Renders
@JensRenders, nun, ich habe einige Iterationen des Newton-Lösers hinzugefügt, die anfängliche Vermutung und eine bessere Approximation für die Gammafunktion geändert. Das sollte jetzt den Regeln entsprechen. Lassen Sie mich jetzt, wenn es in Ordnung ist :)
Michael M.
Ja, jetzt ist es perfekt, ich habe dafür gestimmt :)
Jens Renders
1
Sie könnten 1 Zeichen sparen:n=prompt(M=Math)
Florent
Versuchen Sie, Ihren Code mit einer großen Zahl wie $ 10 ^ {10 ^ 6} $ auszuführen und sicherzustellen, dass Sie ein ganzzahliges Ergebnis erhalten
David G. Stork,
13

Mathematica - 74 54 49

Der richtige Weg wird sein

f[x_?NumberQ]:=NIntegrate[t^x E^-t,{t,0,∞}]
x/.FindRoot[f@x-Input[],{x,1}]

Wenn wir den Test einfach fallen ?NumberQlassen, funktioniert er immer noch, wirft aber einige üble Warnungen, die verschwinden, wenn wir auf symbolische Integration umstellen. IntegrateDies wäre jedoch illegal (ich nehme an), da die Funktion automatisch in konvertiert würdeGamma Funktion . Auch können wir auf diese Weise die externe Funktion loswerden.

Sowieso

x/.FindRoot[Integrate[t^x E^-t,{t,0,∞}]-Input[],{x,1}]

Um mit der richtigen Eingabe fertig zu werden, einfach Funktionsdefinition (MatLab kann nicht gewinnen)

x/.FindRoot[Integrate[t^x E^-t,{t,0,∞}]-#,{x,1}]&

Wenn eingebaute Fakultät erlaubt wäre

N@InverseFunction[#!&]@Input[]

Das obige gibt keine ganze Zahl an (was das Argument für eine wahre Fakultätsfunktion ist). Das Folgende tut:

Floor[InverseFunction[Gamma][n]-1]
swish
quelle
Ahh all diese eingebauten Funktionen! Ich denke nicht, dass das schlagbar ist, außer auf ähnliche Weise.
Rubik
4
Mathematica ist so unfair für Mathe-Zeug! : D
Michael M.
1
aus dem Namen selbst MATHematica
Dadan
Ist ein NumberQMustertest erforderlich? Oder parens in E^(-t)? Ist es Betrug drehen NIntegratezu Integrate? Wahrscheinlich ... :)
Orion
Es wird eine echte Herausforderung;)
mmumboss
6

ised: 72 46 Zeichen

Das passt fast perfekt ... es gibt da draußen eine "Sprache", die genau für Mathe-Golf gedacht zu sein scheint: ised . Seine verschleierte Syntax sorgt für einen sehr kurzen Code (keine benannten Variablen, nur ganzzahlige Speicherplätze und viele vielseitige einzelne Zeichenoperatoren). Wenn ich die Gammafunktion mit einem Integral definiere, habe ich sie auf 80 scheinbar zufällige Zeichen gebracht

@4{:.1*@+{@3[.,.1,99]^x:*exp-$3}:}@6{:@{$4::@5avg${0,1}>$2}$5:}@0,0@1,99;$6:::.

Hier ist der Speicherplatz $ 4 eine Fakultätsfunktion, und es wird erwartet, dass der Speicherplatz $ 6 als Bisektionsfunktion und der Speicherplatz $ 2 als Eingabe festgelegt werden (angegeben, bevor dieser Code bezogen wird). Die Slots $ 0 und $ 1 sind die Halbierungsgrenzen. Aufrufbeispiel (vorausgesetzt obiger Code ist in Datei inversefactorial.ised)

bash> ised '@2{556}' --f inversefactorial.ised
556
5.86118

Natürlich könnte man das eingebaute benutzen! Operator, in diesem Fall erhalten Sie bis zu 45 Zeichen

@6{:@{{@5avg${0,1}}!>$2}$5:}@0,0@1,99;$6:::.

Vorsicht, Bedienerpräzision ist manchmal seltsam.

Bearbeiten: Es wurde daran gedacht, die Funktionen zu integrieren, anstatt sie zu speichern. Besiege Mathematica mit 72 Charakteren!

@0,0@1,99;{:@{{:.1*@+{@3[.,.1,99]^x:*exp-$3}:}::@5avg${0,1}>$2}$5:}:::.

Und mit dem! Eingebaut bekommst du 41.


Ein Jahr überfälliges Update:

Mir ist gerade aufgefallen, dass dies sehr ineffizient ist. Golf bis zu 60 Zeichen:

@0#@1,99;{:@{.1*@3[.,.1,99]^@5avg${0,1}@:exp-$3>$2}$5:}:::.

Wenn utf-8 verwendet wird (Mathematica tut es auch), erhalten wir zu 57:

@0#@1,99;{:@{.1*@3[.,.1,99]^@5avg${0,1}·exp-$3>$2}$5:}∙.

Ein etwas anderes Umschreiben kann es auf 46 (oder 27, wenn es eingebaut ist!) Reduzieren:

{:x_S{.5@3[.,.1,99]^avgx·exp-$3*.1<$2}:}∙∓99_0

Die letzten beiden Zeichen können entfernt werden, wenn die Antwort zweimal gedruckt werden muss.

orion
quelle
Ich wäre überrascht, wenn jemand dies schlagen würde: o
Jens Renders
@ JensRenders: Ich habe es gerade getan;)
mmumboss
Um die Diskussion über die Genauigkeit zu verdeutlichen: Sie wird durch .1 (Integrationsschritt) und 99 (Integrationslimit) festgelegt. Bisection setzt auf Maschinengenauigkeit. Die Bisektionsgrenze bei 1,99 kann bei 99 gehalten werden, es sei denn, Sie möchten Zahlen über (99!) Eingeben.
Orion
@ mmumboss hast du wieder :)
orion
5

MATLAB 54 47

Wenn ich die richtigen Herausforderungen wähle, ist MATLAB wirklich gut zum Golfen geeignet :). In meinem Code finde ich die Lösung für die Gleichung (ux!) = 0, in der u die Benutzereingabe und x die zu lösende Variable ist. Dies bedeutet, dass u = 6 zu x = 3 usw. führt.

@(x)fsolve(@(y)u-quad(@(x)x.^y./exp(x),0,99),1)

Die Genauigkeit kann durch Ändern der Obergrenze des Integrals, die auf 99 eingestellt ist, geändert werden. Wenn Sie diese verringern, ändert sich die Genauigkeit der Ausgabe wie folgt. Zum Beispiel für eine Eingabe von 10:

upper limit = 99; answer = 3.390077650833145;
upper limit = 20; answer = 3.390082293675363;
upper limit = 10; answer = 3.402035336604546;
upper limit = 05; answer = 3.747303578099607;

etc.

mmumboss
quelle
Sie sollten die Option für die Genauigkeit angeben, da dies in den Regeln erforderlich ist! "Es sollte eine Zahl enthalten, die beliebig groß oder klein gemacht werden kann, um eine beliebige Genauigkeit zu erhalten"
Jens Renders
Ich sehe es auch nicht in den ised- und Mathematica-Lösungen? Aber ich werde es untersuchen ..
mmumboss
1
Ich sehe die Nummer 99 in der ised-Version, und die mathematica-Version ist sowieso geschlagen
Jens Renders
Aufgrund der Position im Code ist dies wahrscheinlich die Obergrenze für das Integral. In meinem Code ist dies inf. Also ja, wenn ich diese inf in 99 ändere, wird meine Antwort ungenauer, was bedeutet, dass diese Zahl die Genauigkeit beeinflusst und ich die Regeln erfülle. Wenn ich es auf 99 ändere, spare ich sogar ein
Zeichen
Aber nach der Änderung von inf auf 99 wird die erforderliche Präzision erreicht?
Rubik
3

Python - 199 Zeichen

Ok, du wirst also viel Stapelplatz und viel Zeit brauchen, aber hey, es wird dort ankommen!

from random import *
from math import e
def f(x,n):
    q=randint(0,x)+random()
    z=0
    d=0.1**n
    y=d
    while y<100:
            z+=y**q*e**(-y)*d
            y+=d
    return q if round(z,n)==x else f(x,n)

Hier ist ein weiterer Ansatz mit noch mehr Rekursion.

from random import *
from math import e
def f(x,n):
    q=randint(0,x)+random()
    return q if round(h(q,0,0.1**n,0),n)==x else f(x,n)
def h(q,z,d,y):
    if y>100:return z
    else:return h(q,z+y**q*e**(-y)*d,d,y+d)

Beide können mit getestet werden >>>f(10,1) vorausgesetzt, Sie legen das Rekursionslimit auf 10000 fest. Bei mehr als einer Dezimalstelle wird wahrscheinlich kein realistisches Rekursionslimit erreicht.

Mit Kommentaren und ein paar Modifikationen, bis zu 199 Zeichen.

from random import*
from math import*
def f(x,n):
    q=random()*x+random()
    z=y=0
    while y<100:
            z+=y**q*e**-y*0.1**n
            y+=0.1**n
    return q if round(z,n)==x else f(x,n)
intx13
quelle
2
Da dies eine code-golfFrage ist, müssen Sie die kürzeste Antwort geben und die Länge Ihrer Lösung angeben.
VisioN
Eine nette Methode, aber das Problem ist, dass Sie nicht garantieren können, dass dies jemals die Antwort finden wird ... Auch dies ist Codegolf zo, Sie könnten versuchen, den Zeichengebrauch zu minimieren.
Jens Renders
1
Pythons random () verwendet einen Mersenne-Twister, von dem ich glaube, dass er den Raum von Pythons Floats abläuft. Daher sollte er immer enden, wenn eine Antwort innerhalb der Toleranz liegt.
Intx13
Meinen Sie damit, dass jeder Float-Wert zurückgegeben wird, bevor einer wiederholt wird? Wenn dies der Fall ist, ist dieser Code gültig, wenn Sie in der Lage sind, den Stapelüberlauf zu überwinden
Jens Renders
2
Der Code ist in der Lage, es ist nur so, dass Sie und ich möglicherweise weder die Zeit noch die Computerressourcen haben, um ihn
vollständig
3

Python 2.7 - 215 189 Zeichen

f=lambda t:sum((x*.1)**t*2.71828**-(x*.1)*.1for x in range(999))
n=float(raw_input());x=1.;F=0;C=99
while 1:
 if abs(n-f(x))<1e-5:print x;break
 F,C,x=f(x)<n and(x,C,(x+C)/2)or(F,x,(x+F)/2)

Verwendung:

# echo 6 | python invfact_golf.py
2.99999904633
# echo 10 | python invfact_golf.py
3.39007514715
# echo 3628800 | python invfact_golf.py
9.99999685376

So ändern Sie die Präzision: Ändern Sie die Genauigkeit 1e-5auf eine kleinere Zahl, um eine höhere Genauigkeit zu erzielen, und auf eine größere Zahl, um eine schlechtere Genauigkeit zu erzielen. Für eine bessere Genauigkeit möchten Sie wahrscheinlich einen besseren Wert für angeben e.

Dies implementiert lediglich die Fakultätsfunktion as fund führt dann eine binäre Suche durch, um den genauesten Wert der Inverse der Eingabe zu ermitteln. Angenommen, die Antwort ist kleiner oder gleich 99 (bei einer Antwort von 365 würde dies nicht funktionieren, da ich einen mathematischen Überlauffehler erhalte). Sehr vernünftige Raum- und Zeitnutzung, endet immer.

Alternativ ersetzt if abs(n-f(x))<=10**-5: print x;breakmit print xabrasieren 50 Zeichen . Es wird für immer wiederholt und gibt Ihnen eine immer genauere Schätzung. Ich bin mir nicht sicher, ob dies mit den Regeln übereinstimmt.

Claudiu
quelle
Ich kannte diese Seite nicht, um Zeichen zu zählen. Ich benutze immer cat file | wc -c.
Rubik
@rubik: oh schön, hätte nicht gedacht, das zu benutzen. beide passen zusammen =)
Claudiu
2

dg - 131 133 Bytes

o,d,n=0,0.1,float$input!
for w in(-2..9)=>while(sum$map(i->d*(i*d)**(o+ 10**(-w))/(2.718281**(i*d)))(0..999))<n=>o+=10**(-w)
print o

Da dg CPython-Bytecode erzeugt, sollte dies auch für Python gelten, aber oh ... Einige Beispiele:

$ dg gam.dg 
10
3.3900766499999984
$ dg gam.dg 
24
3.9999989799999995
$ dg gam.dg 
100
4.892517629999997
$ dg gam.dg 
12637326743
13.27087070999999
$ dg gam.dg  # i'm not really sure about this one :P it's instantaneous though
28492739842739428347929842398472934929234239432948923
42.800660880000066
$ dg gam.dg  # a float example
284253.232359
8.891269689999989

BEARBEITEN: Zwei Bytes hinzugefügt, weil ich mich nicht daran erinnerte, dass es auch Floats akzeptieren sollte!

rubik
quelle
Meins gibt 42.8006566063, damit sie innerhalb von 5 Stellen der Genauigkeit übereinstimmen!
Claudiu
Das ist großartig! Ich weiß nicht, wo sich die Obergrenze befindet, aber sie sollte irgendwo brechen. Für 1e100sie gibt: 69.95780520000001für 1e150sie gibt 96.10586423000002, während für 1e200sie explodiert. Aber ich weiß wirklich nicht, ob diese Ergebnisse zuverlässig sind ...
Rubik
1

R , 92 Bytes

Eine Funktion, gdie zdie inverse Fakultät dieser Zahl annimmt und ausgibt

Es gibt mit ziemlicher Sicherheit noch mehr zu tun. Wenn Sie also etwas sehen, das ich verbessern kann, lassen Sie es mich bitte wissen.

library(pryr)
g=f(z,uniroot(f(a,integrate(f(x,x^a*exp(-x)),0,Inf)$v-z),c(0,z+1),tol=1e-9)$r)

Probieren Sie es online!

Ungolfed und Kommentiert

library(pryr)                     # Add pryr to workspace
inv.factorial = f(z,              # Declare function which  
  uniroot(                        # Finds the root of
    f(a, integrate(               # The integral of 
      f(x, x^a*exp(-x))           # The gamma function
        ,0 ,Inf                   # From 0 to Infinity
      )$value-z                   # Minus the input value, `z`
    ), c(0, z+1),                 # On the bound of 0 to z+1
    tol = 1e-323                  # With a specified tolerance
  )$root                          # And outputs the root
)                                 # End function

Probieren Sie es online!

Taylor Scott
quelle
0

Javascript (ohne Schleifen!)

Zu diesem Zweck habe ich eine bekannte numerische Approximation der Umkehrung der Stirling-Faktoriellen Approximation verwendet (und mich auch von diesem ... Husten ... Husten ... Code von jemand anderem inspirieren lassen ...).

function f(n){
    if(n==1) return 1;
    else if(n==2) return 2;
    else if(n==6) return 3;
    else if(n==24) return 4;
    else{
        return Math.round((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))/Math.log((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))))/Math.log((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))/Math.log((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))))))
    }
}
Antonio Ragagnin
quelle