Happy Pi Day allerseits! Ohne jeden Grund versuche ich, einen Monte-Carlo-Schätzer für Pi zu konstruieren, der so kurz wie möglich ist. Können wir eine erstellen, die in einen Tweet passt?
Um das zu verdeutlichen, denke ich an den typischen Ansatz, zufällige Punkte aus dem Einheitsquadrat zu ziehen und das Verhältnis zu berechnen, das in den Einheitskreis fällt. Die Anzahl der Samples kann fest codiert sein oder nicht. Wenn Sie sie fest codieren, müssen Sie mindestens 1000 Beispiele verwenden. Das Ergebnis kann als Gleitkomma-, Festkomma- oder rationale Zahl zurückgegeben oder gedruckt werden.
Keine Triggerfunktionen oder Pi-Konstanten müssen ein Monte-Carlo-Ansatz sein.
Dies ist Codegolf, daher gewinnt die kürzeste Übermittlung (in Bytes).
code-golf
random
pi
approximation
keegan
quelle
quelle
((0..4e9).map{rand**2+rand**2<1}.to_s.sub(/./,"$1.")
map
Ihnen das nicht eine Reihe vontrue
undfalse
?.filter{...}.size
sollte aber funktionieren.Antworten:
80386 Maschinencode,
4038 BytesHexdump des Codes:
So erhalten Sie diesen Code (aus der Assemblersprache):
Dies ist eine Funktion, die die MS-
fastcall
Aufrufkonvention verwendet (Anzahl der Iterationen wird im Register übergebenecx
). Es gibt das Ergebnis imst
Register zurück.Unterhaltsame Dinge über diesen Code:
rdrand
- Nur 3 Bytes, um eine Zufallszahl zu generieren!D
) mit dem quadratischen Radius (2^32
) wird automatisch durchgeführt - das Übertragsflag enthält das Ergebnis.quelle
eax
; dermul
Befehl multipliziert es mit sich selbst und setzt den hohen Anteil einedx
; Der untere Teil voneax
wird verworfen.Matlab / Octave, 27 Bytes
Ich weiß, dass es bereits eine Matlab / Octave-Antwort gibt, aber ich habe meinen eigenen Ansatz ausprobiert. Ich habe die Tatsache benutzt, dass das Integral
4/(1+x^2)
zwischen 0 und 1 pi ist.quelle
R, 40 (oder 28 oder 24 mit anderen Methoden)
Python 2, 56
Eine andere Python-Version, wenn dies erlaubt ist, aber ähnlich wie Matlab / Octave:
quelle
Mathematica,
424039 Bytes (oder 31/29?)Ich habe drei Lösungen alle bei 42 Bytes:
Dies sind alle unbenannten Funktionen, die die Anzahl der Abtastwerte
n
messen und eine rationale Approximation von π zurückgeben. Zunächst erzeugen sie allen
Punkte im Einheitsquadrat im positiven Quadranten. Dann bestimmen sie die Anzahl der Abtastwerte, die innerhalb des Einheitskreises liegen, und dividieren dann durch die Anzahl der Abtastwerte und multiplizieren mit4
. Der einzige Unterschied besteht darin, wie sie die Anzahl der Proben innerhalb des Einheitskreises bestimmen:Count
mit der Bedingung, dassNorm[p] < 1
.1
und rundet dann auf. Dies dreht Zahlen innerhalb des Einheitenkreises nach1
und solche außerhalb nach0
. Danach fasse ich sie alle zusammenTr
.1.5
, sodass ich sieRound
anstelle von verwenden kannCeiling
.Aaaaaund als ich das aufschrieb , kam mir der Gedanke , dass es tatsächlich eine kürzere Lösung gibt, wenn ich einfach subtrahiere
2
und dann benutzeFloor
:Oder speichern Sie ein anderes Byte mit den Unicode-Operatoren für Fußböden oder Decken:
Beachten Sie, dass die drei Runden-basierten Lösungen können auch mit geschrieben werden
Mean
stattTr
und ohne der/#
wieder für das gleiche Bytes.Wenn andere Monte-Carlo-basierte Ansätze in Ordnung sind (insbesondere der von Peter gewählte), kann ich 31 Bytes ausführen, indem ich das Integral von oder 29 unter Verwendung des Integrals von schätze . Diese Zeit wird als Gleitkommazahl angegeben:
√(1-x2)
1/(1+x2)
quelle
CJam,
27 2322 oder 20 Bytes2 Bytes gespart dank Runner112, 1 Byte gespart dank Sp3000
Es wird die Iterationszahl von STDIN als Eingabe verwendet.
Das ist so einfach wie es nur geht. Dies sind die wichtigsten Schritte:
Code-Erweiterung :
Probieren Sie es hier online aus
Wenn der Durchschnittswert von
1/(1+x^2)
auch als Monte Carlo betrachtet wird, kann dies in 20 Bytes erfolgen:Probieren Sie es hier aus
quelle
1dmr
anstelle vonKmrK/
und überprüfe, ob die Summe der Quadrate größer als 1 miti
anstelle von ist1>
(ich fand das besonders clever) .i
Trick ist wirklich ordentlich! Und verdammt die fehlende Dokumentation für1dmr
Python 2,
7775 BytesVerwendet 4000 Samples, um Bytes zu speichern
1e3
.quelle
...*8000;print a/2e3
.Commodore 64 Basic, 45 Bytes
PETSCII-Substitutionen:
─
=SHIFT+E
,/
=SHIFT+N
,┌
=SHIFT+O
Erzeugt 1000 Punkte im ersten Quadranten. Addiert für jedes die Wahrheit von "x ^ 2 + y ^ 2 <1" zu einer laufenden Zählung und dividiert dann die Zählung durch 250, um zu erhalten
pi
. (Das Vorhandensein eines Minuszeichens liegt daran, dass auf dem C64 "true" = -1 ist.)quelle
(1)
das?/
ist nicht das Teilungssymbol, sondern das Zeichen, das durch EingebenSHIFT+N
auf einer Commodore 64-Tastatur erzeugt wird.R/(1)
ist die Abkürzungsform fürRND(1)
, dh. msgstr "eine Zufallszahl zwischen 0 und 1 mit dem aktuellen RNG - Startwert erzeugen".J, 17 Bytes
Berechnet den Mittelwert der
40000
Abtastwerte der Funktion4*sqrt(1-sqr(x))
im Bereich[0,1]
.Handlich
0 o.x
kehrt zurücksqrt(1-sqr(x))
.quelle
> <> (Fisch) , 114 Bytes
Jetzt hat> <> keinen eingebauten Zufallsgenerator. Es hat jedoch eine Funktion, die den Zeiger in eine zufällige Richtung sendet. Der Zufallsgenerator in meinem Code:
Grundsätzlich werden Zufallsbits generiert, aus denen eine Binärzahl besteht, und diese Zufallsbinärzahl wird dann in eine Dezimalzahl konvertiert.
Der Rest ist nur die regelmäßigen Punkte in der quadratischen Annäherung.
Verwendung: Wenn Sie den Code ausführen, müssen Sie sicherstellen, dass der Stack (-v im Python-Interpreter) beispielsweise mit der Anzahl der Samples gefüllt ist
kehrt zurück
quelle
Matlab oder Octave 29 Bytes (danke an flawr!)
(Ich bin mir nicht ganz sicher, ob <1 in Ordnung ist. Ich habe gelesen, dass es <= 1 sein sollte. Aber wie groß ist die Wahrscheinlichkeit, genau 1 zu ziehen ...)
Matlab oder Octave 31 Bytes
quelle
mean(sum(rand(2,4e6).^2)<1)*4
.Java, 108 Bytes
Viertausend Iterationen, die jeweils 0,001 addieren, wenn sich der Punkt innerhalb des Einheitskreises befindet. Ziemlich einfaches Zeug.
Hinweis: Ja, ich weiß, dass ich durch Ändern
π
eines Einzelbytezeichens vier Bytes verlieren kann. Ich mag es so.quelle
Javascript: 62 Bytes
Ich habe die vorherige (jetzt gelöschte) Javascript-Antwort verwendet und 5 Bytes rasiert.
quelle
GolfScript (34 Zeichen)
Online-Demo
Hier wird ein fester Punkt verwendet, da GS eigentlich keinen Fließkommawert hat. Die Verwendung von Fixpunkten wird leicht missbraucht. Wenn Sie also die Iterationszahl ändern möchten, stellen Sie sicher, dass es sich um eine doppelte Zehnerpotenz handelt.
Gutschrift an xnor für die jeweils angewandte Monte-Carlo-Methode.
quelle
Python 2,
908581 Byteskehrt
3.14120037157
zum Beispiel zurück. Die Stichprobenanzahl beträgt 4782969 (9 ^ 7). Sie können mit 9 ^ 9 ein besseres pi erzielen, aber Sie müssen geduldig sein.quelle
range(9**7)
mit[0]*9**7
oder etwas, da Sie nicht verwendeni
. Und die Liste ist nicht zu lang, um auf Speicherprobleme zu stoßen.range()
aber ich hatte diesen Trick völlig vergessen.[0]9**7
, dass die Syntax nicht gültig ist.Ruby, 39 Bytes
Einer der Höhepunkte ist, dass dieser die
8e5
Notation verwenden kann, wodurch er auf ~ 8e9 Samples in derselben Programmbytezahl erweiterbar ist.quelle
Perl 6 , 33 Bytes
Probieren Sie es online!
Dies ist eine Funktion, die die Anzahl der Samples als Argument verwendet.
quelle
Scala,
877766 Bytesquelle
1000
mit8000
und250d
mit ersetzen,2e4
sparen Sie ein Byte und erhöhen die Anzahl der Samples um den Faktor 8.Pure Bash, 65 Bytes
Nimmt einen einzelnen Befehlszeilenparameter an, der mit 4 multipliziert wird, um die Anzahl der Stichproben zu erhalten. Bash-Arithmetik ist nur eine Ganzzahl, daher wird eine Rationale ausgegeben. Dies kann
bc -l
für die Enddivision weitergeleitet werden:quelle
Joe ,
20 bis19 BytesHinweis: Diese Antwort ist nicht konkurrierend, da Version 0.1.2, die die Zufälligkeit erhöht hat, nach dieser Herausforderung veröffentlicht wurde.
Benannte Funktion F:
Unbenannte Funktion:
Beide verwenden die Anzahl der Stichproben als Argument und geben das Ergebnis zurück. Wie arbeiten Sie?
Beispiel läuft:
quelle
dc, 59 zeichen (whitespace wird ignoriert)
Ich habe dies auf Plan 9 und OpenBSD getestet, also stelle ich mir vor, dass es unter Linux (GNU?) Funktionieren wird
dc
.Erklärung nach Zeile:
i
wenn 1 größer ist als die Summe der Quadrate] im Registeru
.x
im Register [Inkrementiere das Register um 1]i
.u
inkrementierenm
und dann Register ausführen,z
wenn Registerm
größer als Register istn
]z
.Stellen Sie die Skala auf 5 Dezimalstellen ein.
z
.x
(die Anzahl der Treffer) durch das Registern
(die Anzahl der Punkte), multiplizieren Sie das Ergebnis mit 4 und drucken Sie es aus.Ich habe jedoch betrogen:
Das Programm benötigt eine Zufallsmenge zwischen 0 und 1.
Verwendung:
Testlauf:
Jetzt mit weniger Betrug (100 Bytes)
Jemand wies darauf hin, dass ich ein einfaches Prng einschließen könnte.
http://en.wikipedia.org/wiki/RANDU
Ungolfed
Testlauf:
quelle
Pyth, 19
Geben Sie die gewünschte Anzahl von Iterationen als Eingabe ein.
Demonstration
Da Pyth keine "Random Floating Number" -Funktion hat, musste ich improvisieren. Das Programm wählt zwei zufällige positive ganze Zahlen aus, die kleiner sind als die Eingabe, Quadrate, Summen und die mit der Eingabe im Quadrat verglichen werden. Dies wurde so oft durchgeführt, wie es der Eingabe entsprach, dann wird das Ergebnis mit 4 multipliziert und durch die Eingabe dividiert.
In ähnlichen Nachrichten werde ich in Kürze eine zufällige Gleitkommaoperation zu Pyth hinzufügen. Dieses Programm verwendet diese Funktion jedoch nicht.
Wenn wir interpretieren "Das Ergebnis kann als Gleitkomma, Festkomma oder rationale Zahl zurückgegeben oder gedruckt werden." großzügig, dann sollte das Drucken des Zählers und des Nenners der resultierenden Fraktion ausreichen. In diesem Fall:
Pyth, 18
Dies ist ein identisches Programm, bei dem die Gleitkommadivisionsoperation (
c
) entfernt wurde.quelle
Julia, 37 Bytes
Die Anzahl der Stichproben beträgt 65536 (= 4 ^ 8).
Eine etwas längere Variante: Eine Funktion mit der Anzahl der Samples
s
als einziges Argument:quelle
C 130 Bytes
Ungolfed:
quelle
f()
. Welchen Compiler hast du benutzt? Siehe tio.run/##Pc49C4JAHIDx3U9xGMG9ZdYgwWkgtNbQ1BZ6L/UHO8M07hA/…Eigentlich 14 Bytes (nicht konkurrierend)
Probieren Sie es online!
Diese Lösung ist nicht konkurrierend, da die Sprache die Herausforderung postdatiert. Die Anzahl der Samples wird als Eingabe angegeben (nicht fest codiert).
Erläuterung:
quelle
Schläger 63 Bytes
Mit der Methode der R-Sprache Antwort von @Matt:
Ungolfed:
Testen:
Leistung (Bruchteil):
Als Dezimalzahl:
quelle
Fortran (gfortran) ,
8483 BytesProbieren Sie es online!
Dieser Code ist sehr schlecht geschrieben. Es schlägt fehl, wenn gfortran entscheidet, eine Variable
A
mit einem anderen Wert als 0 zu initialisieren (was ungefähr 50% der Kompilierungen entspricht), und wennA
es mit 0 initialisiert wird, wird immer dieselbe zufällige Sequenz für den angegebenen Startwert generiert. Dann wird immer der gleiche Wert für Pi ausgegeben.Dies ist ein viel besseres Programm:
Fortran (GFortran) ,
100 bis99 BytesProbieren Sie es online!
(Ein Byte in jeder Version gespeichert; danke Penguino).
quelle
Japt , 26 oder 18 Bytes
Probieren Sie es online!
Analog zu Optimizers Antwort , hauptsächlich um Japt zu lernen.
Legt die Anzahl der auszuführenden Iterationen als implizite Eingabe fest
U
.Wenn dies
1/(1+x^2)
erlaubt ist (anstelle von zwei getrennten Zufällen), können wir mit derselben Logik 18 Bytes erreichen.quelle
Mh
die Hypotenuse berechnen lassen , anstatt sie selbst zu machen ;-) Sie könnenx
auch die Summe eines Arrays verwenden, anstatt sie durch Addition zu reduzieren:o x@MhMr Mr)<1Ã*4/U
Mh
, danke! Deine zwei zufällige Antwort ist fast so kurz wie meine Antwort mit nur einer zufälligen, das ist ziemlich cool. Ich werdex
bedenken, ich neige dazu, beim Golfspiel viel Reduktion zu verwenden, daher ist dies sehr praktisch.F #, 149 Bytes
Probieren Sie es online!
Soweit ich das beurteilen kann, ist es für diese Art der Summierung in F # kürzer, ein Array von Zahlen zu erstellen und die
Seq.sumBy
Methode zu verwenden, als einenfor..to..do
Block zu verwenden.Mit diesem Code wird eine Auflistung von Gleitkommazahlen von 1 bis erstellt
s
, die Funktionfun x->...
für die Anzahl der Elemente in der Auflistung ausgeführt und das Ergebnis summiert. Es gibts
Elemente in der Sammlung, so dass der Zufallstests
mal durchgeführt wird. Die tatsächlichen Zahlen in der Sammlung werden ignoriert (fun x->
aberx
nicht verwendet).Dies bedeutet auch, dass die Anwendung zuerst das Array erstellen und füllen und dann darüber iterieren muss. Es ist also wahrscheinlich doppelt so langsam wie eine
for..to..do
Schleife. Und bei der Array-Erstellung liegt die Speichernutzung im Bereich von O (f ** k)!Für den eigentlichen Test selbst
if then else
berechnet er anstelle einer Anweisung den Abstand (q()+q()|>Math.Sqrt
) und rundet ihn abMath.Floor
. Wenn der Abstand innerhalb des Kreises liegt, wird er auf 0 abgerundet. Wenn der Abstand außerhalb des Kreises liegt, wird er auf 1 abgerundetSeq.sumBy
Methode addiert dann diese Ergebnisse.Beachten Sie dann, dass
Seq.sumBy
die Summe nicht die Punkte ist innerhalb des Kreises , sondern die Punkte außerhalb des Kreises . Also für das Ergebnis braucht ess
(unsere Stichprobengröße) und subtrahiert die Summe davon.Es scheint auch, dass das Verwenden einer Stichprobengröße als Parameter kürzer ist als das Festcodieren des Werts. Also betrüge ich ein bisschen ...
quelle
Haskell,
11611411096 BytesDa der Umgang mit
import System.Random; r=randoms(mkStdGen 2)
zu vielen wertvollen Bytes zu viel Zeit in Anspruch nimmt, erstelle ich mit dem linearen Kongruenzgenerator eine unendliche Liste von Zufallszahlen, von denen manche sagen, dass sie fast kryptografisch stark sind:x↦x*9+1 mod 8^9
, die von der Hull-Dobell Satz den gesamten Zeitraum hat8^9
.g
Ausbeuten4
wenn der Zufallszahlenpunkt innerhalb des Kreises für Zufallszahlenpaare liegt,[0..8^9-1]
da dies eine Multiplikation in der verwendeten Formel eliminiert.Verwendung:
Probieren Sie es online!
quelle
Perl 5, 34 Bytes
Die Anzahl der Proben wird von stdin genommen. Benötigt
-p
.Funktioniert weil:
Probieren Sie es online!
quelle