Pi Natural # 0 - Rocha

39

Objetivo

Crie um programa / função que receba uma entrada N, verifique se Npares aleatórios de números inteiros são relativamente primos e retorne sqrt(6 * N / #coprime).

TL; DR

Esses desafios são simulações de algoritmos que exigem apenas a natureza e seu cérebro (e talvez alguns recursos reutilizáveis) para aproximar o Pi. Se você realmente precisa de Pi durante o apocalipse zumbi, esses métodos não desperdiçam munição ! Existem mais oito desafios por vir. Faça o checkout da caixa de areia para fazer recomendações.

Simulação

O que estamos simulando? Bem, a probabilidade de que dois inteiros aleatórios sejam relativamente primos (por exemplo, coprime ou gcd == 1) é 6/Pi/Pi, portanto, uma maneira natural de calcular Pi seria colher dois baldes (ou punhados) de rochas; conta-os; veja se o seu gcd é 1; repetir. Depois de fazer isso um par muitas vezes, sqrt(6.0 * total / num_coprimes)tenderá para Pi. Se calcular a raiz quadrada no mundo pós-apocalíptico o deixa nervoso, não se preocupe! Existe o método de Newton para isso.

Como estamos simulando isso?

  • Aceitar entrada N
  • Faça os seguintes Nhorários:
    • Gere uniformemente números inteiros positivos aleatórios iej
    • Com 1 <= i , j <= 10^6
    • Se gcd(i , j) == 1:result = 1
    • Outro: result = 0
  • Pegue a soma dos Nresultados,S
  • Retorna sqrt(6 * N / S)

insira a descrição da imagem aqui

Especificação

  • Entrada
    • Flexível, receba informações de qualquer uma das formas padrão (por exemplo, parâmetro de função, STDIN) e em qualquer formato padrão (por exemplo, String, Binário)
  • Saída
    • Flexível, produza de qualquer forma padrão (por exemplo, devolução, impressão)
    • Espaço em branco, espaço em branco à direita e à esquerda é aceitável
    • Precisão, forneça pelo menos 4 casas decimais de precisão (ou seja 3.1416)
  • Pontuação
    • O código mais curto vence!

Casos de teste

Sua saída pode não estar alinhada com isso, por causa do acaso. Mas, em média, você deve obter tanta precisão para o valor especificado de N.

Input     ->  Output 
-----         ------
100       ->  3.????
10000     ->  3.1???
1000000   ->  3.14??
NonlinearFruit
fonte
1
Nossa resposta precisa funcionar N = 1000000ou tudo bem se o programa retornar, por exemplo, um estouro de pilha se Nfor muito grande?
Fatalize
@Fatalize se for uma limitação do idioma, com certeza. Caso contrário, você precisa lidar N=10^6.
NonlinearFruit
1
Relacionado
Luis Mendo
2
O objetivo é enganoso, pois afirma que apenas um par de números inteiros está marcado.
user253751
1
O limite superior para os números aleatórios gerados precisa ser exatamente 1000000? Um limite superior maior seria aceitável?
Sok

Respostas:

12

APL, 23 bytes

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

Explicação:

  • ?⍵2⍴1e6: gerar uma matriz de 2 por of de números aleatórios no intervalo [1..10 6 ]
  • 1+.=∨/: obtenha o MDC de cada par e veja quantos são iguais a 1. Isso calcula S.
  • .5*⍨6×⍵÷: (6 × ÷ ÷ S) 0,5
marinus
fonte
11

Geléia , 20 18 16 bytes

-2 bytes graças a @ Pietu1998 (contagem de cadeia e uso 1s, ċ1no lugar de menos de dois somados <2S)

-2 bytes graças a @Dennis (repita 1e6 várias vezes antes da amostragem para evitar encadeamento)

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

(Extremamente lento devido à função aleatória)

Quão?

Ḥȷ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
fonte
ḤRµȷ6Xµ€g2/ċ1÷³6÷½economiza 2 bytes. ( ȷ6É de 10 ^ 6, em uma única nilad, ċ1contagens aqueles)
PurkkaKoodari
Ah eu não poderia trabalhar para fora como cadeia-lo assim (eu tentei algumas coisas), e esqueceu-se a contagem de um truque - graças (acho que ȷ²é uma pequena pouquinho mais rápido do que ȷ6)
Jonathan Allan
Pode ser. Agora que penso nisso, ȷ²sendo dois links não faz mal aqui, mas exigiria uma ligação extra ou ¤para alguns casos de uso
PurkkaKoodari
1
Ḥȷ6xX€deve funcionar para a amostragem aleatória.
Dennis
9

Python 2, 143 140 132 124 122 124 122 122 bytes

Já faz algum tempo desde que tentei jogar golfe, por isso posso ter perdido algo aqui! Será atualizado à medida que reduzi isso.

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-me aqui!

graças a Jonathan Allan pelo salvamento de dois bytes :)

Kade
fonte
De acordo com o OP, 1 <= i , j <= 10^6então você precisa usar randrange(1,1e6+1).
mbomb007
1
Além disso, é realmente estranho ter o link repl.it no nome do idioma. Um link no nome do idioma deve ser a página inicial do idioma, se houver. Coloque seu link repl.it como um link separado abaixo do seu código.
mbomb007
@ mbomb007 Bom ponto, eu consertei :) Já faz um tempo!
Kade
1
k=lambda:r.randrange(1e6)+1salva dois bytes
Jonathan Allan
1
@JonathanAllan boa captura, obrigado!
Kade6
8

Mathematica, 49 48 51 bytes

Salvo um byte e corrigido um erro, graças a @ LegionMammal978 .

(6#/Count[GCD@@{1,1*^6}~RandomInteger~{2,#},1])^.5&
alefalpha
fonte
1
Você pode salvar um byte:(6#/Count[GCD@@1*^6~RandomInteger~{2,#},1])^.5&
LegionMammal978 15/10
1
Além disso, 1*^6deve ser substituído por {1,1*^6}para garantir que i , j ≠ 0.
LegionMammal978
8

R, 103 99 95 99 98 94 bytes

Provavelmente pode ser jogado um pouco abaixo. Corte 4 bytes devido a @ antoine-sac e outros 4 bytes definindo um alias para sample, usando em ^.5vez de sqrte em 1e6vez de 10^6. Adicionado 4 bytes para garantir que a amostragem ie jseja verdadeiramente uniforme. Removido um byte depois que percebi que 6*N/sum(x)é o mesmo que 6/mean(x). Usado em pryr::fvez de function(x,y)salvar 4 bytes.

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

Saída de amostra:

N=100     -> 3.333333
N=10000   -> 3.137794
N=1000000 -> 3.141709
rturnbull
fonte
1
Você pode simplesmente usar sample(10^6,N). Além de ser mais curto, também é muito mais eficiente.
asac - Restabelece Monica
Posso estar errado, mas a amostra não deve ser usada com replace = T para números inteiros aleatórios adequadamente uniformes. Por exemplo, sample(10,10)é garantido o retorno de todos os números em 1:10, ao passo sample(10,10,T)que produzirá uma seleção aleatória na qual os números podem ser repetidos.
MickyT
@MickyT Você está absolutamente correto, eu acabei de perceber isso há alguns minutos atrás. Não tenho muita certeza de como isso ocorre matematicamente neste caso - até onde posso dizer, ambos os métodos são aproximadamente igualmente precisos. Vou editar minha postagem para adicionar essas informações.
rturnbull
Ambos os métodos são igualmente precisos quando N << 10 ^ 6. Para lidar com N arbitrariamente grande, você precisa provar com substituição, boa captura.
asac - Restabelece Monica 4/16
7

Na verdade, 19 bytes

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

Experimente online!

Explicação:

`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
fonte
i, j não podem ser 0
isaacg
1
@isaacg Eles não são. Se você ler a explicação, ele informará que os valores aleatórios são selecionados entre [0, 10 ** 6) e depois incrementados.
Mego
7

MATL , 22 bytes

1e6Hi3$YrZ}Zd1=Ym6w/X^

Experimente 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
fonte
6

Pitão, 21 bytes

@*6cQ/iMcmhO^T6yQ2lN2

Experimente online.

Explicação

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

Explicação:

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
fonte
Eu <3 Scala! Especialmente porque às vezes realmente precisa de uma explicação.
Roman Gräf
@ RomanGräf Para ser honesto, as únicas coisas que acho que podem não estar claras são 6f, Seq.fille math.random.
Corvus_192
5

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

Teste:

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

Saída:

2.970442628930023
3.188964020716403
3.144483068444827
rnso
fonte
5

JavaScript (ES7), 107 95 94 bytes

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

A versão do ES6 tem exatamente 99 bytes, mas o operador de exponenciação do ES7 **economiza 5 bytes 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
fonte
Na versão Ungolfed gcdchama a funçãog
Roman Gräf
r=_=>esse código ou um desenho?
Aross4
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 mais curto
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 bytes

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

Execute assim:

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

Explicação

Faz o que diz na lata. Requer PHP_GMP para gcd.

Tweaks

  • Salva 3 bytes usando $argn
aross
fonte
4

Perl, 64 bytes

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

Requer a opção de linha de comando -pMntheory=gcd, contada como 13. A entrada é obtida do stdin.

Uso da amostra

$ echo 1000 | perl -pMntheory=gcd pi-rock.pl
3.14140431218772
primo
fonte
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

Relativamente lento, mas ainda funciona. Replicar N vezes uma função que recebe 2 números aleatórios (de 1 a 1e6) e verifica se o seu MDC é menor que 2 (usando uma função antiga do meu MDC ).

plannapus
fonte
1
Se você não estiver preocupado com avisos, 1:xfuncionará.
MickyT
4

PowerShell v2 +, 118 114 bytes

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)

Recebe entrada $n, inicia um forloop até ser $kigual $n(implícito $k=0na primeira entrada no loop). A cada iteração, obtenha novos Randomnúmeros $ie $j(o sinalizador -mimínimo 1garante que >=1não existam e nenhum sinalizador máximo permite [int]::MaxValue, o que é permitido pelo OP, pois é maior que 10e6).

Em seguida, entramos em um loop GCDwhile . Então, enquanto o GCD estiver 1, $oserá incrementado. No final do forloop, fazemos uma simples[math]::Sqrt() chamada , que é deixada no pipeline e a saída está implícita.

Demora cerca de 15 minutos para executar a entrada 10000no meu laptop Core i5 com ~ 1 ano de idade.

Exemplos

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

Explicação

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
}

Equipamento de teste

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

Atualizar

  • -13 [16-10-05] Graças ao @TNT e adicionado equipamento de teste
NonlinearFruit
fonte
1
Você não precisa de parênteses ao redor do primeiro n, t+=1pode se tornar t++, pode condensar suas intdeclarações em uma linha, ou seja int c=n,t=0,x,y;, e !=0(acho) pode se tornar >0. Isso deve economizar 12 bytes no geral. Essa é uma maneira elegante de encontrar o MDC de x e y, no entanto.
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]

Eu tive sorte: g = n = ... salva um byte sobre g = 0 n = ... ; e 1% gcd () dá (0,1) vs (1,0) para que eu possa subtrair. E azarado: n é pré-atribuído e um usado porque variáveis de laço e seus limites são locais e indefinido fora do loop.

Verbose

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 ½
maybeso
fonte
São 90 bytes e 88 caracteres ...?
CalculatorFeline
Obrigado por capturar isso. Não contei novas linhas e, embora ², ³ sejam apenas 1 byte ⁶, é mais. Corrigi-o para 89 bytes sem nova linha final.
21417 Maybeso
Você não corrigiu o código detalhado.
CalculatorFeline
Não é um jogo de um-para-um de qualquer maneira com espaçamento, as aspas e números, etc.
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

Experimente online!

Estou surpreso que ele seja executado em um período de tempo razoável para 1000000.

Robert Benson
fonte
1

Pyt , 37 35 bytes

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

Explicação:

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

J, 27 bytes

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

Explicação:

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

Tive muita sorte com um 3.14157for N = 10000000, que levou 2.44segundos.

Bolce Bussiere
fonte
1

Japonês , 23 bytes

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

Tente

Shaggy
fonte