Zufälliges Golf des Tages # 4: Das Bertrand-Paradoxon

19

Über die Serie

Zunächst einmal können Sie dies wie jede andere Code-Golf-Herausforderung behandeln und beantworten, ohne sich Gedanken über die Serie zu machen. Es gibt jedoch eine Rangliste für alle Herausforderungen. Sie finden die Rangliste zusammen mit einigen weiteren Informationen über die Serie im ersten Beitrag .

Obwohl ich eine Menge Ideen für die Serie habe, sind die zukünftigen Herausforderungen noch nicht in Stein gemeißelt. Wenn Sie Vorschläge haben, teilen Sie mir dies bitte auf dem entsprechenden Sandbox-Post mit .

Loch 4: Das Bertrand-Paradoxon

Das Bertrand-Paradoxon ist ein interessantes Problem, das zeigt, wie verschiedene Methoden zum Auswählen zufälliger Akkorde in einem Kreis unterschiedliche Verteilungen von Akkorden, deren Mittelpunkten und Längen ergeben können.

In dieser Herausforderung sollst du zufällige Akkorde des Einheitskreises mit der "richtigen" Methode erzeugen, dh mit einer Verteilung der Akkorde, die unter Skalierung und Übersetzung unveränderlich ist. In dem verlinkten Wikipedia-Artikel ist "Methode 2" eine solche Methode.

Hier sind die genauen Regeln:

  • Sie sollten eine positive Ganzzahl verwenden,N die angibt, wie viele Akkorde zurückgegeben werden sollen. Die Ausgabe sollte eine Liste von NAkkorden sein, die jeweils als zwei Punkte auf dem Einheitskreis angegeben sind und durch ihren Polarwinkel im Bogenmaß angegeben werden.
  • Ihr Code sollte mindestens 2 20 verschiedene Werte für jeden der beiden Winkel zurückgeben können . Wenn Ihr verfügbares RNG eine geringere Reichweite hat, müssen Sie entweder zuerst ein RNG mit einer ausreichend großen Reichweite über dem eingebauten aufbauen oder Sie müssen Ihr eigenes geeignetes RNG implementieren . Diese Seite kann hilfreich sein.
  • Die Verteilung der Akkorde muss nicht von der Verteilung nach "Methode 2" im verlinkten Wikipedia-Artikel zu unterscheiden sein. Wenn Sie einen anderen Algorithmus zur Auswahl von Akkorden verwenden, legen Sie bitte einen Korrektheitsnachweis bei. Unabhängig davon, welchen Algorithmus Sie implementieren, muss er theoretisch in der Lage sein, einen gültigen Akkord im Einheitskreis zu generieren (abgesehen von Einschränkungen des zugrunde liegenden PRNG- oder Datentyps mit begrenzter Genauigkeit).
  • Ihre Implementierung sollte entweder Gleitkommazahlen (mindestens 32 Bit breit) oder Festkommazahlen (mindestens 24 Bit breit) verwenden und zurückgeben, und alle arithmetischen Operationen sollten innerhalb von höchstens 16 ulp genau sein .

Sie können ein vollständiges Programm oder eine Funktion schreiben und Eingaben über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und Ausgaben über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) erzeugen.

Die Ausgabe kann in einem beliebigen Listen- oder Zeichenfolgeformat erfolgen, sofern die einzelnen Zahlen klar voneinander zu unterscheiden sind und ihre Gesamtzahl immer gerade ist.

Dies ist Codegolf, daher gewinnt die kürzeste Übermittlung (in Bytes). Und natürlich wird die kürzeste Einreichung pro Benutzer auch in die Gesamt-Bestenliste der Serie aufgenommen.

Visualisierung

Sie können das folgende Snippet verwenden, um die generierten Linien zu rendern und ihre Verteilung zu überprüfen. Fügen Sie einfach eine Liste von Winkelpaaren in den Textbereich ein. Das Snippet sollte mit fast jedem Listenformat umgehen können, solange die Zahlen einfache Dezimalzahlen sind (keine wissenschaftliche Notation). Ich empfehle Ihnen, mindestens 1000 Zeilen zu verwenden, um eine gute Vorstellung von der Verteilung zu erhalten. Ich habe auch einige Beispieldaten für die verschiedenen Methoden bereitgestellt, die im folgenden Artikel vorgestellt werden.

Beispieldaten, die mit Methode 1 generiert wurden.

Beispieldaten, die mit Methode 2 generiert wurden .

Beispieldaten, die mit Methode 3 generiert wurden.

Bestenliste

Der erste Beitrag der Serie generiert eine Rangliste.

Um sicherzustellen, dass Ihre Antworten angezeigt werden, beginnen Sie jede Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

(Die Sprache wird derzeit nicht angezeigt, das Snippet erfordert sie jedoch und analysiert sie. Ich füge möglicherweise in Zukunft eine Bestenliste nach Sprachen hinzu.)

Martin Ender
quelle

Antworten:

12

IA-32 Maschinencode, 54 Bytes

Hexdump des Codes:

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

Es verwendet einen (leicht modifizierten) Algorithmus, den Wikipedia beschrieben hat. Im Pseudocode:

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

Ich benutze den Bereich, -1...1weil es einfach ist, Zufallszahlen in diesem Bereich zu bilden: Die rdrandAnweisung erzeugt eine ganze Zahl zwischen -2^31und 2^31-1, die leicht durch 2 ^ 31 geteilt werden kann.

Ich hätte den Bereich 0...1für die andere Zufallszahl (x) verwenden sollen, in die eingespeist wird acos; Der negative Teil ist jedoch symmetrisch mit dem positiven Teil - negative Zahlen erzeugen Akkorde, deren Spannweite größer als Pi-Radiant ist, aber zum Zwecke der Veranschaulichung des Bertrand-Paradoxons spielt dies keine Rolle.

Da der Befehlssatz 80386 (oder x87) keinen dedizierten acosBefehl enthält, musste ich die Berechnung nur mit dem atanBefehl ausdrücken :

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

Hier ist der Quellcode, der den obigen Maschinencode generiert:

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

Um zwei Zufallszahlen zu generieren, verwendet der Code eine verschachtelte Schleife. Um die Schleife zu organisieren, nutzt der Code den Vorteil, dass das ecxRegister (Zähler der äußeren Schleife) positiv ist. Es wird vorübergehend negiert ecxund dann erneut ausgeführt, um den ursprünglichen Wert wiederherzustellen. Die jsAnweisung wiederholt die Schleife, wenn sie ecxnegativ ist (dies geschieht genau einmal).

anatolyg
quelle
Ich mag diese Antwort für die Verwendung von IA32-Assembly! Nur um zu sagen: Dies ist kein reiner 386-Maschinencode, da 80386 offensichtlich weder eine RDRAND-Anweisung noch einen FP-Coprozessor benötigt
user5572685 29.04.15
Ja, IA32 ist ein besserer Name. Nicht spezifisch genug, aber wahrscheinlich korrekter als 80386.
anatolyg
7

Pyth, 25 23 22 Bytes

Eine Portierung der C ++ 11-Antwort von rcrmn. Dies ist meine erste Verwendung von Pyth, und ich hatte viel Spaß!

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

23-Byte-Version:

VQJ*y.n0O0K.tOZ4+JK-JKd

Schneiden Sie ein Byte aus, indem Sie das Programm so ändern, dass es Falten + Summen verwendet, und setzen Sie J auf ein Tupel, indem Sie K entfernen.

Original:

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

Schneiden Sie 2 Bytes dank @orlp ab.

Erläuterung:

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
quelle
1
Pyth-Tipps: *2_ist das gleiche wie y_. Die Variable Zist anfangs 0, sodass Sie das Leerzeichen .tO0 4durch Schreiben entfernen können .tOZ4.
Orlp
1
Ich zähle 25 Bytes ...
Maltysen
Außerdem können Sie die Ausgabe mit,+JK-JK
Maltysen 28.04.15
@Maltysen Beides behoben. Vielen Dank!
Kirbyfan64sos
@orlp Ich hatte keine Ahnung yund habe es vergessen Z. Fest; Vielen Dank!
Kirbyfan64sos
6

Julia, 48 Bytes

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

Dies verwendet den Algorithmus der Methode 2, wie die meisten bisherigen Antworten. Es erstellt eine Lambda-Funktion, die eine Ganzzahleingabe akzeptiert und ein nx 2-Array zurückgibt. Um es zu nennen, geben Sie ihm einen Namen, z f=n->....

Ungolfed + Erklärung:

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

Mir gefällt wirklich, wie die Visualisierungen aussehen, also werde ich eine einfügen. Es ist das Ergebnis von f(1000).

Kreis

Alex A.
quelle
5

Pyth, 22 Bytes

Ein Port der C ++ Antwort. Ich hatte noch eine 23-Byte-Lösung (jetzt 22!), Aber es war fast eine Kopie von @ kirbyfan64sos 'Pyth-Antwort mit Optimierungen, also musste ich ein wenig über den Tellerrand hinaus denken und kreativ (ab) den Fold-Operator verwenden.

m,-Fdsdm,y*.nZOZ.tOZ4Q

Beachten Sie, dass dies derzeit aufgrund eines Fehlers im Fold-Operator nach der Einführung von nicht funktioniert reduce2. Ich stelle eine Pull-Anfrage.

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

Aus Referenzgründen war dies meine andere Lösung, die auf die gleiche Weise funktioniert: VQKy*.nZOZJ.tOZ4,+KJ-KJ

Maltysen
quelle
Du hast meinen Benutzernamen falsch geschrieben ... :(
kirbyfan64sos
@ kirbyfan64sos derp. Sorry;)
Maltysen
4

IDL, 65 Bytes

Offensichtlich ist dies derselbe Algorithmus wie @rcrmn, obwohl ich ihn unabhängig abgeleitet habe, bevor ich ihre Antwort gelesen habe.

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

Die IDL-Zufallsfunktion verwendet den Mersenne-Twister mit einer Periode von 2 19937 -1.

BEARBEITEN: Ich habe 1000 Akkorde über den obigen Visualizer gespielt. Hier ist ein Screenshot des Ergebnisses:

IDL Bertrand

sirpercival
quelle
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<<';';}}

Dies ist also eine direkte Implementierung des richtigen Algorithmus von der Wikipedia-Seite. Das Hauptproblem beim Golfen sind die ach so verdammt langen Namen, die die Klassen der Zufallsgeneratoren haben. Aber im Gegensatz zum guten alten Rand ist es zumindest richtig gleichmäßig.

Erläuterung:

#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
quelle
1
Dieser Faktor M_PI_2sieht verdächtig aus. Ich denke, es sollte stattdessen 1 sein.
Anatolyg
Ja, ganz richtig, ich werde es jetzt reparieren! Vielen Dank!
Lorlork
4

APL, 46 Bytes

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

Mein erstes APL-Programm überhaupt! Sicherlich kann es stark verbessert werden (da mein allgemeines Verständnis von APL fehlt), also wären alle Vorschläge fantastisch. Dadurch wird eine Funktion erstellt, fdie eine Ganzzahl als Eingabe verwendet, die Akkordpunktpaare nach Methode 2 berechnet und jedes Paar durch eine neue Linie getrennt ausgibt.

Sie können es online ausprobieren !

Erläuterung:

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

Hinweis: Meine vorherige 19-Byte-Lösung war ungültig, da sie (x, y) und nicht (x + y, xy) zurückgab. Traurigkeit gibt es zuhauf.

Alex A.
quelle
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));}};

Grundlegende Implementierung in Java. Verwendung als Lambda-Ausdruck.

Anwendungsbeispiel

Die Nummer eins
quelle
Können Sie die Größe nicht reduzieren, indem Sie sie Mathirgendwo aufbewahren? Oder so? (Ich bin kein Java-Programmierer)
Ismael Miguel
@IsmaelMiguel Das würde 2 zusätzliche Zeichen kosten.
TheNumberOne
Entschuldigung: / Es ist verlockend zu versuchen, die Anzahl der MathShows zu reduzieren . Was sagt das Meta über die Verwendung eines Codes zur Generierung eines anderen Codes zur Behebung des Problems?
Ismael Miguel
2
@IsmaelMiguel Das ist faires Spiel, obwohl ich mich wundern werde, wenn Sie tatsächlich besser im Metagolf als im Golfen sind.
Martin Ender
3

Ruby, 72 Bytes

Mein erster Golf hier! Ich habe den gleichen Code wie alle anderen benutzt, ich hoffe das ist okay

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

Java, 115 123

Dies ist im Grunde das gleiche wie bei den meisten anderen, aber ich benötige einen Java-Score für dieses Loch.

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

1000 Beispielakkorde sind im Pastebin zu finden , hier sind die ersten fünf aus einem Lauf:

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

CJam, 24 22 Bytes

Ähnlich wie bei anderen Algorithmen ist hier eine Version in CJam.

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

Eine Eingabe von 1000 ergibt eine Verteilung wie:

Bildbeschreibung hier eingeben

Wie es funktioniert

Der Algorithmus ist einfach 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

Aktualisieren : 2 Bytes gespart dank Martin!

Probieren Sie es hier aus

Optimierer
quelle
1

Python 3, 144 117 Bytes

(Danke an Blckknght für das lambda Zeiger)

Verwenden Sie die gleiche Methode wie andere:

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

Aus der Python-Dokumentation:

Python verwendet den Mersenne Twister als Kerngenerator. Es produziert 53-Bit-Präzisions-Floats und hat eine Periode von 2 19937 -1.

Ausgabe

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

Und so weiter.

Visualisierung

Visualisierung

Zach Gates
quelle
Sie können ungefähr 20 Bytes einsparen, wenn Sie ein Lambda für die Funktion verwenden und ein Listenverständnis (mit einem inneren Generatorausdruck) zurückgeben:f=lambda n:[(x,x+2*m.acos(r()))for x in(2*m.pi*r()for _ in range(n))]
Blckknght
Ah, ich hatte ursprünglich einen Lambda. Ich habe wohl nicht daran gedacht, das Listenverständnis zu verdoppeln. Vielen Dank! @Blckknght
Zach Gates
Kann durch Fummeln mit den Importen auf 109 Byte verkürzt werden: tio.run/#python2
Triggernometry
1

Perl, 60

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

R, 60 56 53 49 Bytes

Weitere 4 Bytes dank @JayCe und der Umwandlung in eine Funktion.

Verwenden Sie die gleiche Grundformel wie die anderen. R verwendet standardmäßig die Mersenne-Twister-Methode, andere können jedoch festgelegt werden. Gibt eine durch Leerzeichen getrennte Liste aus.

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

Probieren Sie es online!

MickyT
quelle
Hallo Micky, du kannst 4 Bytes speichern, indem du es zu einer Funktion machst und nicht x definierst.
JayCe
@ JayCe, das ist viel besser, danke
MickyT
0

SmileBASIC, 62 Bytes

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