Golf aleatorio del día # 4: la paradoja de Bertrand

19

Sobre la serie

En primer lugar, puede tratar esto como cualquier otro desafío de golf de código y responderlo sin preocuparse por la serie. Sin embargo, hay una tabla de clasificación en todos los desafíos. Puede encontrar la tabla de clasificación junto con más información sobre la serie en la primera publicación .

Aunque tengo un montón de ideas para la serie, los desafíos futuros aún no están establecidos en piedra. Si tiene alguna sugerencia, hágamelo saber en la publicación de sandbox relevante .

Hoyo 4: La paradoja de Bertrand

La paradoja de Bertrand es un problema interesante, que muestra cómo los diferentes métodos para elegir acordes aleatorios en un círculo pueden producir diferentes distribuciones de acordes, sus puntos medios y sus longitudes.

En este desafío, se supone que debe generar acordes aleatorios del círculo de la unidad, utilizando el método "correcto", es decir, uno que produce una distribución de acordes que es invariable bajo la escala y la traducción. En el artículo vinculado de Wikipedia, "Método 2" es un método de este tipo.

Aquí están las reglas exactas:

  • Debe tomar un entero positivoN que especifique cuántos acordes se deben devolver. La salida debe ser una lista de Nacordes, cada uno especificado como dos puntos en el círculo unitario, dado por su ángulo polar en radianes.
  • Su código debe poder devolver al menos 2 20 valores diferentes para cada uno de los dos ángulos . Si su RNG disponible tiene un rango más pequeño, primero debe construir un RNG con un rango lo suficientemente grande encima del incorporado o debe implementar su propio RNG adecuado . Esta página puede ser útil para eso.
  • La distribución de los acordes debe ser indistinguible de la producida por el "Método 2" en el artículo vinculado de Wikipedia. Si implementa un algoritmo diferente para elegir acordes, incluya una prueba de corrección. Cualquiera que sea el algoritmo que elija implementar, en teoría debe ser capaz de generar cualquier acorde válido en el círculo unitario (salvo las limitaciones del PRNG subyacente o los tipos de datos de precisión limitada).
  • Su implementación debe usar y devolver números de punto flotante (al menos 32 bits de ancho) o números de punto fijo (al menos 24 bits de ancho) y todas las operaciones aritméticas deben ser precisas en un máximo de 16 ulp .

Puede escribir un programa completo o una función y recibir información a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y producir salida a través de STDOUT (o alternativa más cercana), valor de retorno de función o parámetro de función (out).

La salida puede estar en cualquier lista conveniente o formato de cadena, siempre que los números individuales sean claramente distinguibles y su número total sea siempre par.

Este es el código de golf, por lo que gana el envío más corto (en bytes). Y, por supuesto, la presentación más corta por usuario también entrará en la tabla de clasificación general de la serie.

Visualización

Puede usar el siguiente fragmento para representar las líneas generadas e inspeccionar su distribución. Simplemente pegue una lista de pares de ángulos en el área de texto. El fragmento debe poder manejar casi cualquier formato de lista, siempre que los números sean simples números decimales (sin notación científica). Le recomiendo que use al menos 1000 líneas para tener una buena idea de la distribución. También proporcioné algunos datos de ejemplo para los diferentes métodos presentados en el artículo a continuación.

Datos de ejemplo generados con el método 1.

Datos de ejemplo generados con el método 2.

Datos de ejemplo generados con el método 3.

Tabla de clasificación

La primera publicación de la serie genera una tabla de clasificación.

Para asegurarse de que sus respuestas aparezcan, comience cada respuesta con un título, utilizando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntuación, se puede mantener viejas cuentas en el título, golpeándolos a través. Por ejemplo:

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

(El idioma no se muestra actualmente, pero el fragmento requiere y analiza, y puedo agregar una tabla de clasificación por idioma en el futuro).

Martin Ender
fuente

Respuestas:

12

Código de máquina IA-32, 54 bytes

Hexdump del código:

68 00 00 00 4f 0f c7 f0 50 db 04 24 58 d8 34 24
f7 d9 78 f1 d9 c0 dc c8 d9 e8 de e1 d9 fa d9 c9
d9 f3 dc c0 d9 eb de ca d8 c1 dd 1a dd 5a 08 83
c2 10 e2 d1 58 c3

Utiliza un algoritmo (ligeramente modificado) que Wikipedia describió. En pseudocódigo:

x = rand_uniform(-1, 1)
y = rand_uniform(-1, 1)
output2 = pi * y
output1 = output2 + 2 * acos(x)

Utilizo el rango -1...1porque es fácil hacer números aleatorios en este rango: la rdrandinstrucción genera un número entero entre -2^31y 2^31-1, que se puede dividir fácilmente por 2 ^ 31.

Debería haber usado el rango 0...1para el otro número aleatorio (x), que se alimenta acos; sin embargo, la parte negativa es simétrica con la parte positiva: los números negativos producen acordes cuyo lapso es mayor que pi radianes, pero con el propósito de ilustrar la paradoja de Bertrand, no importa.

Como el conjunto de instrucciones 80386 (o x87) no tiene una acosinstrucción dedicada , tuve que expresar el cálculo usando solo la ataninstrucción:

acos(x) = atan(sqrt(1-x^2)/x)

Aquí está el código fuente que genera el código de máquina anterior:

__declspec(naked) void __fastcall doit1(int n, std::pair<double, double>* output)
{
    _asm {
        push 0x4f000000;        // [esp] = float representation of 2^32

    myloop:
        rdrand eax;             // generate a random number, -2^31...2^31-1
        push eax;               // convert it
        fild dword ptr [esp];   // to floating-point
        pop eax;                // restore esp
        fdiv dword ptr [esp];   // convert to range -1...1
        neg ecx;
        js myloop;              // do the above 2 times

        // FPU stack contents:  // x           | y
        fld st(0);              // x           | x   | y
        fmul st(0), st;         // x^2         | x   | y
        fld1;                   // 1           | x^2 | x | y
        fsubrp st(1), st;       // 1-x^2       | x   | y
        fsqrt;                  // sqrt(1-x^2) | x   | y
        fxch;                   // x           | sqrt(1-x^2) | y
        fpatan;                 // acos(x)     | y
        fadd st, st(0);         // 2*acos(x)   | y
        fldpi;                  // pi          | 2*acos(x) | y
        fmulp st(2), st;        // 2*acos(x)   | pi*y
        fadd st, st(1);         // output1     | output2
        fstp qword ptr [edx];   // store the numbers
        fstp qword ptr [edx + 8];

        add edx, 16;            // advance the output pointer
        loop myloop;            // loop

        pop eax;                // restore stack pointer
        ret;                    // return
    }
}

Para generar dos números aleatorios, el código usa un bucle anidado. Para organizar el bucle, el código aprovecha el ecxregistro (contador del bucle externo) que es positivo. Niega temporalmente ecxy luego lo vuelve a hacer para restaurar el valor original. La jsinstrucción repite el ciclo cuando ecxes negativo (esto sucede exactamente una vez).

anatolyg
fuente
¡Me gusta esta respuesta para usar el ensamblaje IA32! Solo para decir: esto no es estrictamente un código de máquina 386, ya que 80386 obviamente no tiene instrucciones rdrand ni es necesario un coprocesador FP
user5572685
Sí, IA32 es un mejor nombre. No lo suficientemente específico, pero probablemente más correcto que 80386.
anatolyg
7

Pyth, 25 23 22 bytes

Un puerto de respuesta de C ++ 11 de rcrmn. Este es mi primer uso de Pyth, ¡y me he divertido mucho!

VQJ,*y.n0O0.tOZ4,sJ-FJ

Versión de 23 bytes:

VQJ*y.n0O0K.tOZ4+JK-JKd

Corte un byte cambiando el programa para usar pliegues + sumas y estableciendo J en una tupla, eliminando K.

Original:

VQJ**2.n0O0K.tO0 4+JK-JKd

Corte 2 bytes gracias a @orlp.

Explicación:

VQ                         loop as many times as the input number
  J,                       set J to the following tuple expression
    *y.n0O0                2 * .n0 (pi) * O0 (a random number between 0 and 1)
            .tOZ4          .tOZ 4 (acos of OZ (a random number))
                 ,sJ-FJ    print the sum of J and folding J using subtraction in parenthesis, separated by a comma, followed by another newline
kirbyfan64sos
fuente
1
Consejos de Pyth: *2_es lo mismo que y_. La variable Zes inicialmente 0, por lo que puede eliminar el espacio .tO0 4escribiendo .tOZ4.
orlp
1
Estoy contando 25 bytes ...
Maltysen
Además, puede formatear mejor la salida con,+JK-JK
Maltysen
@Maltysen Ambos arreglados. ¡Gracias!
kirbyfan64sos
@orlp no tenía ni idea yy me olvidé Z. Fijo; ¡Gracias!
kirbyfan64sos
6

Julia, 48 bytes

n->(x=2π*rand(n);y=acos(rand(n));hcat(x+y,x-y))

Esto usa el algoritmo del método 2, como la mayoría de las respuestas hasta ahora. Crea una función lambda que toma una entrada entera y devuelve una matriz nx 2. Para llamarlo, dale un nombre, por ejemplo f=n->....

Ungolfed + explicación:

function f(n::Int64)
    # The rand() function returns uniform random numbers using
    # the Mersenne-Twister algorithm

    # Get n random chord angles
    x = 2π*rand(n)

    # Get n random rotations
    y = acos(rand(n))

    # Bind into a 2D array
    hcat(x+y, x-y)
end

Realmente me gusta cómo se ven las visualizaciones, así que incluiré una. Es el resultado de f(1000).

Circulo

Alex A.
fuente
5

Pyth, 22 bytes

Un puerto de la respuesta de C ++. Tenía otra solución de 23 bytes (¡ahora 22!), Pero era casi una copia de la respuesta pyth de @ kirbyfan64sos con optimizaciones, por lo que tuve que pensar un poco fuera de la caja y creativamente (ab) usar el operador de plegado.

m,-Fdsdm,y*.nZOZ.tOZ4Q

Tenga en cuenta que esto no funciona en este momento debido a un error en el operador de plegado después de la introducción de reduce2. Estoy haciendo una solicitud de extracción.

m             Map    
 ,            Tuple of
  -Fd         Fold subtraction on input
  sd          Fold addition on input
 m      Q     Map over range input
  ,           Tuple           
   y          Double
    *         Product
     .nZ      Pi
     OZ       [0, 1) RNG
  .t  4       Acos
    OZ        [0, 1) RNG

Por referencia, esta fue mi otra solución que funciona de la misma manera: VQKy*.nZOZJ.tOZ4,+KJ-KJ

Maltysen
fuente
Escribiste mal mi nombre de usuario ... :(
kirbyfan64sos
@ kirbyfan64sos derp. Lo sentimos;)
Maltysen
4

IDL, 65 bytes

Obviamente, este es el mismo algoritmo que @rcrmn, aunque lo deduje de forma independiente antes de leer su respuesta.

read,n
print,[2,2]#randomu(x,n)*!pi+[-1,1]#acos(randomu(x,n))
end

La función randomu de IDL utiliza el Mersenne Twister, que tiene un período de 2 19937 -1.

EDITAR: ejecuté 1000 acordes a través del visualizador anterior, aquí hay una captura de pantalla del resultado:

IDL bertrand

Sirpercival
fuente
4

C ++ 11, 214 bytes

#include<random>
#include<iostream>
#include<cmath>
int main(){using namespace std;int n;cin>>n;random_device r;uniform_real_distribution<> d;for(;n;--n){float x=2*M_PI*d(r),y=acos(d(r));cout<<x+y<<' '<<x-y<<';';}}

Entonces, esta es una implementación directa del algoritmo correcto de la página de wikipedia. El principal problema aquí en el golf son los nombres tan largos que tienen las clases generadoras aleatorias. Pero, a diferencia del buen rand, es al menos uniforme.

Explicación:

#include<random>
#include<iostream>
#include<cmath>
int main()
{
    using namespace std;
    int n;
    cin>>n; // Input number
    random_device r; // Get a random number generator
    uniform_real_distribution<> d;   // Get a uniform distribution of 
                                     // floats between 0 and 1
    for(;n;--n)
    {
        float x = 2*M_PI*d(r),       // x: Chosen radius angle
              y = acos(d(r));        // y: Take the distance from the center and 
                                     // apply it an inverse cosine, to get the rotation

        cout<<x+y<<' '<<x-y<<';';    // Print the two numbers: they are the rotation
                                     // of the radius +/- the rotation extracted from
                                     // the distance to the center
    }
}
rorlork
fuente
1
Ese factor M_PI_2parece sospechoso. Creo que debería ser 1 en su lugar.
anatolyg
Sí, completamente correcto, ¡lo arreglaré ahora! ¡Muchas gracias!
rorlork
4

APL, 46 bytes

f←{U←⍵ 2⍴∊{(○2×?0)(¯1○?0)}¨⍳⍵⋄⍉2⍵⍴∊(+/U)(-/U)}

¡Mi primer programa APL! Seguramente se puede mejorar enormemente (ya que mi comprensión general de APL es insuficiente), por lo que cualquier sugerencia sería fantástica. Esto crea una función fque toma un número entero como entrada, calcula los pares de puntos de acorde utilizando el método 2 e imprime cada par separado por una nueva línea.

¡Puedes probarlo en línea !

Explicación:

f←{ ⍝ Create the function f which takes an argument ⍵

    ⍝ Define U to be an ⍵ x 2 array of pairs, where the first
    ⍝ item is 2 times a random uniform float (?0) times pi (○)
    ⍝ and the second is the arccosine (¯1○) of another random
    ⍝ uniform float.

    U ← ⍵ 2 ⍴ ∊{(○2×?0)(¯1○?0)}¨⍳⍵

    ⍝ Create a 2 x ⍵ array filled with U[;1]+U[;2] (+/U) and
    ⍝ U[;1]-U[;2] (-/U). Transpose it into an ⍵ x 2 array of
    ⍝ chord point pairs and return it.

    ⍉ 2 ⍵ ⍴ ∊(+/U)(-/U)
}

Nota: Mi solución anterior de 19 bytes no era válida ya que devolvía (x, y) en lugar de (x + y, xy). La tristeza abunda.

Alex A.
fuente
3

Java, 114 bytes

n->{for(;n-->0;){double a=2*Math.PI*Math.random(),b=Math.acos(Math.random());System.out.println(a+b+" "+(a-b));}};

Implementación básica en java. Úselo como una expresión lambda.

Ejemplo de uso

El numero uno
fuente
¿No puedes reducir el tamaño almacenando en Mathalgún lugar? ¿O algo? (No soy un programador de Java)
Ismael Miguel
@IsmaelMiguel Eso costaría 2 caracteres adicionales.
TheNumberOne
Lo sentimos: / Es tentador intentar reducir la cantidad de veces que se Mathmuestra. ¿Qué dice el meta sobre el uso de un código para generar otro código para resolver el problema?
Ismael Miguel
2
@IsmaelMiguel Eso es un juego justo, aunque me sorprendería si en realidad eres mejor en el metagolf que en el golf.
Martin Ender
3

Ruby, 72 bytes

Mi primer golf aquí! Usé el mismo código que todos, espero que esté bien

gets.chomp.to_i.times{puts"#{x=2*Math::PI*rand},#{x+2*Math.acos(rand)}"}
rorlok
fuente
2

Java, 115 123

Esto es básicamente lo mismo que la mayoría de los demás, pero necesito una puntuación de Java para este agujero, así que aquí va:

void i(int n){for(double x;n-->0;System.out.println(x+2*Math.acos(Math.random())+" "+x))x=2*Math.PI*Math.random();}

Se pueden encontrar 1000 acordes de muestra en pastebin , estos son los primeros cinco de una ejecución:

8.147304676211474 3.772704020731153
8.201346559916786 3.4066194978900106
4.655131524088468 2.887965593766409
4.710707820868578 3.8493686706403984
3.3839198612642423 1.1604092552846672
Geobits
fuente
1

CJam, 24 22 bytes

Similar a otros algoritmos, aquí hay una versión en CJam.

{2P*mr_1dmrmC_++]p}ri*

Una entrada de 1000 produce una distribución como:

ingrese la descripción de la imagen aquí

Cómo funciona

El algoritmo es simplemente x = 2 * Pi * rand(); print [x, x + 2 * acos(rand())]

{                 }ri*        e# Run this loop int(input) times
 2P*mr                        e# x := 2 * Pi * rand()
      _                       e# copy x
       1dmr                   e# y := rand()
           mC                 e# z := acos(y)
             _++              e# o := x + z + z
                ]             e# Wrap x and o in an array
                 p            e# Print the array to STDOUT on a new line

Actualizar : 2 bytes guardados gracias a Martin!

Pruébalo aquí

Optimizador
fuente
1

Python 3, 144117 bytes

(gracias a Blckknght por el lambda puntero)

Usando el mismo método que otros:

import math as m;from random import random as r;f=lambda n:[(x,x+2*m.acos(r()))for x in(2*m.pi*r()for _ in range(n))]

De la documentación de Python:

Python usa el Mersenne Twister como generador principal. Produce flotadores de precisión de 53 bits y tiene un período de 2 19937 -1.

Salida

>>> f(10)
[(4.8142617617843415, 0.3926824824852387), (3.713855302706769, 1.4014527571152318), (3.0705105305032188, 0.7693910749957577), (1.3583477245841715, 0.9120275474824304), (3.8977143863671646, 1.3309852045392736), (0.9047010644291349, 0.6884780437147916), (3.333698164797664, 1.116653229885653), (3.0027328050516493, 0.6695430795843016), (5.258167740541786, 1.1524381034989306), (4.86435124286598, 1.5676690324824722)]

Y así.

Visualización

visualización

Puertas de Zach
fuente
Puede guardar unos 20 bytes si utiliza una lambda para la función y devuelve una comprensión de la lista (con una expresión de generador interno):f=lambda n:[(x,x+2*m.acos(r()))for x in(2*m.pi*r()for _ in range(n))]
Blckknght
Ah, tuve una lambda originalmente. Supongo que no pensé en duplicar las comprensiones de la lista. ¡Gracias! @Blckknght
Zach Gates
Se puede acortar a 109 bytes jugando con las importaciones: tio.run/#python2
Triggernometry
1

Perl, 60

#!perl -l
use Math::Trig;print$x=2*pi*rand,$",$x+2*acos rand for 1..<>
nutki
fuente
1

R, 60 56 53 49 bytes

4 bytes adicionales gracias a @JayCe y cambiándolo a una función.

Usando la misma fórmula básica que los demás. R utiliza el método Mersenne-Twister de forma predeterminada, pero se pueden configurar otros. Emite una lista separada por espacios.

function(n,y=acos(runif(n)))runif(n)*2*pi+c(y,-y)

Pruébalo en línea!

MickyT
fuente
Hola Micky, puedes guardar 4 bytes convirtiéndolo en una función y no definiendo x.
JayCe
@JayCe eso está mucho mejor gracias
MickyT
0

SmileBASIC, 62 bytes

INPUT N
FOR I=1TO N
X=PI()*2*RNDF()Y=ACOS(RNDF())?X+Y,X-Y
NEXT
12Me21
fuente