Natural Pi # 0 - Rock

39

Objectif

Créez un programme / une fonction qui prend une entrée N, vérifiez si Nles paires aléatoires d’entiers sont relativement premiers et retourne sqrt(6 * N / #coprime).

TL; DR

Ces défis sont des simulations d’algorithmes qui ne nécessitent que la nature et votre cerveau (et peut-être quelques ressources réutilisables) pour approcher Pi. Si vous avez vraiment besoin de Pi lors de l'apocalypse des zombies, ces méthodes ne gaspillent pas les munitions ! Huit autres défis sont à venir. Consultez le message du bac à sable pour faire des recommandations.

Simulation

Que simulons-nous? Eh bien, la probabilité que deux entiers aléatoires soient relativement premiers (c.-à-d. Coprime ou gcd == 1) est 6/Pi/Pi, donc un moyen naturel de calculer Pi serait d'extraire deux seaux (ou poignées) de roches; compte les; voir si leur gcd est 1; répéter. Après avoir fait cela plusieurs fois, vous sqrt(6.0 * total / num_coprimes)aurez tendance à Pi. Si calculer la racine carrée dans un monde post-apocalyptique vous rend nerveux, ne vous inquiétez pas! Il y a la méthode de Newton pour cela.

Comment simulons-nous cela?

  • Prendre une entrée N
  • Faites les Ntemps suivants :
    • Générer uniformément des entiers positifs aléatoires, ietj
    • Avec 1 <= i , j <= 10^6
    • Si gcd(i , j) == 1:result = 1
    • Autre: result = 0
  • Prenez la somme des Nrésultats,S
  • Revenir sqrt(6 * N / S)

enter image description here

spécification

  • Contribution
    • Flexible, prenez les entrées de n'importe quelle manière standard (par exemple, paramètre de fonction, STDIN) et dans n'importe quel format standard (par exemple, chaîne, binaire)
  • Sortie
    • Flexible, donnez la sortie de n'importe quelle manière standard (retour, impression, etc.)
    • Les espaces blancs, les espaces de fuite et les espaces de début sont acceptables
    • Précision, veuillez fournir au moins 4 décimales de précision (c.-à-d. 3.1416)
  • Notation
    • Le code le plus court gagne!

Cas de test

Votre sortie peut ne pas s'aligner sur celles-ci, à cause du hasard. Mais en moyenne, vous devriez obtenir autant de précision pour la valeur donnée de N.

Input     ->  Output 
-----         ------
100       ->  3.????
10000     ->  3.1???
1000000   ->  3.14??
Fruit non linéaire
la source
1
Notre réponse doit-elle fonctionner N = 1000000ou est-il acceptable si le programme renvoie par exemple un débordement de pile s'il Nest trop volumineux?
Fataliser
@ Fatalize si c'est une limitation de la langue, bien sûr. Sinon, vous devez gérer N=10^6.
NonlinearFruit
1
Connexes
Luis Mendo
2
L'objectif est trompeur, il est indiqué qu'une seule paire d'entiers est vérifiée.
user253751
1
La limite supérieure des nombres aléatoires générés doit-elle être exactement 1000000? Une limite supérieure plus grande serait-elle acceptable?
Sok

Réponses:

12

APL, 23 octets

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

Explication:

  • ?⍵2⍴1e6: générer une matrice 2-sur-⍵ de nombres aléatoires dans l'intervalle [1..10 6 ]
  • 1+.=∨/: obtenez le GCD de chaque paire et voyez combien sont égaux à 1. Ceci calcule S.
  • .5*⍨6×⍵÷: (6 × ÷ S) 0,5
marinus
la source
11

Jelly , 20 18 16 octets

-2 octets grâce à @ Pietu1998 (chain & use count 1s, ċ1au lieu de moins de deux cumed <2S)

-2 octets grâce à @Dennis (répétez 1e6 fois avant l'échantillonnage pour éviter l'enchaînement)

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

(Extrêmement lent en raison de la fonction aléatoire)

Comment?

Ḥȷ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
la source
ḤRµȷ6Xµ€g2/ċ1÷³6÷½enregistre 2 octets. ( ȷ6est 10 ^ 6 dans un seul nilad, ċ1compte les uns)
PurkkaKoodari
Ah, je ne savais pas comment enchaîner ça (j'ai essayé quelques trucs), et j'ai oublié le tour 1 - merci (je pense que ȷ²c'est un tout petit peu plus rapide que ȷ6)
Jonathan Allan
Pourrait être. Maintenant que j'y pense, ȷ²être deux liens ne fait pas mal ici, mais nécessite un lien supplémentaire ou ¤pour certains cas d'utilisation
PurkkaKoodari
1
Ḥȷ6xX€devrait fonctionner pour l'échantillonnage aléatoire.
Dennis
9

Python 2, 143 140 132 124 122 124 122 octets

Cela fait longtemps que je n’ai pas essayé le golf, j’ai peut-être manqué quelque chose ici! Sera mise à jour que je raccourcis cela.

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

Testez moi ici!

merci à Jonathan Allan pour la sauvegarde de deux octets :)

Kade
la source
Selon OP, 1 <= i , j <= 10^6vous devez donc utiliser randrange(1,1e6+1).
mbomb007
1
En outre, il est vraiment étrange d’avoir le lien repl.it dans le nom de la langue. Un lien dans le nom de langue devrait être vers la page d'accueil de la langue, le cas échéant. Placez votre lien repl.it en tant que lien séparé sous votre code.
mbomb007
@ mbomb007 Bon point, je l'ai déjà réparé :) Ça fait longtemps!
Kade
1
k=lambda:r.randrange(1e6)+1économise deux octets
Jonathan Allan
1
@ JonathanAllan bonne prise, merci!
Kade
8

Mathematica, 49 48 51 octets

Sauvegardé d'un octet et correction d'un bug grâce à @ LegionMammal978 .

(6#/Count[GCD@@{1,1*^6}~RandomInteger~{2,#},1])^.5&
Alephalpha
la source
1
Vous pouvez enregistrer un octet:(6#/Count[GCD@@1*^6~RandomInteger~{2,#},1])^.5&
LegionMammal978
1
Aussi, 1*^6devrait être remplacé par {1,1*^6}pour s'assurer que je , j 0.
LegionMammal978
8

R, 103 99 95 99 98 94 octets

Peut probablement être joué au golf un peu. Réduisez 4 octets à cause de @ antoine-sac et 4 autres octets en définissant un alias pour sample, à la ^.5place de sqrtet à la 1e6place de 10^6. Ajout de 4 octets pour s'assurer que l'échantillonnage de iet jest vraiment uniforme. Suppression d’un octet après avoir réalisé que 6*N/sum(x)c’était la même chose que 6/mean(x). Utilisé pryr::fau lieu de function(x,y)sauvegarder 4 octets.

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

Exemple de sortie:

N=100     -> 3.333333
N=10000   -> 3.137794
N=1000000 -> 3.141709
tourbull
la source
1
Vous pouvez simplement utiliser sample(10^6,N). Non seulement c'est plus court, mais c'est aussi beaucoup plus efficace.
asac - Réintégrer Monica
Je peux me tromper, mais ne devrions-nous pas utiliser l'échantillon avec replace = T pour obtenir des nombres entiers aléatoires bien uniformes. Par exemple, il sample(10,10)est garanti de renvoyer tous les nombres en 1:10, alors que sample(10,10,T)produira une sélection aléatoire où les nombres peuvent être répétés.
MickyT
@MickyT Vous avez absolument raison, je viens de m'en rendre compte moi-même il y a quelques minutes. Je ne suis pas tout à fait sûr de savoir comment cela se passe mathématiquement dans cet exemple - pour autant que je sache, les deux méthodes sont à peu près aussi précises. Je vais éditer mon post pour ajouter cette information.
rturnbull
Les deux méthodes sont également précises lorsque N << 10 ^ 6. Pour traiter arbitrairement de gros N, vous devez échantillonner avec remplacement, bonne capture.
asac - Réintégrez Monica
7

En fait, 19 octets

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

Essayez-le en ligne!

Explication:

`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
la source
je ne suis pas autorisé à être 0
isaacg
1
@isaacg Ils ne le sont pas. Si vous lisez l'explication, elle indique que les valeurs aléatoires sont sélectionnées parmi [0, 10 ** 6), puis incrémentées.
Mego
7

MATL , 22 octets

1e6Hi3$YrZ}Zd1=Ym6w/X^

Essayez-le en ligne!

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
la source
6

Pyth, 21 octets

@*6cQ/iMcmhO^T6yQ2lN2

Essayez-le en ligne.

Explication

                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
la source
6

Scala, 149 126 octets

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

Explication:

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
la source
Je <3 Scala! Surtout, parce que parfois, il faut vraiment une explication.
Roman Gräf
@ RomanGräf Pour être honnête, les seules choses que je pense ne pas être claires sont 6f, Seq.fillet math.random.
corvus_192
5

Raquette 92 octets

(λ(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)
              )))))

Essai:

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

Sortie:

2.970442628930023
3.188964020716403
3.144483068444827
rnso
la source
5

JavaScript (ES7), 107 95 94 octets

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

La version ES6 est exactement de 99 octets, mais l'opérateur d'exponentiation ES7 **enregistre 5 octets 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
la source
Dans la version non-gérée gcdappelle la fonctiong
Roman Gräf
r=_=>est ce code ou un dessin?
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 plus court
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 octets

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

Courez comme ça:

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

Explication

Fait ce qu'il dit sur l'étain. Requiert PHP_GMP pour gcd.

Tweaks

  • 3 octets enregistrés en utilisant $argn
aross
la source
4

Perl, 64 octets

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

Nécessite l'option de ligne de commande -pMntheory=gcd, comptabilisée comme 13. L'entrée est prise à partir de stdin.

Exemple d'utilisation

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

R, 94 octets

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

Relativement lent mais fonctionne toujours. Répliquer N fois une fonction qui prend 2 nombres aléatoires (de 1 à 1e6) et vérifie si leur gcd est inférieur à 2 (en utilisant une ancienne fonction de gcd ).

planificateur
la source
1
Si vous n'êtes pas inquiet pour les avertissements, 1:xcela fonctionnera.
MickyT
4

PowerShell v2 +, 118 114 octets

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)

Prend entrée $n, commence une forboucle jusqu'à être $kégal à $n(implicite $k=0lors de la première entrée dans la boucle). À chaque itération, obtenez de nouveaux Randomnuméros $iet $j(l' indicateur -minimum 1garantit que nous sommes >=1et qu'aucun indicateur maximal ne permet jusqu'à[int]::MaxValue , ce qui est autorisé par l'OP puisqu'il est supérieur à 10e6).

Nous passons ensuite dans une boucle GCDwhile . Alors, tant que le GCD est 1, $oest incrémenté. À la fin defor boucle, nous effectuons un [math]::Sqrt()appel simple , qui reste sur le pipeline et la sortie est implicite.

Prend environ 15 minutes pour fonctionner avec l'entrée 10000 sur mon ordinateur portable Core i5 âgé d'environ 1 an.

Exemples

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
la source
3

Java 8, 164 151 octets

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

Explication

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
}

Harnais de test

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

Mise à jour

  • -13 [16-10-05] Merci à @TNT et au harnais de test ajouté
Fruit non linéaire
la source
1
Vous n’avez pas besoin de parenthèses entre les premières n, vous t+=1pouvez devenir t++, vous pouvez condenser vos intdéclarations sur une seule ligne, c’est int c=n,t=0,x,y;-à- dire , et !=0(je pense) pouvoir le devenir >0. Cela devrait économiser 12 octets au total. C’est pourtant une excellente façon de trouver le DPC de x et y.
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]

J'ai eu de la chance: g = n = ... enregistre un octet sur g = 0 n = ... ; et 1% gcd () donne (0,1) vs (1,0) pour que je puisse soustraire. Et malchanceux: n est prédéfini et un utilisé parce que les variables de boucle et leurs limites sont en dehors de la boucle locale et non défini.

Verbeux

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 ½
Peut-être
la source
C'est 90 octets et 88 caractères ...?
CalculatorFeline
Merci d'avoir attrapé ça. Je n'ai pas compté les nouvelles lignes et, bien que ², ³ ne représente qu'un octet, c'est plus. Je l'ai fixé à 89 octets sans nouvelle ligne finale.
Maybeso
Vous n'avez pas corrigé le code détaillé.
CalculatriceFeline
Ce n'est pas un match un contre un de toute façon avec l'espacement, les guillemets et les chiffres, etc.
maybeso
1

AWK , 109 octets

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

Essayez-le en ligne!

Je suis surpris que cela fonctionne dans un laps de temps raisonnable pour 1000000.

Robert Benson
la source
1

Pyt , 37 35 octets

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

Explication:

←Đ                                              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
la source
1

J, 27 octets

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

Explication:

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

J'ai eu beaucoup de chance avec 3.14157pour N = 10000000, ce qui a pris 2.44quelques secondes.

Bolce Bussiere
la source
1

Japt , 23 octets

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

L'essayer

Hirsute
la source