Natürlicher Pi # 0 - Rock

39

Tor

Erstellen Sie ein Programm / eine Funktion, die eine Eingabe akzeptiert N, prüfen Sie, ob Nzufällige Paare von Ganzzahlen relativ prim sind, und geben Sie zurück sqrt(6 * N / #coprime).

TL; DR

Diese Herausforderungen sind Simulationen von Algorithmen, für die nur die Natur und Ihr Gehirn (und möglicherweise einige wiederverwendbare Ressourcen) erforderlich sind, um sich dem Pi anzunähern. Wenn Sie Pi während der Zombie-Apokalypse wirklich brauchen, verschwenden diese Methoden keine Munition ! Es gibt noch acht weitere Herausforderungen. Überprüfen Sie den Sandbox-Post , um Empfehlungen abzugeben .

Simulation

Was simulieren wir? Nun, die Wahrscheinlichkeit, dass zwei zufällige ganze Zahlen relativ prim (dh coprime oder gcd == 1) sind 6/Pi/Pi, ist so, dass ein natürlicher Weg, um Pi zu berechnen, darin besteht, zwei Eimer (oder eine Handvoll) Steine ​​zu schöpfen; zähle sie; sehen, ob ihr gcd 1 ist; wiederholen. Nachdem Sie dies einige Male getan haben, sqrt(6.0 * total / num_coprimes)tendieren Sie dazu Pi. Wenn die Berechnung der Quadratwurzel in der postapokalyptischen Welt Sie nervös macht, machen Sie sich keine Sorgen! Dafür gibt es Newtons Methode .

Wie simulieren wir das?

  • Eingaben übernehmen N
  • Mach die folgenden NZeiten:
    • Einheitlich zufällige positive ganze Zahlen erzeugen, iundj
    • Mit 1 <= i , j <= 10^6
    • Wenn gcd(i , j) == 1:result = 1
    • Sonst: result = 0
  • Nehmen Sie die Summe der NErgebnisse,S
  • Rückkehr sqrt(6 * N / S)

Bildbeschreibung hier eingeben

Spezifikation

  • Eingang
    • Flexibel, Eingaben auf eine der Standardarten (zB Funktionsparameter, STDIN) und in einem beliebigen Standardformat (zB String, Binary)
  • Ausgabe
    • Flexibel, Ausgabe auf eine der Standardarten (z. B. Rückgabe, Druck)
    • Leerzeichen, nachfolgende und führende Leerzeichen sind zulässig
    • Genauigkeit, geben Sie bitte mindestens 4 Dezimalstellen Genauigkeit (dh 3.1416)
  • Wertung
    • Kürzester Code gewinnt!

Testfälle

Ihre Ausgabe stimmt möglicherweise nicht mit diesen überein, weil zufällige Zufälle vorliegen. Aber im Durchschnitt sollte man für den gegebenen Wert von ungefähr so ​​viel Genauigkeit bekommen N.

Input     ->  Output 
-----         ------
100       ->  3.????
10000     ->  3.1???
1000000   ->  3.14??
NichtlinearFruit
quelle
1
Muss unsere Antwort funktionieren N = 1000000oder ist es in Ordnung, wenn das Programm z. B. einen Stapelüberlauf zurückgibt, wenn er Nzu groß ist?
Fatalize
@Fatalize, wenn es eine Einschränkung der Sprache ist, sicher. Ansonsten musst du damit umgehen N=10^6.
NonlinearFruit
1
Related
Luis Mendo
2
Das Ziel ist irreführend, es besagt, dass nur ein ganzzahliges Paar überprüft wird.
user253751
1
Muss die Obergrenze für die generierten Zufallszahlen genau 1000000 betragen? Wäre eine größere Obergrenze akzeptabel?
Sok

Antworten:

12

APL, 23 Bytes

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

Erläuterung:

  • ?⍵2⍴1e6: Erzeuge eine 2-mal-⍵-Matrix von Zufallszahlen im Bereich [1..10 6 ]
  • 1+.=∨/: Ermitteln Sie die GCD jedes Paares und sehen Sie, wie viele gleich 1 sind. Dies berechnet S.
  • .5*⍨6×⍵÷: (6 × ≤ S) 0,5
Marinus
quelle
11

Jelly , 20 18 16 Bytes

-2 Bytes dank @ Pietu1998 (chain & use count 1s, ċ1anstelle von weniger als zwei summierten <2S)

-2 Bytes dank @Dennis (1e6 vor dem Sampling mehrmals wiederholen, um Verkettung zu vermeiden)

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

(Extrem langsam aufgrund der Zufallsfunktion)

Wie?

Ḥȷ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
quelle
ḤRµȷ6Xµ€g2/ċ1÷³6÷½Spart 2 Bytes. ( ȷ6ist 10 ^ 6 in einem einzigen Nilad, ċ1zählt diejenigen)
PurkkaKoodari
Ah, ich konnte nicht herausfinden, wie ich es so verketten kann (ich habe ein paar Dinge ausprobiert) und habe den Trick mit der Zählung 1 vergessen - danke (ich denke, er ȷ²ist ein winziges bisschen schneller als ȷ6)
Jonathan Allan,
Könnte sein. Nun, da ich darüber nachdenke, ȷ²tut es hier nicht weh, zwei Links zu haben, sondern würde einen zusätzlichen Link oder ¤für einige Anwendungsfälle erfordern
PurkkaKoodari,
1
Ḥȷ6xX€sollte für die Stichprobe arbeiten.
Dennis
9

Python 2, 143 140 132 124 122 124 122 Bytes

Es ist schon eine Weile her, dass ich Golf gespielt habe, also habe ich hier vielleicht etwas verpasst! Wird aktualisiert, wenn ich dies verkürze.

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

Teste mich hier!

danke an Jonathan Allan für die Zwei-Byte-Speicherung :)

Kade
quelle
Laut OP müssen 1 <= i , j <= 10^6Sie also verwenden randrange(1,1e6+1).
mbomb007
1
Es ist auch sehr merkwürdig, dass der Link repl.it im Namen der Sprache enthalten ist. Ein Link in der Sprache sollte, wenn überhaupt, zur Homepage der Sprache führen. Fügen Sie Ihren repl.it-Link als separaten Link unter Ihren Code ein.
mbomb007
@ mbomb007 Guter Punkt, ich habe es behoben :) Schon eine Weile!
Kade
1
k=lambda:r.randrange(1e6)+1spart zwei Bytes
Jonathan Allan
1
@ JonathanAllan guten Fang, danke!
Kade
8

Mathematica, 49 48 51 Bytes

Ein Byte gespeichert und ein Fehler behoben dank @ LegionMammal978 .

(6#/Count[GCD@@{1,1*^6}~RandomInteger~{2,#},1])^.5&
Alephalpha
quelle
1
Sie können ein Byte speichern:(6#/Count[GCD@@1*^6~RandomInteger~{2,#},1])^.5&
LegionMammal978
1
Auch 1*^6sollte mit ersetzt werden, {1,1*^6}um sicherzustellen, dass i , j ≠ 0.
LegionMammal978
8

R 103 99 95 99 98 94 Bytes

Kann wahrscheinlich ein bisschen runtergolfen werden. Reduzieren Sie 4 Bytes aufgrund von @ antoine-sac und weitere 4 Bytes, indem Sie einen Alias ​​für sample, using ^.5anstelle von sqrtund 1e6anstelle von definieren 10^6. Es wurden 4 Bytes hinzugefügt, um sicherzustellen, dass die Abtastung von iund jwirklich einheitlich ist. Ein Byte wurde entfernt, nachdem mir klar wurde, dass 6*N/sum(x)es dasselbe ist wie 6/mean(x). Wird pryr::fverwendet function(x,y), um 4 Bytes zu speichern.

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

Beispielausgabe:

N=100     -> 3.333333
N=10000   -> 3.137794
N=1000000 -> 3.141709
rturnbull
quelle
1
Sie können einfach verwenden sample(10^6,N). Es ist nicht nur kürzer, sondern auch effizienter.
asac - Wiedereinsetzung von Monica
Ich kann mich irren, aber sollte die Stichprobe nicht mit replace = T für richtig gleichmäßige Zufallszahlen verwendet werden. Beispielsweise sample(10,10)werden garantiert alle Zahlen in 1:10 zurückgegeben, während sample(10,10,T)eine zufällige Auswahl erstellt wird, bei der Zahlen wiederholt werden können.
MickyT
@MickyT Du hast absolut recht, ich habe das erst vor ein paar Minuten selbst gemerkt. Ich bin mir nicht ganz sicher, wie dies in diesem Fall mathematisch aussieht - soweit ich das beurteilen kann, sind beide Methoden ungefähr gleich genau. Ich bearbeite meinen Beitrag, um diese Informationen hinzuzufügen.
Rturnbull
Beide Methoden sind gleich genau, wenn N << 10 ^ 6. Um mit beliebig großen N umzugehen, muss man mit Ersatz einen guten Fang probieren.
asac
7

Eigentlich 19 Bytes

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

Probieren Sie es online!

Erläuterung:

`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
quelle
i, j darf nicht 0 sein
isaacg
1
@isaacg Sie sind nicht. Wenn Sie die Erklärung lesen, heißt es, dass die Zufallswerte aus [0, 10 ** 6) ausgewählt und dann inkrementiert werden.
Mego
7

MATL , 22 Bytes

1e6Hi3$YrZ}Zd1=Ym6w/X^

Probieren Sie es 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
quelle
6

Pyth, 21 Bytes

@*6cQ/iMcmhO^T6yQ2lN2

Probieren Sie es online aus.

Erläuterung

                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
quelle
6

Scala, 149 126 Bytes

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

Erläuterung:

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
quelle
I <3 Scala! Vor allem, weil es manchmal wirklich eine Erklärung braucht.
Roman Gräf
@ RomanGräf Um ehrlich zu sein, könnte sein , die einzigen Dinge , die ich denke , unklar sind 6f, Seq.fillund math.random.
corvus_192
5

Schläger 92 Bytes

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

Ungolfed:

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

Testen:

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

Ausgabe:

2.970442628930023
3.188964020716403
3.144483068444827
rnso
quelle
5

JavaScript (ES7), 107 95 94 Byte

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

Die ES6-Version hat genau 99 Byte, aber der ES7-Exponentiationsoperator **spart 5 Byte mehr Math.sqrt.

Ungolfed

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));
}
ETHproductions
quelle
In der Ungolfed-Fassung gcdnennt sich die Funktiong
Roman Gräf
r=_=>ist das ein Code oder eine Zeichnung?
Am
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 kürzer
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
14.
5

PHP, 82 77 74 Bytes

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

Laufen Sie wie folgt:

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

Erläuterung

Tut was es verspricht. Benötigt PHP_GMP für gcd.

Optimierungen

  • 3 Bytes mit gespeichert $argn
aross
quelle
4

Perl, 64 Bytes

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

Erfordert die Befehlszeilenoption -pMntheory=gcd, die als 13 gezählt wird. Die Eingabe erfolgt über stdin.

Beispielnutzung

$ echo 1000 | perl -pMntheory=gcd pi-rock.pl
3.14140431218772
primo
quelle
4

R, 94 Bytes

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

Relativ langsam, funktioniert aber immer noch. Repliziere N-mal eine Funktion, die 2 Zufallszahlen (von 1 bis 1e6) akzeptiert und prüfe, ob ihr gcd kleiner als 2 ist (unter Verwendung einer alten gcd-Funktion von mir ).

Plannapus
quelle
1
Wenn Sie nicht über Warnungen besorgt sind, 1:xwird funktionieren.
MickyT
4

PowerShell v2 +, 118 bis 114 Byte

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)

Übernimmt die Eingabe $n, startet eine forSchleife, bis sie $kgleich ist $n(impliziert $k=0beim ersten Betreten der Schleife). Bei jeder Iteration erhalten Sie neue RandomZahlen $iund $j(das -miNimum- 1Flag stellt sicher, dass wir >=1und kein Maximum-Flag bis zu [int]::MaxValuezulassen sind, was vom OP zulässig ist, da es größer als ist 10e6).

Wir gehen dann in eine GCD- whileSchleife . Dann wird, solange der GCD ist 1, $oinkrementiert. Am Ende der forSchleife führen wir einen einfachen [math]::Sqrt()Aufruf durch, der in der Pipeline verbleibt und dessen Ausgabe implizit ist.

Die Ausführung mit Eingaben 10000auf meinem ~ 1 Jahr alten Core i5-Laptop dauert ungefähr 15 Minuten .

Beispiele

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
quelle
3

Java 8, 164 151 Bytes

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

Erläuterung

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
}

Testgeschirr

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

Aktualisieren

  • -13 [16-10-05] Danke an @TNT und hinzugefügtes Testgeschirr
NichtlinearFruit
quelle
1
Sie brauchen keine Klammern um die erste n, t+=1können werden t++, Sie können Ihre intDeklarationen in einer Zeile zusammenfassen, dh int c=n,t=0,x,y;und !=0(ich denke) können werden >0. Das sollte insgesamt 12 Bytes einsparen. Dies ist jedoch eine gute Methode, um die GCD von x und y zu ermitteln.
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]

Ich hatte Glück: g = n = ... speichert ein Byte über g = 0 n = ... ; und 1% gcd () ergibt (0,1) vs (1,0), so dass ich subtrahieren kann. Und Pech: n ist vorbelegt und ein verwendet , da Schleifenvariablen und ihre Grenzen sind lokal und außerhalb der Schleife nicht definiert.

Ausführlich

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 ½
vielleicht so
quelle
Das sind 90 Bytes und 88 Zeichen ...?
CalculatorFeline
Danke, dass du das verstanden hast. Ich habe keine Zeilenumbrüche gezählt und während ², ³ nur 1 Byte sind, ist ⁶ mehr. Ich habe es auf 89 Bytes ohne letzte Zeile korrigiert.
Maybeso
Sie haben den ausführlichen Code nicht korrigiert.
CalculatorFeline
Es ist sowieso kein Eins-zu-Eins-Match mit Abständen, Anführungszeichen und Zahlen usw.
Maybeso
1

AWK , 109 Bytes

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

Probieren Sie es online!

Ich bin überrascht, dass es für 1000000 in angemessener Zeit läuft.

Robert Benson
quelle
1

Pyt , 37 35 Bytes

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

Erläuterung:

←Đ                                              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
quelle
1

J, 27 Bytes

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

Erläuterung:

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

Ich hatte ziemlich viel Glück mit einem 3.14157für N = 10000000, was 2.44Sekunden dauerte .

Bolce Bussiere
quelle
1

Japt , 23 Bytes

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

Versuch es

Zottelig
quelle