Wszystkiego najlepszego z okazji Dnia Pi! Bez żadnego powodu staram się zbudować estymator Monte Pi Carlo tak krótki, jak to możliwe. Czy możemy zbudować taki, który zmieści się w tweecie?
Aby wyjaśnić, mam na myśli typowe podejście do rysowania losowych punktów z kwadratu jednostkowego i obliczania stosunku, który mieści się w okręgu jednostkowym. Liczba próbek może być zakodowana na stałe lub nie. Jeśli je kodujesz na stałe, musisz użyć co najmniej 1000 próbek. Wynik może zostać zwrócony lub wydrukowany jako zmiennoprzecinkowy, stały punkt lub liczba wymierna.
Żadnych funkcji triggera ani stałych Pi, musi być podejście Monte Carlo.
To jest kod golfowy, więc wygrywa najkrótsze przesłanie (w bajtach).
code-golf
random
pi
approximation
keegan
źródło
źródło
((0..4e9).map{rand**2+rand**2<1}.to_s.sub(/./,"$1.")
map
daje ci tablicytrue
ifalse
?.filter{...}.size
powinien jednak działać.Odpowiedzi:
Kod maszynowy 80386,
4038 bajtówHexdump kodu:
Jak zdobyć ten kod (z języka asemblera):
Jest to funkcja korzystająca z
fastcall
konwencji wywoływania MS (liczba iteracji jest przekazywana do rejestruecx
). Zwraca wynik wst
rejestrze.Zabawne rzeczy na temat tego kodu:
rdrand
- zaledwie 3 bajty, aby wygenerować losową liczbę!D
) z kwadratowym promieniem (2^32
) odbywa się automatycznie - flaga przenoszenia zawiera wynik.źródło
eax
; temul
wielokrotności każe mu przez siebie i stawia wysoki udział wedx
; dolna częśćeax
jest odrzucana.Matlab / Octave, 27 bajtów
Wiem, że już istnieje odpowiedź Matlab / Octave, ale wypróbowałem własne podejście. Wykorzystałem fakt, że całka
4/(1+x^2)
między 0 a 1 to pi.źródło
R, 40 (lub 28 lub 24 przy użyciu innych metod)
Python 2, 56
Kolejny Python, jeśli dozwolone jest numpy, ale dość podobny do Matlab / Octave:
źródło
Mathematica,
424039 bajtów (lub 31/29?)Mam trzy rozwiązania o wielkości 42 bajtów:
Wszystkie są nienazwanymi funkcjami, które pobierają liczbę próbek
n
i zwracają racjonalne przybliżenie π. Najpierw wszystkie generująn
punkty na kwadracie jednostki w kwadrancie dodatnim. Następnie określają liczbę próbek, które znajdują się w okręgu jednostkowym, a następnie dzielą przez liczbę próbek i mnożą przez4
. Jedyna różnica polega na tym, w jaki sposób określają liczbę próbek w okręgu jednostkowym:Count
pod warunkiem, żeNorm[p] < 1
.1
a następnie zaokrągla w górę. To zmienia liczby wewnątrz okręgu jednostki na1
i na zewnątrz na0
. Potem podsumowuję je wszystkieTr
.1.5
, więc mogę użyćRound
zamiastCeiling
.Aaaaaand podczas pisania tej góry, to dotarło do mnie, że rzeczywiście istnieje krócej rozwiązanie, jeśli po prostu odjąć od
2
a następnie użyćFloor
:lub zapisywanie innego bajtu za pomocą operatorów podłogowych lub sufitowych Unicode:
Należy zauważyć, że trzy rozwiązania oparte zaokrąglenia można również pisane
Mean
zamiastTr
i bez/#
, znowu dla tych samych bajtów.Jeśli inne podejścia oparte na Monte Carlo są w porządku (konkretnie ten, który wybrał Peter), mogę zrobić 31 bajtów poprzez oszacowanie całki lub 29 za pomocą całki , tym razem podanej jako liczba zmiennoprzecinkowa:
√(1-x2)
1/(1+x2)
źródło
CJam,
27 2322 lub 20 bajtów2 bajty zapisane dzięki Runner112, 1 bajt zapisany dzięki Sp3000
Pobiera na wejściu liczbę iteracji ze STDIN.
Jest to tak proste, jak to możliwe. Oto najważniejsze kroki:
Rozszerzenie kodu :
Wypróbuj online tutaj
Jeśli średnia wartość
1/(1+x^2)
jest również uważana za Monte Carlo, można to zrobić w 20 bajtach:Wypróbuj tutaj
źródło
1dmr
zamiastKmrK/
i sprawdź, czy suma kwadratów jest większa niż 1i
zamiast1>
(myślałem, że ta była szczególnie sprytna) .i
Sztuką jest naprawdę fajnie! I niech to szlag brak dokumentacji dla1dmr
Python 2,
7775 bajtówUżywa 4000 próbek do zapisania bajtów
1e3
.źródło
...*8000;print a/2e3
.Commodore 64 Basic, 45 bajtów
Podstawienia PETSCII:
─
=SHIFT+E
,/
=SHIFT+N
,┌
=SHIFT+O
Generuje 1000 punktów w pierwszej ćwiartce; dla każdego dodaje prawdziwość „x ^ 2 + y ^ 2 <1” do bieżącej liczby, a następnie dzieli liczbę przez 250, aby uzyskać
pi
. (Obecność znaku minus wynika z tego, że na C64 „true” = -1.)źródło
(1)
zrobić?/
nie jest symbolem podziału, lecz postacią wytwarzaną przez pisanieSHIFT+N
na klawiaturze Commodore 64.R/(1)
to formularz skrótu dlaRND(1)
, tj. „wygeneruj liczbę losową z zakresu od 0 do 1 przy użyciu bieżącego ziarna RNG”.J, 17 bajtów
Oblicza średnią wartość
40000
przykładowych wartości funkcji4*sqrt(1-sqr(x))
w zakresie[0,1]
.Łatwo
0 o.x
wracasqrt(1-sqr(x))
.źródło
> <> (Ryba) , 114 bajtów
Teraz> <> nie ma wbudowanego generatora liczb losowych. Ma jednak funkcję, która wysyła wskaźnik w losowym kierunku. Generator liczb losowych w moim kodzie:
Zasadniczo generuje losowe bity, które tworzą liczbę binarną, a następnie konwertuje tę losową liczbę binarną na dziesiętną.
Reszta to zwykłe punkty w podejściu kwadratowym.
Sposób użycia: po uruchomieniu kodu należy upewnić się, że stos został wstępnie wypełniony (-v w interpreterie w języku Python), na przykład liczbą próbek, na przykład
zwraca
źródło
Matlab lub Octave 29 bajtów (dzięki flawr!)
(Nie jestem pewien, czy <1 jest w porządku. Przeczytałem, że powinno być <= 1. Ale jak duże jest prawdopodobieństwo narysowania dokładnie 1 ...)
Matlab lub Octave 31 bajtów
źródło
mean(sum(rand(2,4e6).^2)<1)*4
.Java, 108 bajtów
Cztery tysiące iteracji, dodając 0,001 za każdym razem, gdy punkt znajduje się wewnątrz okręgu jednostki. Całkiem podstawowe rzeczy.
Uwaga: Tak, wiem, że mogę zrzucić cztery bajty, zmieniając
π
znak na jednobajtowy. Podoba mi się to w ten sposób.źródło
JavaScript: 62 bajtów
Użyłem poprzedniej (teraz usuniętej) odpowiedzi javascript i ogoliłem 5 bajtów.
źródło
GolfScript (34 znaki)
Demo online
Wykorzystuje stały punkt, ponieważ GS tak naprawdę nie ma zmiennoprzecinkowego. Lekko nadużywa użycia punktu stałego, więc jeśli chcesz zmienić liczbę iteracji, upewnij się, że jest to dwukrotność potęgi dziesięciu.
Kredyt dla XNOR dla danej metody Monte Carlo zatrudniony.
źródło
Python 2,
908581 bajtówzwraca
3.14120037157
na przykład. Liczba próbek wynosi 4782969 (9 ^ 7). Możesz uzyskać lepsze pi z 9 ^ 9, ale będziesz musiał uzbroić się w cierpliwość.źródło
range(9**7)
ze[0]*9**7
albo coś, bo nie używaszi
. A lista nie jest zbyt długa, aby napotkać problemy z pamięcią.range()
ale zupełnie zapomniałem tej sztuczki.[0]9**7
nie jest poprawna składnia.Rubin, 39 bajtów
Jedną z głównych zalet jest to, że można w nim stosować
8e5
notację, dzięki czemu można go rozszerzyć do ~ 8e9 próbek w tej samej liczbie bajtów programu.źródło
Perl 6 , 33 bajtów
Wypróbuj online!
Jest to funkcja, która przyjmuje liczbę próbek jako argument.
źródło
Scala,
877766 bajtówźródło
1000
się8000
i250d
z2e4
wami zarówno zapisać bajt i zwiększenie liczby próbek przez współczynnik 8.Pure Bash, 65 bajtów
Pobiera pojedynczy parametr wiersza polecenia, który jest mnożony przez 4, aby podać liczbę próbek. Arytmetyka Bash jest tylko liczbą całkowitą, więc wynik jest racjonalny. Można to przesłać do
bc -l
końcowego podziału:źródło
Joe ,
20 lat19 bajtówUwaga: ta odpowiedź nie jest konkurencyjna, ponieważ wersja 0.1.2, która dodała losowość, została wydana po tym wyzwaniu.
Nazwana funkcja F:
Funkcja bez nazwy:
Oba biorą próbkę jako argument i zwracają wynik. Jak oni pracują?
Przykładowe przebiegi:
źródło
dc, 59 znaków (białe znaki są ignorowane)
Przetestowałem to na Planie 9 i OpenBSD, więc wyobrażam sobie, że będzie działać na Linuksie (GNU?)
dc
.Objaśnienie według wiersza:
i
jeśli 1 jest większy niż suma ich kwadratów] w rejestrzeu
.x
o 1] w rejestrzei
.u
, rejestr przyrostowym
, a następnie uruchom rejestr,z
jeśli rejestrm
jest większy niż rejestrn
] w rejestrzez
.Ustaw skalę na 5 miejsc po przecinku.
z
.x
(liczbę trafień) według rejestrun
(liczbę punktów), pomnóż wynik przez 4 i wydrukuj.Oszukałem jednak:
Program potrzebuje zapasów liczb losowych od 0 do 1.
Stosowanie:
Testowe uruchomienie:
Teraz z mniejszym oszustwem (100 bajtów)
Ktoś zwrócił uwagę, że mogę załączyć prosty prng.
http://en.wikipedia.org/wiki/RANDU
Nie golfił
Testowe uruchomienie:
źródło
Pyth, 19 lat
Podaj żądaną liczbę iteracji jako dane wejściowe.
Demonstracja
Ponieważ Pyth nie ma funkcji „Losowa liczba zmiennoprzecinkowa”, musiałem improwizować. Program wybiera dwie losowe liczby całkowite dodatnie mniejsze niż wartość wejściowa, kwadraty, sumy i porównywane z kwadratem wejściowym. Wykonano to kilka razy równe wartości wejściowej, a następnie wynik pomnożono przez 4 i podzielono przez wartość wejściową.
W pokrewnych wiadomościach wkrótce dodam do Pytha losową liczbę zmiennoprzecinkową. Ten program nie korzysta jednak z tej funkcji.
Jeśli interpretujemy „Wynik może zostać zwrócony lub wydrukowany jako zmiennoprzecinkowy, stały punkt lub liczba wymierna”. swobodnie, wystarczy wydrukować licznik i mianownik powstałej frakcji. W tym wypadku:
Pyth, 18 lat
Jest to identyczny program, z
c
usuniętą operacją dzielenia zmiennoprzecinkowego ( ).źródło
Julia, 37 bajtów
Liczba próbek wynosi 65536 (= 4 ^ 8).
Odrobinę dłuższy wariant: funkcja z liczbą próbek
s
jako jedynym argumentem:źródło
C, 130 bajtów
Nie golfowany:
źródło
f()
. Z jakiego kompilatora korzystałeś? Zobacz tio.run/##Pc49C4JAHIDx3U9xGMG9ZdYgwWkgtNbQ1BZ6L/UHO8M07hA/…Właściwie 14 bajtów (niekonkurujące)
Wypróbuj online!
To rozwiązanie nie konkuruje, ponieważ język jest późniejszy niż wyzwanie. Liczba próbek jest podawana jako dane wejściowe (a nie na stałe).
Wyjaśnienie:
źródło
Rakieta 63 bajty
Przy użyciu metody odpowiedzi w języku R autorstwa @Matt:
Nie golfowany:
Testowanie:
Wyjście (ułamek):
W systemie dziesiętnym:
źródło
Fortran (GFortran) ,
8483 bajtówWypróbuj online!
Ten kod jest bardzo źle napisany. Nie powiedzie się, jeśli gfortran zdecyduje się zainicjować zmienną
A
inną wartością niż 0 (co występuje w przybliżeniu w 50% kompilacji) i, jeśliA
zostanie zainicjowany jako 0, zawsze wygeneruje tę samą losową sekwencję dla danego ziarna. Następnie zawsze drukowana jest ta sama wartość dla Pi.To jest znacznie lepszy program:
Fortran (GFortran) ,
10099 bajtówWypróbuj online!
(Jeden bajt zapisany w każdej wersji; dzięki Penguino).
źródło
Japt , 26 lub 18 bajtów
Wypróbuj online!
Analogicznie do odpowiedzi Optimizera , głównie po prostu próbując nauczyć się Japt.
Pobiera domyślną liczbę iteracji do uruchomienia
U
.Jeśli
1/(1+x^2)
jest dozwolone (zamiast dwóch oddzielnych losowych), możemy osiągnąć 18 bajtów przy użyciu tej samej logiki.źródło
Mh
obliczyć przeciwprostokątną zamiast robić to sam ;-) Możesz także użyćx
do pobrania sumy tablicy, zamiast zmniejszania przez dodanie:o x@MhMr Mr)<1Ã*4/U
Mh
tak używać , dzięki! Twoja losowa odpowiedź jest prawie tak krótka, jak moja odpowiedź z tylko jedną losową, to całkiem fajne. Będęx
pamiętać, że często staram się używać redukcji podczas gry w golfa, więc będzie to bardzo przydatne.F #, 149 bajtów
Wypróbuj online!
O ile mi wiadomo, aby wykonać tego rodzaju sumę całkowitą w F #, krótsze jest utworzenie tablicy liczb i użycie
Seq.sumBy
metody niż użyciefor..to..do
bloku.Co robi ten kod, że tworzy zbiór liczb zmiennoprzecinkowych od 1 do
s
, wykonuje funkcjęfun x->...
dla liczby elementów w kolekcji i sumuje wynik. Ws
kolekcji znajdują się elementy, więc losowy test jest wykonywanys
razy. Rzeczywiste liczby w kolekcji są ignorowane (fun x->
alex
nie są używane).Oznacza to również, że aplikacja musi najpierw utworzyć i wypełnić tablicę, a następnie wykonać iterację. Jest więc prawdopodobnie dwa razy wolniejszy niż
for..to..do
pętla. A przy tworzeniu tablicy wykorzystanie pamięci jest w obszarze O (f ** k)!Dla samego testu, zamiast używać
if then else
instrukcji, robi to, oblicza odległość (q()+q()|>Math.Sqrt
) i zaokrągla ją w dółMath.Floor
. Jeśli odległość mieści się w okręgu, zostanie zaokrąglona w dół do 0. Jeśli odległość znajduje się poza okręgiem, zostanie zaokrąglona w dół do 1.Seq.sumBy
Metoda następnie sumuje te wyniki.Zauważ, że
Seq.sumBy
sumą nie są punkty wewnątrz koła, ale punkty poza nim. Więc dla wyniku potrzebas
(nasz rozmiar próbki) i odejmuje od niego sumę.Wydaje się również, że przyjęcie wielkości próbki jako parametru jest krótsze niż zakodowanie na stałe wartości. Więc trochę oszukuję ...
źródło
Haskell,
11611411096 bajtówPonieważ zajmowanie się
import System.Random; r=randoms(mkStdGen 2)
zajęłoby zbyt wiele cennych bajtów, generuję nieskończoną listę liczb losowych za pomocą liniowego generatora kongruencjalnego, który według niektórych jest prawie kryptograficznie silny:x↦x*9+1 mod 8^9
który według twierdzenia Hulla-Dobella ma pełny okres8^9
.g
daje,4
jeśli punkt liczb losowych znajduje się wewnątrz koła dla par liczb losowych w[0..8^9-1]
ponieważ eliminuje to mnożenie w stosowanej formule.Stosowanie:
Wypróbuj online!
źródło
Perl 5, 34 bajtów
Liczba próbek jest pobierana ze standardowego wejścia. Wymaga
-p
.Działa, ponieważ:
Wypróbuj online!
źródło