Sobre a série

Primeiro, você pode tratar isso como qualquer outro desafio de golfe com código e respondê-lo sem se preocupar com a série. No entanto, existe uma tabela de classificação em todos os desafios. Você pode encontrar a tabela de classificação junto com mais informações sobre a série no primeiro post .

Embora eu tenha várias idéias alinhadas para a série, os desafios futuros ainda não estão definidos. Se você tiver alguma sugestão, informe-me na postagem da sandbox relevante .

Furo 2: Números de uma distribuição normal

Não acredito que isso ainda não foi feito! Você deve gerar números aleatórios, a partir de uma distribuição normal . Algumas regras (a maioria delas provavelmente são cobertas automaticamente pela maioria dos envios, mas algumas existem para garantir a consistência dos resultados entre idiomas muito diferentes):

• Você deve usar dois números inteiros não negativos como entrada : uma semente Se a quantidade Nde números a serem retornados. A saída deve ser uma lista de Nnúmeros de ponto flutuante, extraídos de uma distribuição normal com média 0 e variação 1 . Sempre que sua submissão recebe a mesma semente, Sela deve produzir o mesmo número. Em particular, se for chamado uma vez com e uma vez com , as primeiras entradas das duas saídas deverão ser idênticas. Além disso, pelo menos 2 ¹⁶ valores diferentes de devem produzir sequências diferentes.(S, N1)(S, N2)min(N1, N2)S

• Você pode usar qualquer gerador de números aleatórios incorporado que esteja documentado para desenhar números de uma distribuição (aproximadamente) uniforme , desde que você possa transmiti S-lo e suportar pelo menos 2 ¹⁶ sementes diferentes. Se o fizer, o RNG deve poder retornar pelo menos 2 ²⁰ valores diferentes para qualquer número que você solicitar.

• Se o seu RNG uniforme disponível tiver um alcance menor, não puder ser cultivado ou suportar poucas sementes, você deve primeiro criar um RNG uniforme com um intervalo suficientemente grande em cima do incorporado ou implementar seu próprio RNG adequado usando a semente. Esta página pode ser útil para isso.
• Se você não implementar um algoritmo estabelecido para gerar distribuições normais, inclua uma prova de correção. Em qualquer um dos casos, o algoritmo que você escolher deve gerar uma distribuição normal teoricamente exata (exceto restrições do PRNG subjacente ou tipos de dados de precisão limitada).
• Sua implementação deve usar e retornar números de ponto flutuante (pelo menos 32 bits de largura) ou números de ponto fixo (pelo menos 24 bits de largura) e todas as operações aritméticas devem fazer uso da largura total do tipo escolhido.
• Você não deve usar nenhuma função interna diretamente relacionada à distribuição normal ou integrais gaussianas, como a função Error ou sua inversa.

Você pode escrever um programa completo ou uma função e receber entradas via STDIN, argumento de linha de comando, argumento de função ou prompt e produzir saída via valor de retorno ou imprimindo em STDOUT (ou alternativa mais próxima).

Se Nserão números inteiros não negativos, cada um menor que 2 ²⁰ . A saída pode estar em qualquer lista conveniente ou inequívoca ou formato de string.

Isso é código de golfe, então a submissão mais curta (em bytes) vence. E, é claro, o menor envio por usuário também entrará na tabela geral de líderes da série.

Entre os melhores

O primeiro post da série gera uma tabela de classificação.

Para garantir que suas respostas sejam exibidas, inicie todas as respostas com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

(O idioma não é mostrado no momento, mas o snippet exige e o analisa, e eu posso adicionar um cabeçalho por idioma no futuro.)

Dyalog APL, 33 bytes

{(.5*⍨¯2×⍟?0)×1○○2×?0}¨⍳⎕⊣⎕rl←1+⎕

Box-Muller :

⎕         ⍝ evaluated input
⎕rl←1+⎕   ⍝ set APL's random seed to 1+⎕ (S)
          ⍝   add 1 because ⎕rl←0 has special meaning: sets the seed randomly
{ }¨⍳N    ⍝ do the thing in braces N times
?0        ⍝ random number 0≤x<1
1○○2×A    ⍝ sin(2πA)
.5*⍨¯2×⍟B ⍝ sqrt(-2lnB)

R, 68 bytes

function(S,N){set.seed(S);sqrt(-2*log(runif(N)))*cos(2*pi*runif(N))}

Isso usa a runif()função, que gera desvios aleatórios de uma distribuição uniforme. A semente para a geração de números aleatórios é especificada usando set.seed(), que por padrão usa o algoritmo de Mersenne-Twister com um período de 2 ^ 19937-1.

O resultado é um vetor R de comprimento N contendo os desvios normais padrão calculados.

Utiliza o método Box-Muller: Para duas variáveis ​​aleatórias uniformes independentes U e V,

Dyalog APL, 42 34

{⎕RL←⍺⋄{(.5*⍨¯2×⍟⍺)×1○⍵×○2}/?⍵2⍴0}

Essa é uma função que assume Scomo argumento à esquerda e Ncomo argumento à direita.

     5{⎕RL←⍺⋄{(.5*⍨¯2×⍟⍺)×1○⍵×○2}/?⍵2⍴0}10
3.019132549 ¯0.2903143175 ¯0.7353414637 1.421417015 2.327544764 ¯0.00005019747711 ¯0.9582127248 ¯0.2764568462
      ¯0.1602736853 ¯0.9912352616
     5{⎕RL←⍺⋄{(.5*⍨¯2×⍟⍺)×1○⍵×○2}/?⍵2⍴0}20
3.019132549 ¯0.2903143175 ¯0.7353414637 1.421417015 2.327544764 ¯0.00005019747711 ¯0.9582127248 ¯0.2764568462
      ¯0.1602736853 ¯0.9912352616 0.642585109 ¯0.2450019151 ¯0.415034463 0.03481768503 ¯0.4621212815 ¯0.760925979
      0.2592913013 1.884867889 ¯0.9621252731 0.3062560446

É uma implementação da transformação Box-Muller, usando o operador aleatório interno do Dyalog APL ?, que por padrão é um twister de Mersenne que retorna valores de 64 bits, o que deve ser suficiente.

Explicação:

• ⎕RL←⍺: defina a semente aleatória como ⍺.
• ?⍵2⍴0: gera ⍵pares de números aleatórios entre 0 e 1.
• {... }/: aplique a seguinte função a cada par:
  • (.5*⍨¯2×⍟⍺)×1○⍵×○2: calcule o Z0valor ( sqrt(-2 ln ⍺)×cos(2π⍵)).

Perl, 67

sub f{srand$_[0];map{cos(atan2(1,1)*rand 8)*sqrt-2*log rand}1..pop}

Box-Muller como em outras entradas. fleva parâmetros em ordem S, N.

Usar:

$ perl -le 'sub f{srand$_[0];map{cos(atan2(1,1)*rand 8)*sqrt-2*log rand}1..pop}print for f(5,3)'
-1.59212831801942
0.432167710756345
-0.533673305924252

Java, 164 161 bytes

class B extends java.util.Random{B(int s,int n){super(s);for(;n-->0;System.out.println(Math.sqrt(-2*Math.log(nextDouble()))*Math.cos(2*Math.PI*nextDouble())));}}

Isso recebe entrada via função e saída via stdout. Ele usa o método Box-Muller.

Commodore 64 Básico, 76 70 63 bytes

1INPUTS,N:S=R/(-S):F┌I=1TON:?S●(-2*LOG(R/(1)))*S╮(2*π*R/(1)):N─

Como o conjunto de caracteres PETSCII contém alguns símbolos não presentes no Unicode, fiz substituições: /= SHIFT+N, ┌= SHIFT+O, ●= SHIFT+Q, ╮= SHIFT+I, ─=SHIFT+E

Isso implementa a transformação Box-Muller padrão para gerar os números; Eu escolhi a metade do pecado (x) da transformação porque o Commodore 64 Basic possui um atalho de dois caracteres para sin(), mas não para cos().

Embora os estados manuais Caso contrário, o valor do argumento para RND não importa: se um número negativo é passado, o gerador de números aleatórios não é meramente re-semeado, é re-semeado com esse número . Isso torna a propagação muito mais simples: em vez de precisar de POKEcinco locais de memória, eu apenas preciso fazer uma chamada de não fazer nada RND, o que reduz o código de duas linhas / 121 bytes para 1 linha / 76 bytes.

Edit: Golfed seis bytes off, percebendo que eu poderia combinar as duas INPUTinstruções, e que o espaço depois TOera opcional.

Edit: Jogou mais sete partidas: o Commodore Basic, de fato, tem o Pi como uma constante interna, e é até tipificável em um teclado moderno ( SHIFT+PgDnno caso de você estar se perguntando).

Código da máquina 80386, 72 bytes

Hexdump do código:

60 8b 7c 24 24 33 ed 8d 75 fb 8d 46 79 f7 e2 f7
f6 8b da b3 7f 0f cb d1 eb 89 1f d9 07 d9 e8 de
e9 33 ee 75 e5 d9 ed d9 c9 d9 f1 dc c0 d9 e0 d9
fa d9 c9 d9 eb de c9 dc c0 d9 ff de c9 d9 1f 83
c7 04 e2 c6 61 c2 04 00

Aqui está o código fonte (pode ser compilado pelo Visual Studio):

__declspec(naked) void __fastcall doit(int count, unsigned seed, float* output)
{
    _asm {
                                // ecx = count
                                // edx = seed
        // save registers
        pushad;
        mov edi, [esp + 0x24];  // edi = pointer to output
        xor ebp, ebp;           // ebp = 0
        lea esi, [ebp - 5];     // esi = 4294967291 (a prime number)

    myloop:
        // Calculate the next random number
        lea eax, [esi + 121];   // eax = 116
        mul edx;
        div esi;
        mov ebx, edx;

        // Convert it to a float in the range 1...2
        mov bl, 0x7f;
        bswap ebx;
        shr ebx, 1;

        // Convert to range 0...1 and push onto the FPU stack
        mov [edi], ebx;
        fld dword ptr [edi];
        fld1;
        fsubp st(1), st;

        // Make 2 such random numbers
        xor ebp, esi;
        jnz myloop;

        // Calculate sqrt(-2*ln(x))
        fldln2;
        fxch;
        fyl2x;
        fadd st, st(0);
        fchs;
        fsqrt;

        // Calculate cos(2*pi*y)
        fxch st(1);
        fldpi;
        fmul;
        fadd st, st(0);
        fcos;

        // Calculate and write output
        fmulp st(1), st;
        fstp dword ptr [edi];
        add edi, 4;

        // Repeat
        loop myloop

        // Return
        popad;
        ret 4;
    }
}

Aqui eu uso um gerador de números aleatórios Lehmer . Ele usa o seguinte algoritmo:

x(k+1) = 116 * x(k) mod 4294967291

Aqui 4294967291 é um número primo grande (2 ^ 32-5) e 116 é um número pequeno (menor que 128; veja abaixo) que é sua raiz primitiva . Eu escolhi uma raiz primitiva que tem uma distribuição mais ou menos aleatória de zeros e uns na representação binária (01110100). Esse RNG possui o período máximo possível de 4294967290, se a semente for diferente de zero.

Os números relativamente pequenos que usei aqui (116 e 4294967291, que também podem ser representados como -5) me permitem aproveitar a leacodificação da instrução:

8d 46 79     lea eax, [esi+121]

Ele é montado em 3 bytes se os números puderem caber em 1 byte.

A multiplicação e a divisão usam edxe eaxcomo seus registros de trabalho, e é por isso que criei seedo segundo parâmetro para a função (a fastcallconvenção de chamada usa edxpara passar o segundo parâmetro). Além disso, o primeiro parâmetro é passado ecx, o que é um bom local para armazenar um contador: um loop pode ser organizado em 1 instrução!

e2 c6        loop myloop

Para converter um número inteiro em um número de ponto flutuante, explorei a representação de números de ponto flutuante de precisão única: se eu definir os 9 bits altos (expoente) no padrão de bits 001111111e deixar os 23 bits baixos aleatoriamente, obtenha um número aleatório no intervalo de 1 a 2. Eu peguei a ideia daqui . Para definir os 9 bits mais altos, usei algumas brincadeiras em ebx:

mov ebx, edx;    xxxxxxxx|yyyyyyyy|zzzzzzzz|aaaaaaaa
mov bl, 0x7f;    xxxxxxxx|yyyyyyyy|zzzzzzzz|01111111
bswap ebx;       01111111|zzzzzzzz|yyyyyyyy|xxxxxxxx
shr ebx, 1;      00111111|1zzzzzzz|zyyyyyyy|yxxxxxxx

Para gerar dois números aleatórios, usei um loop aninhado de 2 iterações. Eu o organizei com xor:

xor ebp, esi;    first time, the result is -5
jnz myloop;      second time, the result is 0 - exit loop

O código de ponto flutuante implementa a transformação Box-Muller .

Haskell, 118  144 

import System.Random;h z=let(u,r)=random z in(cos$2*pi*fst(random r)::Float)*sqrt(-2*log u):h r;g=(.(h.mkStdGen)).take

Exemplo de uso:

*Main> g 3 0x6AE4A92CAFA8A742
[0.50378895,-0.20593005,-0.16684927]
*Main> g 6 0x6AE4A92CAFA8A742
[0.50378895,-0.20593005,-0.16684927,1.1229043,-0.10026576,0.4279402]
*Main> g 6 0xE09B1088DF461F7D
[2.5723906,-0.5177805,-1.3535261,0.7400385,3.5619608e-3,-8.246434e-2]

O tipo de retorno de randomé restrito a Float, o que faz randomgerar uma flutuação uniforme em [0, 1). A partir de então, é uma fórmula simlpe box-muller com alguma mágica inútil para a geração de listas.

Golflua, 63 70

Golflua informações e instruções.

\g(n,s)`_ENV,b=M,{}rs(s)~@i=1,n b[i]=q(l(r()^-2))*c(r()*pi)$~b$

Retorna uma tabela contendo os valores. No exemplo que estou usando ~T.u( ), que é igual a return table.unpack( )lua.

> ~T.u(g(3,1234567))
0.89302672974232 0.36330401643578 -0.64762161593981
> ~T.u(g(5,1234567))
0.89302672974232 0.36330401643578 -0.64762161593981 -0.70654636393063 -0.65662878785425
> ~T.u(g(5,7654321))
0.3867923683064 -0.31758512485963 -0.58059120409317 1.2079459300077 1.1500121921242

Muitos caracteres foram salvos configurando o ambiente da função para M(aka math).

SAS, 108

Eu já postei uma resposta em R que é mais curta que isso, mas há muito poucas respostas SAS no PPCG, então por que não adicionar outra?

%macro f(s,n);data;do i=1 to &n;x=sqrt(-2*log(ranuni(&s)))*cos(8*atan2(1,1)*ranuni(&s));put x;end;run;%mend;

Com algum espaço em branco:

%macro f(s, n);
    data;
        do i = 1 to &n;
            x = sqrt(-2 * log(ranuni(&s))) * cos(8 * atan2(1, 1) * ranuni(&s));
            put x;
        end;
    run;
%mend;

Isso define uma macro que pode ser chamada como %f(5, 3). A macro executa uma etapa de dados que percorre os números inteiros 1 a N e, a cada iteração, calcula um desvio normal aleatório usando o Box-Muller e imprime no log usando a putinstrução

O SAS não possui built-in para pi, portanto, o melhor que podemos fazer é aproximar-se com arctangent.

A ranuni()função (que foi preterida, mas requer alguns caracteres a menos que a função mais recente) retorna um número aleatório de uma distribuição uniforme. A documentação do SAS não fornece muitos detalhes sobre a implementação do RNG, a não ser que tenha um período de 2 ^ 31-2.

Nas macros SAS, as variáveis ​​de macro são referenciadas com um precedente &e resolvem seus valores no tempo de execução.

Como você provavelmente já testemunhou, o SAS raramente é um candidato real em um concurso de código-golfe .

Java, 193 bytes

Embora isso não supere o atual líder Java, decidi postar de qualquer maneira para mostrar um método diferente de cálculo. É uma versão de golfe do OpenJDK nextGaussian().

class N extends java.util.Random{N(int s,int n){super(s);for(float a,v;n-->0;System.out.println(v*Math.sqrt(-2*Math.log(a)/a)))for(a=0;a>=1|a==0;a=v*v+(v=2*nextFloat()-1)*v)v=2*nextFloat()-1;}}

Com quebras de linha:

class N extends java.util.Random{
    N(int s,int n){
        super(s);
        for(float a,v;
            n-->0;
            System.out.println(v*Math.sqrt(-2*Math.log(a)/a)))
                for(a=0;
                    a>=1|a==0;
                    a=v*v+(v=2*nextFloat()-1)*v)v=2*nextFloat()-1;
    }
}

T-SQL, 155 bytes

CREATE PROC R(@S BIGINT,@N INT)AS
DECLARE @ INT=0,@K INT=8388607WHILE @<@N
BEGIN
SELECT SQRT(-2*LOG(RAND(@S*@%@K)))*COS(2*PI()*RAND(@S*9*@%@K))SET @+=1
END

Use com EXEC RS, N, porque não há STD_IN no T-SQL, em que S e N são a semente e N, respectivamente. S produzirá sequências "aleatórias" (RAND (semente) é uma péssima implementação de números aleatórios) quando S> 2 ^ 16 (possivelmente antes disso, mas não garanto). Usa o Box-Muller como a maioria das soluções até agora. 8388607 é 2 ^ 23-1, o que deve gerar 2 ^ 20 valores diferentes.

Powershell, 164 bytes

Param($s,$n)$q=2147483647
$a=GET-RANDOM -SETSEED $s
FOR(;$n---gt0;){$a=GET-RANDOM
$b=GET-RANDOM
[math]::SQRT(-2*[math]::LOG($a/$q))*[math]::COS(2*[math]::PI*$b/$q)}

O mesmo que a maioria das respostas com o Box-Muller. Não tem muita experiência com o Powershell, então qualquer ajuda com o golfe seria apreciada.

Ruby, 72 bytes

->n,s{include Math;srand s;n.times{p sqrt(-2*log(rand))*sin(2*rand*PI)}}

Entrada (como função lambda):

f.(6, 12353405)

Resultado:

-1.1565142460805273
0.9352802655317097
1.3566720571574993
-0.9683973210257978
0.9851210877202192
0.14709635752306677

PS: Eu gostaria de saber se isso pode ser jogado mais. Eu sou apenas um iniciante.

Matlab, 77

A primeira entrada deve ser n, a segunda s.

a=input('');
rand('seed',a(2));
for i=1:a;
    (-2*log(rand))^.5*cos(2*pi*rand)
end

Oitava, 91 96 88 bytes

function r=n(s,n)rand("seed",s);x=rand(2,n);r=cos(2*pi*x(1,:)).*sqrt(-2*log(x(2,:)));end

Ou, com espaço em branco:

function r=n(s,n)
  rand("seed",s);
  x=rand(2,n);
  r=cos(2*pi*x(1,:)).*sqrt(-2*log(x(2,:)));
end

Coloque a semente na frente e use o método Box-Mueller.

Nota: O Octave permite a geração de matrizes de números aleatórios e pode usar operações padrão nessas matrizes que produzem saídas de matriz. O .*operador é a multiplicação elemento a elemento de duas matrizes para produzir o resultado.

Pitão, 32 bytes

Nenhum Python sendo usado agora em super cotações por causa das novas funções que o Pyth possui agora. Mais um Box-Mueller.

 .xvzVQ*@_y.lOZ2.71 2.ty*3.14OZ1

Esse espaço no começo é importante.

.xvz             Seed RNG with evaluated input
VQ               For N in second input
*                Multiplication
 @       2       Square root
   _y            Times negative 2
    .l )         Natural log
     OZ          Of random float (RNG with zero give [0, 1) float)
 .t       1      Cosine from list of trig functions
  y              Double
   *             Multiplication
    .nZ          Pi from constants list
    OZ           Random Float

A propagação parece não funcionar no intérprete online, mas funciona bem na versão local. O intérprete on-line parece estar corrigido, então aqui está um link permanente: link permanente

STATA, 85 bytes

di _r(s)_r(n)
set se $s
set ob $n
g a=sqrt(-2*ln(runiform()))*cos(2*runiform()*_pi)
l

Recebe a entrada via padrão (o primeiro número é S e depois N). Define a semente como S. Define o número de observações como N. Cria uma variável e define seu valor como o valor da transformação Box Muller (obrigado a @Alex por mostrá-lo). Em seguida, lista todas as observações em uma tabela com o cabeçalho da coluna a e os números de observação próximos a eles. Se não estiverem bem, informe-me e posso remover cabeçalhos e / ou números de observação.

R, 89 bytes

Eu sei que R já foi feito antes, mas eu queria mostrar uma abordagem diferente da Box-Muller que todos os outros usavam. Minha solução usa o Teorema do Limite Central .

f=function(S,N){set.seed(S);a=1000;for(i in(1:N)){print(sqrt(12/a)*(sum(runif(a))-a/2))}}

TI-Básico, 74 bytes

Prompt S,N:S→rand:For(X,1,N:0→A:0→V:0→W:While A≥1 or A=0:2rand-1→V:2rand-1→W:V²+W²→A:End:Disp VW√(Aֿ¹-2log(A:End

1      1111111   11   1111111111111111111     1111   111111   1111111   11111111111111  11    111111111   111

Na ¹verdade, é o operador inverso.

Perl, 150 108 107 bytes

Isso usa o método polar Marsaglia . Chamado com f (S, N).

Movida a atribuição de $apara o cálculo de $c.

107:

sub f{srand$_[0];map{do{$c=($a=-1+2*rand)**2+(-1+2*rand)**2}until$c<1;print$a*sqrt(-2*log($c)/$c)}1..$_[1]}

Removido o armazenamento do número de reposição e a definição de $b.

108:

sub f{srand$_[0];map{do{$a=-1+2*rand,$c=$a**2+(-1+2*rand)**2}until$c<1;print$a*sqrt(-2*log($c)/$c)}1..$_[1]}

150:

sub f{srand$_[0];map{$h?$h=!print$s:do{do{$a=-1+2*rand,$b=-1+2*rand,$c=$a*$a+$b*$b}until$c<1;$d=sqrt(-2*log($c)/$c);$s=$b*$d;$h=print$a*$d;}}1..$_[1]}

Swift, 144 142

Nada inteligente, apenas vendo como o Swift funciona.

import Foundation;func r(s:UInt32,n:Int){srand(s);for i in 0..<n{println(sqrt(-2*log(Double(rand())/0xffffffff))*sin(2*Double(rand())*M_PI))}}

Eu esperava poder usar (0 ... n) .map {}, mas o compilador não parece reconhecer o mapa {}, a menos que você use um parâmetro.

Haskell , 97 bytes

import System.Random
h(a:b:c)=sqrt(-2*log a::Float)*cos(2*pi*b):h c
f a=take a.h.randoms.mkStdGen

Experimente online!

Apenas sua transformação básica de Box-Muller, em uma lista infinita de números aleatórios.

Python 3 , 118 bytes

from random import*
from math import*
def f(s,n):seed(s);return[sqrt(-2*log(random()))*cos(tau*random())for _ in[0]*n]

Experimente online!

SmileBASIC, 81 bytes

Bem, agora que respondi à primeira pergunta, tenho que fazer todo o resto ...

Gerar números aleatórios é barato, mas semear o RNG usa a função interna mais longa do idioma RANDOMIZE,.

DEF N S,N
RANDOMIZE.,S
FOR I=1TO N?SQR(-2*LOG(RNDF()))*COS(PI()*2*RNDF())NEXT
END

Talvez haja alguma maneira de otimizar a fórmula. Não vejo como é necessário usar duas chamadas RNG.