Natural Pi # 0 - Rock

39

Cel

Utwórz program / funkcję, która pobiera dane wejściowe N, sprawdź, czy Nlosowe pary liczb całkowitych są względnie pierwsze, i zwraca sqrt(6 * N / #coprime).

TL; DR

Wyzwania te są symulacjami algorytmów, które wymagają jedynie natury i twojego mózgu (i być może pewnych zasobów wielokrotnego użytku) do przybliżenia Pi. Jeśli naprawdę potrzebujesz Pi podczas apokalipsy zombie, te metody nie marnują amunicji ! Przed nami jeszcze osiem wyzwań. Zapoznaj się z postem w piaskownicy, aby uzyskać rekomendacje.

Symulacja

Co symulujemy? Prawdopodobieństwo, że dwie losowe liczby całkowite są względnie pierwsze (tj. Coprime lub gcd == 1), jest 6/Pi/Piwięc naturalnym sposobem obliczenia Pi byłoby zgarnięcie dwóch wiader (lub garści) kamieni; Policz je; sprawdź, czy ich gcd wynosi 1; powtarzać. Po zrobieniu tego kilka razy, sqrt(6.0 * total / num_coprimes)będzie dążył do Pi. Jeśli obliczanie pierwiastka kwadratowego w postapokaliptycznym świecie wywołuje niepokój, nie martw się! Jest na to Metoda Newtona .

Jak to symulujemy?

  • Weź wkład N
  • Wykonaj następujące Nczasy:
    • Jednolicie generują losowe liczby całkowite dodatnie, iorazj
    • Z 1 <= i , j <= 10^6
    • Jeżeli gcd(i , j) == 1:result = 1
    • Jeszcze: result = 0
  • Weź sumę Nwyników,S
  • Powrót sqrt(6 * N / S)

wprowadź opis zdjęcia tutaj

Specyfikacja

  • Wejście
    • Elastyczny, przyjmuj dane wejściowe na dowolny ze standardowych sposobów (np. Parametr funkcji, STDIN) i w dowolnym standardowym formacie (np. Ciąg, Binarny)
  • Wydajność
    • Elastyczny, daje wydruk w dowolny ze standardowych sposobów (np. Zwrot, wydruk)
    • Dopuszczalne są białe pola, końcowe i białe znaki wiodące
    • Dokładność, proszę podać co najmniej 4 miejsca dziesiętne dokładności (tj. 3.1416)
  • Punktacja
    • Najkrótszy kod wygrywa!

Przypadki testowe

Twój wynik może się nie zgadzać z powodu losowej szansy. Ale średnio powinieneś uzyskać taką dokładność dla danej wartości N.

Input     ->  Output 
-----         ------
100       ->  3.????
10000     ->  3.1???
1000000   ->  3.14??
Nieliniowe Owoce
źródło
1
Czy nasza odpowiedź musi działać, N = 1000000czy jest w porządku, jeśli program zwróci np. Przepełnienie stosu, jeśli Njest zbyt duże?
Fatalize
@Zatwierdź, jeśli jest to ograniczenie językowe, jasne. W przeciwnym razie musisz sobie poradzić N=10^6.
NielinioweOwoce
1
Powiązane
Luis Mendo
2
Cel jest mylący, stwierdza, że ​​sprawdzana jest tylko jedna para liczb całkowitych.
user253751
1
Czy górny limit generowanych liczb losowych musi wynosić dokładnie 1000000? Czy dopuszczalny byłby większy górny limit?
Sok

Odpowiedzi:

12

APL, 23 bajty

{.5*⍨6×⍵÷1+.=∨/?⍵2⍴1e6}

Wyjaśnienie:

  • ?⍵2⍴1e6: wygeneruj macierz losowych liczb 2 na ⍵ w zakresie [1..10 6 ]
  • 1+.=∨/: pobierz GCD każdej pary i zobacz, ile jest równych 1. To oblicza S.
  • .5*⍨6×⍵÷: (6 × ⍵ ÷ S) 0,5
marinus
źródło
11

Galaretka , 20 18 16 bajtów

-2 bajty dzięki @ Pietu1998 (łańcuch i użycie zliczają 1 s, ċ1zamiast mniej niż dwóch zsumowanych <2S)

-2 bajty dzięki @Dennis (powtórz 1e6 wiele razy przed próbkowaniem, aby uniknąć łączenia)

Ḥȷ6xX€g2/ċ1÷³6÷½

(Niezwykle wolny z powodu funkcji losowej)

W jaki sposób?

Ḥȷ6xX€g2/ċ1÷³6÷½ - Main link: n
 ȷ6              - 1e6
   x             - repeat
Ḥ                -     double, 2n
    X€           - random integer in [1,1e6] for each
       2/        - pairwise reduce with
      g          -     gcd
         ċ1      - count 1s
           ÷     - divide
            ³    - first input, n
             6   - literal 6
              ÷  - divide
               ½ - square root

TryItOnline

Jonathan Allan
źródło
ḤRµȷ6Xµ€g2/ċ1÷³6÷½oszczędza 2 bajty. ( ȷ6ma 10 ^ 6 w jednym niladzie, ċ1liczy się jeden)
PurkkaKoodari
Ach, nie mogłem wymyślić, jak to połączyć w ten sposób (próbowałem kilku rzeczy) i zapomniałem sztuczki liczenia 1 - dzięki (myślę, że ȷ²jest trochę trochę szybszy niż ȷ6)
Jonathan Allan
Może być. Teraz, gdy o tym myślę, ȷ²bycie dwoma linkami nie szkodzi tutaj, ale wymagałoby dodatkowego linku lub ¤w niektórych przypadkach
PurkkaKoodari
1
Ḥȷ6xX€powinien działać dla losowego próbkowania.
Dennis
9

Python 2, 143 140 132 124 122 124 122 bajtów

Minęło sporo czasu, odkąd próbowałem grać w golfa, więc mogłem coś przegapić! Będę aktualizować w miarę skracania tego.

import random as r,fractions as f
n,s=input(),0
k=lambda:r.randrange(1e6)+1
exec's+=f.gcd(k(),k())<2;'*n
print(6.*n/s)**.5

Przetestuj mnie tutaj!

dzięki Jonathanowi Allanowi za dwubajtowe zapisanie :)

Kade
źródło
Według OP, 1 <= i , j <= 10^6więc musisz użyć randrange(1,1e6+1).
mbomb007
1
Poza tym dziwnie jest mieć link repl.it w nazwie języka. Link w nazwie języka powinien znajdować się na stronie głównej języka. Umieść swój link repl.it jako osobny link poniżej kodu.
mbomb007
@ mbomb007 Dobra uwaga, naprawiłem to :) Minęło trochę czasu!
Kade
1
k=lambda:r.randrange(1e6)+1oszczędza dwa bajty
Jonathan Allan
1
@JonathanAllan dobry połów, dzięki!
Kade,
8

Mathematica, 49 48 51 bajtów

Zapisano jeden bajt i naprawiono jeden błąd dzięki @ LegionMammal978 .

(6#/Count[GCD@@{1,1*^6}~RandomInteger~{2,#},1])^.5&
alephalpha
źródło
1
Możesz zapisać bajt:(6#/Count[GCD@@1*^6~RandomInteger~{2,#},1])^.5&
LegionMammal978 15.10.16
1
Ponadto, 1*^6powinny zostać zastąpione {1,1*^6}, aby upewnić się, że ja , j ≠ 0.
LegionMammal978
8

R, 103 99 95 99 98 94 bajtów

Prawdopodobnie można go trochę pograć w golfa. Zmniejsz 4 bajty z powodu @ antoine-sac i kolejne 4 bajty, definiując alias dla sample, używając ^.5zamiast sqrt, i 1e6zamiast 10^6. Dodano 4 bajty, aby zapewnić, że próbkowanie ii jjest naprawdę jednolite. Usunięto jeden bajt po tym, jak zorientowałem się, że 6*N/sum(x)jest taki sam jak 6/mean(x). Używany pryr::fzamiast function(x,y)do zapisania 4 bajtów.

N=scan()
s=sample
g=pryr::f(ifelse(o<-x%%y,g(y,o),y))
(6/mean(g(s(1e6,N,1),s(1e6,N,1))==1))^.5

Przykładowe dane wyjściowe:

N=100     -> 3.333333
N=10000   -> 3.137794
N=1000000 -> 3.141709
rturnbull
źródło
1
Możesz po prostu użyć sample(10^6,N). Jest nie tylko krótszy, ale także znacznie bardziej wydajny.
asac - Przywróć Monikę
Mogę się mylić, ale nie powinienem używać próbki z replace = T dla właściwie jednolitych losowych liczb całkowitych. Na przykład sample(10,10)gwarantowane jest zwrócenie wszystkich liczb w skali 1:10, podczas gdy sample(10,10,T)spowoduje losowy wybór, w którym liczby mogą się powtarzać.
MickyT,
@MickyT Masz całkowitą rację, właśnie zdałem sobie z tego sprawę kilka minut temu. Nie jestem do końca pewien, jak to wygląda matematycznie w tym przypadku - o ile wiem, obie metody są mniej więcej jednakowo dokładne. Zedytuję swój post, aby dodać te informacje.
rturnbull
Obie metody są jednakowo dokładne, gdy N << 10 ^ 6. Aby poradzić sobie z dowolnie dużym N, musisz próbkować z zamiennym, dobrym chwytem.
asac - Przywróć Monikę
7

Właściwie 19 bajtów

`6╤;Ju@Ju┤`nkΣß6*/√

Wypróbuj online!

Wyjaśnienie:

`6╤;Ju@Ju┤`nkΣß6*/√
`6╤;Ju@Ju┤`n         do this N times:
 6╤;                   two copies of 10**6
    Ju                 random integer in [0, 10**6), increment
      @Ju              another random integer in [0, 10**6), increment
         ┤             1 if coprime else 0
            kΣ       sum the results
              ß      first input again
               6*    multiply by 6
                 /   divide by sum
                  √  square root
Mego
źródło
i, j nie mogą mieć wartości 0
isaacg
1
@isaacg Nie są. Jeśli przeczytasz wyjaśnienie, jest napisane, że losowe wartości są wybierane z [0, 10 ** 6), a następnie zwiększane.
Mego
7

MATL , 22 bajty

1e6Hi3$YrZ}Zd1=Ym6w/X^

Wypróbuj online!

1e6      % Push 1e6
H        % Push 2
i        % Push input, N
3$Yr     % 2×N matrix of uniformly random integer values between 1 and 1e6
Z}       % Split into its two rows. Gives two 1×N arrays
Zd       % GCD, element-wise. Gives a 1×N array
1=       % Compare each entry with 1. Sets 1 to 0, and other values to 0
Ym       % Mean of the array
6w/      % 6 divided by that
X^       % Square root. Implicitly display
Luis Mendo
źródło
6

Pyth, 21 bajtów

@*6cQ/iMcmhO^T6yQ2lN2

Wypróbuj online.

Wyjaśnienie

                Q          input number
               y           twice that
         m                 map numbers 0 to n-1:
             T                 10
            ^ 6                to the 6th power
           O                   random number from 0 to n-1
          h                    add one
        c        2         split into pairs
      iM                   gcd of each pair
     /            lN       count ones
   cQ                      divide input number by the result
 *6                        multiply by 6
@                   2      square root
PurkkaKoodari
źródło
6

Scala, 149 126 bajtów

val& =BigInt
def f(n: Int)={math.sqrt(6f*n/Seq.fill(n){val i,j=(math.random*99999+1).toInt
if(&(i).gcd(&(j))>1)0 else 1}.sum)}

Wyjaśnienie:

val& =BigInt                //define & as an alias to the object BigInt, because it has a gcd method
def f(n:Int)={              //define a method
  math.sqrt(                //take the sqrt of...
    6f * n /                //6 * n (6f is a floating-point literal to prevent integer division)
    Seq.fill(n){            //Build a sequence with n elements, where each element is..
      val i,j=(math.random*99999+1).toInt //take 2 random integers
      if(&(i).gcd(&(j))>1)0 else 1        //put 0 or 1 in the list by calling
                                          //the apply method of & to convert the numbers to
                                          //BigInt and calling its bcd method
    }.sum                   //calculate the sum
  )
}
corvus_192
źródło
I <3 Scala! Zwłaszcza, że ​​czasami naprawdę potrzebuje wyjaśnienia.
Roman Gräf
@ RomanGräf Szczerze mówiąc, tylko rzeczy, myślę, że może być niejasne jest 6f, Seq.filli math.random.
corvus_192
5

Rakieta 92 bajty

(λ(N)(sqrt(/(* 6 N)(for/sum((c N))(if(= 1(gcd(random 1 1000000)(random 1 1000000)))1 0)))))

Nie golfowany:

(define f
  (λ (N)
    (sqrt(/ (* 6 N) 
            (for/sum ((c N))
              (if (= 1
                     (gcd (random 1 1000000)
                          (random 1 1000000)))
                  1 0)
              )))))

Testowanie:

(f 100)
(f 1000)
(f 100000)

Wynik:

2.970442628930023
3.188964020716403
3.144483068444827
rnso
źródło
5

JavaScript (ES7), 107 95 94 bajtów

n=>(n*6/(r=_=>Math.random()*1e6+1|0,g=(a,b)=>b?g(b,a%b):a<2,q=n=>n&&g(r(),r())+q(n-1))(n))**.5

Wersja ES6 ma dokładnie 99 bajtów, ale operator potęgowania ES7 **oszczędza 5 bajtów Math.sqrt.

Bez golfa

function pi(n) {
  function random() {
    return Math.floor(Math.random() * 1e6) + 1;
  }
  function gcd(a, b) {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
  function q(n) {
    if (n == 0)
      return 0;
    return (gcd(random(), random()) == 1 ? 1 : 0) + q(n - 1));
  }
  return Math.sqrt(n * 6 / q(n));
}
ETHprodukcje
źródło
W wersji Ungolfed gcdwywołuje funkcjęg
Roman Gräf
r=_=>czy to kod czy rysunek?
aross
n=>(n*6/(r=_=>Math.random()*1e6,g=(a,b)=>b?g(b,a%b):a>-2,q=n=>n&&g(~r(),~r())+q(n-1))(n))**.51B krótszy
l4m2
n=>(n*6/(q=_=>n--&&q(r=_=>Math.random()*1e6)+g(~r(),~r()))(g=(a,b)=>b?g(b,a%b):a>-2))**.5
l4m2
5

PHP, 82 77 74 bajty

for(;$i++<$argn;)$s+=2>gmp_gcd(rand(1,1e6),rand(1,1e6));echo(6*$i/$s)**.5;

Uruchom tak:

echo 10000 | php -R 'for(;$i++<$argn;)$s+=2>gmp_gcd(rand(1,1e6),rand(1,1e6));echo(6*$i/$s)**.5;' 2>/dev/null;echo

Wyjaśnienie

Robi to, co jest napisane na puszce. Wymaga PHP_GMP dla gcd.

Poprawki

  • Zaoszczędzono 3 bajty $argn
aross
źródło
4

Perl, 64 bajty

sub r{1+~~rand 9x6}$_=sqrt$_*6/grep{2>gcd r,r}1..$_

Wymaga opcji wiersza poleceń -pMntheory=gcd , liczonej jako 13. Dane wejściowe są pobierane ze standardowego wejścia.

Przykładowe użycie

$ echo 1000 | perl -pMntheory=gcd pi-rock.pl
3.14140431218772
primo
źródło
4

R, 94 bajty

N=scan();a=replicate(N,{x=sample(1e6,2);q=1:x[1];max(q[!x[1]%%q&!x[2]%%q])<2});(6*N/sum(a))^.5

Stosunkowo wolny, ale nadal działa. Replikuj N razy funkcję, która pobiera 2 liczby losowe (od 1 do 1e6) i sprawdza, czy ich gcd jest mniejsza niż 2 (przy użyciu mojej starej funkcji gcd ).

plannapus
źródło
1
Jeśli nie martwisz się ostrzeżeniami, 1:xzadziała.
MickyT,
4

PowerShell v2 +, 118 114 bajtów

param($n)for(;$k-le$n;$k++){$i,$j=0,1|%{Random -mi 1};while($j){$i,$j=$j,($i%$j)}$o+=!($i-1)}[math]::Sqrt(6*$n/$o)

Pobiera dane wejściowe $n, uruchamia forpętlę, aż będzie $krówna $n(domyślna $k=0przy pierwszym wejściu do pętli). Każda iteracja, otrzymuj nowe Randomliczby $ii $j( flaga -minimum 1gwarantuje, że jesteśmy >=1i żadna maksymalna flaga nie pozwala na [int]::MaxValue, co jest dozwolone przez PO, ponieważ jest większe niż 10e6).

Następnie wchodzimy w pętlę GCDwhile . Następnie, tak długo jak GCD jest 1, $ozwiększa się. Na końcu forpętli wykonujemy proste [math]::Sqrt()wywołanie, które zostaje w potoku, a dane wyjściowe są niejawne.

Uruchomienie z wejściem 10000na moim ~ 1-letnim laptopie Core i5 zajmuje około 15 minut .

Przykłady

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 100
3.11085508419128

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 1000
3.17820863081864

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 10000
3.16756133579975
AdmBorkBork
źródło
3

Java 8, 164 151 bajtów

n->{int c=n,t=0,x,y;while(c-->0){x=1+(int)(Math.random()*10e6);y=1+(int)(Math.random()*10e6);while(y>0)y=x%(x=y);if(x<2)t++;}return Math.sqrt(6f*n/t);}

Wyjaśnienie

n->{
    int c=n,t=0,x,y;
    while(c-->0){                          // Repeat n times
        x=1+(int)(Math.random()*10e6);     // Random x
        y=1+(int)(Math.random()*10e6);     // Random y
        while(y>0)y=x%(x=y);               // GCD
        if(x<2)t++;                        // Coprime?
    }
    return Math.sqrt(6f*n/t);              // Pi
}

Uprząż testowa

class Main {
    public static interface F{ double f(int n); }
    public static void g(F s){
        System.out.println(s.f(100));
        System.out.println(s.f(1000));
        System.out.println(s.f(10000));
    }
    public static void main(String[] args) {
        g(
            n->{int c=n,t=0,y,x;while(c-->0){x=1+(int)(Math.random()*10e6);y=1+(int)(Math.random()*10e6);while(y>0)y=x%(x=y);if(x<2)t++;}return Math.sqrt(6f*n/t);}
        );
    }
}

Aktualizacja

  • -13 [16-10-05] Dzięki @TNT i dodanej uprzęży testowej
Nieliniowe Owoce
źródło
1
Nie trzeba nawiasy wokół pierwszego n, t+=1może stać t++, można skondensować intdeklaracji w jednej linii, to znaczy int c=n,t=0,x,y;, i !=0(chyba) może stać >0. To powinno zaoszczędzić 12 bajtów ogółem. Jest to jednak fajny sposób na znalezienie GCD xiy.
TNT
1

Frink, 84 89

r[]:=random[10^6]+1
g=n=eval[input[1]]
for a=1to n
g=g-1%gcd[r[],r[]]
println[(6*n/g)^.5]

Mam szczęście: g = n = ... zapisuje bajt nad g = 0 n = ... ; a 1% gcd () daje (0,1) vs (1,0), więc mogę odjąć. I pecha: n jest wstępnie przypisane i stosowane, ponieważ zmienne pętlowe i ich granice są lokalne i niezdefiniowana poza pętlą.

Gadatliwy

r[] := random[10^6] + 1     // function. Frink parses Unicode superscript!
g = n = eval[input[""]]     // input number, [1] works too
for a = 1 to n              // repeat n times
   g = g - 1%gcd[r[], r[]]  // subtract 1 if gcd(i, j) > 1
println[(6*n/g)^.5]         // ^.5 is shorter than sqrt[x], but no super ".", no ½
Może tak
źródło
To 90 bajtów i 88 znaków ...?
CalculatorFeline
Dzięki za złapanie tego. Nie liczyłem nowych linii i chociaż ², ³ mają tylko 1 bajt ⁶ to więcej. Naprawiłem to do 89 bajtów bez końcowej nowej linii.
maybeso
Nie poprawiono pełnego kodu.
CalculatorFeline
To i tak nie jest pojedynek jeden na jeden z odstępami, cytatami i liczbami itp.
maybeso
1

AWK , 109 bajtów

func G(p,q){return(q?G(q,p%q):p)}{for(;i++<$0;)x+=G(int(1e6*rand()+1),int(1e6*rand()+1))==1;$0=sqrt(6*$0/x)}1

Wypróbuj online!

Dziwi mnie, że działa w rozsądnym czasie na 1000000.

Robert Benson
źródło
1

Pyt , 37 35 bajtów

←Đ0⇹`25*⁶⁺Đ1⇹ɾ⇹1⇹ɾǤ1=⇹3Ș+⇹⁻łŕ⇹6*⇹/√

Wyjaśnienie:

←Đ                                              Push input onto stack twice
  0                                             Push 0
   ⇹                                            Swap top two elements of stack
    `                      ł                    Repeat until top of stack is 0
     25*⁶⁺Đ1⇹ɾ⇹1⇹ɾ                              Randomly generate two integers in the range [1,10^6]
                  Ǥ1=                           Is their GCD 1?
                     ⇹3Ș                        Reposition top three elements of stack
                        +                       Add the top 2 on the stack
                         ⇹⁻                     Swap the top two and subtract one from the new top of the stack
                            ŕ                   Remove the counter from the stack
                             ⇹                  Swap the top two on the stack
                              6*                Multiply top by 6
                                ⇹               Swap top two
                                 /              Divide the second on the stack by the first
                                  √             Get the square root
mudkip201
źródło
1

J, 27 bajtów

3 :'%:6*y%+/(1:=?+.?)y#1e6'

Wyjaśnienie:

3 :'                      '  | Explicit verb definition
                     y#1e6   | List of y copies of 1e6 = 1000000
            (1:=?+.?)        | for each item, generate i and j, and test whether their gcd is 1
          +/                 | Sum the resulting list
      6*y%                   | Divide y by it and multiply by six
    %:                       | Square root

Dostaliśmy bardzo szczęśliwy z 3.14157za N = 10000000, które odbyło 2.44sekund.

Bolce Bussiere
źródło
1

Japt , 23 bajty

*6/UÆ1+1e6ö)j1+1e6öÃx)¬

Spróbuj

Kudłaty
źródło