Hitung kebalikan faktorial

30

Tulis kode terpendek yang akan mengambil bilangan real lebih besar dari 1 sebagai input dan akan menampilkan faktorial terbalik positifnya. Dengan kata lain, itu menjawab pertanyaan "nomor faktorial apa yang sama dengan angka ini?". Gunakan fungsi Gamma untuk memperluas definisi faktorial ke bilangan real apa pun seperti dijelaskan di sini .

Sebagai contoh:

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

karena 3! = 6dan3.390077654! = 10

Aturan

  • Dilarang menggunakan fungsi faktorial atau fungsi gamma bawaan, atau fungsi yang mengandalkan fungsi ini.
  • Program harus dapat menghitungnya hingga 5 digit desimal, dengan kemampuan teoritis untuk menghitungnya dengan presisi apa pun (Ini harus mengandung angka yang dapat dibuat arbitrer besar atau kecil untuk mendapatkan presisi arbitrer)
  • Bahasa apa pun diizinkan, kode terpendek dalam karakter akan menang.

Saya membuat contoh kerja di sini . Silahkan lihat.

Jens Render
sumber
2
Ini dapat menggunakan beberapa kasus uji lagi, khususnya untuk mencakup input nol dan negatif.
Peter Taylor
Saya mengedit bahwa input harus lebih besar dari 1 karena jika tidak ada jawaban muliple.
Jens Renders
1
Mungkin ada beberapa jawaban, kecuali jika Anda juga menambahkan persyaratan bahwa output harus lebih besar dari 1.
Peter Taylor
Contoh kerja Anda memberi 3,99999 ketika dimasukkan 24. Jadi, apakah solusi seperti itu dapat diterima?
rubik
ya karena ini dapat dilihat sebagai 4, ke 5 tempat desimal yang benar
Jens Renders

Jawaban:

13

Javascript (116)

Magics hitam di sini! Memberikan hasil dalam beberapa milidetik .
Hanya fungsi matematika dasar yang digunakan: 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)

Sayang sekali LaTeX tidak didukung pada codegolf tetapi pada dasarnya, saya kode a pemecah newton untuk f(y)=gamma(y)-n=0dan x=y-1(karena x!merupakan gamma(x+1)) dan perkiraan untuk gamma dan fungsi digamma.

Perkiraan gamma adalah Stirling Perkiraan
Digamma menggunakan rumus Euler Maclaurin
Fungsi digamma adalah turunan dari fungsi gamma dibagi dengan fungsi gamma:f'(y)=gamma(y)*digamma(y)

Tidak Disatukan:

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);

Kasus uji:

10 => 3.390062988090518
120 => 4.99999939151027
720 => 6.00000187248195
40320 => 8.000003557030217
3628800 => 10.000003941731514
Michael M.
sumber
Jawaban yang sangat bagus meskipun tidak memenuhi presisi yang diperlukan dan hanya berfungsi untuk angka kurang dari 706
Jens Renders
@JensRenders, well, saya telah menambahkan beberapa iterasi dari pemecah newton, mengubah tebakan awal dan perkiraan yang lebih baik untuk fungsi gamma. Itu harus sesuai dengan aturan sekarang. Biarkan saya sekarang jika tidak apa-apa :)
Michael M.
Ya, sekarang sempurna, saya memilihnya :)
Jens Renders
1
Anda bisa menghemat 1 char:n=prompt(M=Math)
Florent
Coba jalankan kode Anda dalam jumlah besar seperti $ 10 ^ {10 ^ 6} $, dan pastikan Anda mendapatkan hasil integer
David G. Stork
13

Mathematica - 74 54 49

Cara yang tepat akan menjadi

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

Jika kita hanya membatalkan tes ?NumberQitu masih akan berfungsi, tetapi membuang beberapa peringatan buruk, yang akan hilang jika kita beralih ke integrasi simbolis Integrate, tetapi ini akan ilegal (saya kira), karena fungsi akan secara otomatis dikonversi menjadi Gammafungsi. Kita juga bisa menyingkirkan fungsi eksternal dengan cara itu.

Bagaimanapun

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

Untuk melakukan input yang tepat, cukup definisi fungsi (tidak bisa membiarkan MatLab menang)

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

Jika faktorial bawaan diizinkan

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

Di atas tidak memberikan bilangan bulat (yang merupakan argumen untuk fungsi faktorial yang benar). Berikut ini tidak:

Floor[InverseFunction[Gamma][n]-1]
desir
sumber
Ahh semua fungsi bawaan itu! Saya tidak berpikir ini bisa dikalahkan kecuali dengan cara yang sama.
rubik
4
Mathematica sangat tidak adil untuk hal-hal matematika! : D
Michael M.
1
dari namanya sendiri MATHematica
Dadan
Apakah NumberQtes pola diperlukan? Atau mengasuh E^(-t)? Apakah kecurangan untuk mengubah NIntegrateke Integrate? Mungkin ... :)
orion
Ini berubah menjadi tantangan nyata;)
mmumboss
6

ised: 72 46 karakter

Ini hampir sangat cocok ... ada "bahasa" di luar sana yang tampaknya dimaksudkan untuk matematika golf: ised . Sintaksnya yang dikaburkan membuat kode yang sangat singkat (tidak ada variabel bernama, hanya slot memori integer dan banyak operator char tunggal yang serbaguna). Mendefinisikan fungsi gamma menggunakan integral, saya dapat 80 karakter acak

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

Di sini, slot memori $ 4 adalah fungsi faktorial, slot memori $ 6 fungsi pembagian dan slot memori $ 2 diharapkan akan disetel ke input (diberikan sebelum mengambil kode ini). Slot $ 0 dan $ 1 adalah batas pembelahan dua. Contoh panggilan (dengan asumsi kode di atas ada dalam fileinversefactorial.ised )

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

Tentu saja, Anda bisa menggunakan builtin! operator, dalam hal ini Anda turun ke 45 karakter

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

Hati-hati, prioritas operator terkadang aneh.

Edit: ingat untuk sebaris fungsi daripada menyimpannya. Kalahkan Mathematica dengan 72 karakter!

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

Dan menggunakan! builtin Anda mendapatkan 41.


Pembaruan tertunda setahun:

Saya baru menyadari ini sangat tidak efisien. Diturunkan hingga 60 karakter:

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

Jika utf-8 digunakan (Mathematica juga melakukannya), kita dapat 57:

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

Menulis ulang yang sedikit berbeda dapat memotongnya menjadi 46 (atau 27 jika menggunakan builtin!):

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

Dua karakter terakhir dapat dihapus jika Anda setuju dengan jawaban dicetak dua kali.

orion
sumber
Saya akan terkejut jika saya melihat seseorang mengalahkan ini: o
Jens Renders
@JensRenders: Saya baru saja melakukannya;)
mmumboss
Untuk mengklarifikasi diskusi tentang akurasi: diset oleh .1 (langkah integrasi) dan 99 (batas integrasi). Bisection menuju ke presisi mesin. Batas pembelahan @ 1,99 dapat dijaga pada 99 kecuali Anda ingin memasukkan angka di atas (99!).
orion
@mmumboss membuat Anda lagi :)
orion
5

MATLAB 54 47

Jika saya memilih tantangan yang tepat, MATLAB sangat bagus untuk bermain golf :). Dalam kode saya, saya menemukan solusi untuk persamaan (ux!) = 0 di mana Anda adalah input pengguna, dan x variabel untuk dipecahkan. Ini berarti bahwa u = 6 akan mengarah ke x = 3, dll ...

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

Akurasi dapat diubah dengan mengubah batas atas integral, yang ditetapkan pada 99. Menurunkan ini akan mengubah keakuratan output sebagai berikut. Misalnya untuk input 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;

dll.

mmumboss
sumber
Anda harus menentukan opsi untuk keakuratan karena ini diperlukan dalam aturan! "Ini harus berisi angka yang dapat dibuat sewenang-wenang besar atau kecil untuk mendapatkan presisi sewenang-wenang"
Jens Renders
Saya tidak melihatnya dalam solusi ised dan Mathematica juga? Tapi saya akan memeriksanya ..
mmumboss
1
Saya melihat angka 99 dalam versi ised, dan versi mathatica dipukuli bagaimanapun juga
Jens Renders
Mengingat posisi dalam kode, ini mungkin merupakan batas atas untuk integral. Dalam kode saya ini inf. Jadi ya, jika saya mengubah inf ini menjadi 99, jawaban saya menjadi kurang akurat, yang berarti bahwa angka ini mempengaruhi ketepatan, dan karena itu saya memenuhi aturan. Jika saya mengubahnya menjadi 99, saya bahkan menyimpan char;)
mmumboss
Tetapi setelah mengubah inf ke 99 apakah memenuhi presisi yang diperlukan?
rubik
3

Python - 199 karakter

Ok, jadi Anda akan membutuhkan banyak ruang stack dan banyak waktu, tapi hei, itu akan sampai di sana!

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)

Berikut ini pendekatan lain dengan rekursi yang lebih banyak lagi.

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)

Keduanya dapat diuji dengan >>>f(10,1) ketentuan Anda menetapkan batas rekursi sekitar 10.000. Akurasi lebih dari satu desimal kemungkinan tidak akan lengkap dengan batas rekursi yang realistis.

Menggabungkan komentar dan beberapa modifikasi, hingga 199 karakter.

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
sumber
2
Ini adalah code-golfpertanyaan, jadi Anda harus memberikan jawaban terpendek, yang menyatakan lamanya solusi Anda.
VisioN
Metode yang bagus tetapi masalahnya adalah Anda tidak dapat menjamin bahwa ini akan pernah menemukan jawabannya ... Juga, ini codegolf Anda mungkin mencoba untuk meminimalkan penggunaan karakter.
Jens Renders
1
Random Python () menggunakan Mersenne Twister yang saya percaya berjalan di ruang pelampung Python, sehingga harus selalu berakhir jika ada jawaban dalam toleransi.
intx13
Apakah maksud Anda bahwa ia mengembalikan setiap nilai float sebelum mengulanginya? jika itu yang terjadi maka kode ini akan valid jika Anda dapat mengatasi stack overflow
Jens Renders
2
Kode ini mampu, hanya saja Anda dan saya mungkin tidak punya waktu atau sumber daya komputer untuk menjalankannya sampai selesai;)
intx13
3

Python 2.7 - 215 189 karakter

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)

Pemakaian:

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

Untuk mengubah presisi: ubah 1e-5ke angka yang lebih kecil untuk presisi yang lebih besar, angka yang lebih besar untuk presisi yang lebih buruk. Untuk presisi yang lebih baik Anda mungkin ingin memberikan nilai yang lebih baike .

Ini hanya mengimplementasikan fungsi faktorial sebagai f, dan kemudian melakukan pencarian biner untuk mengasah nilai paling akurat dari kebalikan dari input. Asumsikan jawabannya kurang dari atau sama dengan 99 (itu tidak akan berhasil untuk jawaban 365 pasti, saya mendapatkan kesalahan matematika melimpah). Penggunaan ruang dan waktu yang sangat wajar, selalu berakhir.

Atau, ganti if abs(n-f(x))<=10**-5: print x;breakdengan print xuntuk mencukur 50 karakter . Ini akan berulang selamanya, memberi Anda perkiraan yang lebih dan lebih akurat. Tidak yakin apakah ini akan sesuai dengan aturan.

Claudiu
sumber
Saya tidak tahu situs itu untuk menghitung karakter. Saya selalu menggunakan cat file | wc -c.
rubik
@rubik: oh bagus, tidak terpikir untuk menggunakannya. keduanya cocok =)
Claudiu
2

dg - 131 133 byte

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

Karena dg menghasilkan bytecode CPython, ini juga harus dihitung untuk Python, tetapi oh ... Beberapa contoh:

$ 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

EDIT: Menambahkan dua byte karena saya tidak ingat bahwa itu juga harus menerima float!

rubik
sumber
Milik saya memberi 42.8006566063, sehingga mereka cocok dalam 5 digit presisi!
Claudiu
Itu keren! Saya tidak tahu di mana batas atas, tetapi harus pecah di suatu tempat. Untuk 1e100itu memberi:, 69.95780520000001untuk 1e150itu output 96.10586423000002, sedangkan untuk 1e200itu meledak. Tapi sungguh saya tidak tahu apakah hasil itu dapat diandalkan ...
rubik
1

R , 92 byte

Suatu fungsi,, gyang mengambil input zdan menghasilkan faktorial terbalik dari angka itu

Hampir bisa dipastikan ada golf lagi, jadi jika Anda melihat sesuatu yang dapat saya tingkatkan, beri tahu saya.

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)

Cobalah online!

Tidak Disatukan dan Dikomentari

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

Cobalah online!

Taylor Scott
sumber
0

Javascript (tanpa menggunakan loop!)

Untuk melakukan ini, saya menggunakan perkiraan numerik yang terkenal dari kebalikan dari perkiraan faktor Stirling , (dan juga mendapat inspirasi dari ini .. batuk .. batuk .. kode orang lain ...)

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
sumber