Pi Annäherung mittels gerasterter Monte-Carlo Simulation nach Dor Fuchs

ThoralfAsmussen · 2. Juni 2023

Hier ist mal was, was auch in Interessantes/Links passen würde, aber vielleicht - je nachdem, ob jemand/viele was basteln mag/mögen - auch hier schön hinpaßt.

Ist also als Idee/Vorschlag zu sehen. Sicher auch geeignet für Programmierwettbewerbe o.ä.

Eine der schönen Varianten PI zu bestimmen, ist ja wahrscheinlich hier doch bißchen sowas wie "allgemein bekannt" - oder wenigstens hat man davon gehört.

Gemeint ist die Monte Carlo Methode. ( WikiP , wo das natürlich kompliziert benannt ist ) ( eine andere Pedia ) ( eine lustige in-Browser Simulation davon )

Hier erklärt ein Mathe Youtuber ein Verfahren, was doch ein klein bißchen anders funktioniert, als die sonst üblichen Varianten ( bekannt aus "Happy Computer", "64'er", "Schneider CPC International" oder "HC" ).

Und: irgendwie ist das so schön "schräg", daß sich das eigentlich bestens für 8Bit Homecomputer eignen sollte. Denn die sonst nötigen Fließkommaberechnungen, werden hier einfach durch ein weiteres Hineinzoomen ins Feld und einen weiteren Würfelwurf ersetzt. Und das dann benötigte Quadrieren großer Zahlen läßt sich ja evtl. sogar noch durch eine schnelle Variante ersetzen, so daß man dann komplett mit Fixpunktzahlen auskäme.

Einfach mal ins Video schauen.

https://www.youtube.com/watch?v=wlYWZMtXJR4

Wie man π mit einem Würfel bestimmen kann (Pi Day 2023)

Vielleicht wirds ja mal ein neuer Benchmark (zumindest für kleine Rechner), und der Channel Betreiber erlangt so ewigen Ruhm als Mathematiker.

detlef · 3. Juni 2023

Zitat von ThoralfAsmussen

Eine der schönen Varianten PI zu bestimmen, ist ja wahrscheinlich hier doch bißchen sowas wie "allgemein bekannt" - oder wenigstens hat man davon gehört.
Gemeint ist die Monte Carlo Methode. ( WikiP , wo das natürlich kompliziert benannt ist ) ( eine andere Pedia ) ( eine lustige in-Browser Simulation davon )

Das habe ich "damals" mal im Informatikunterricht auf dem PET programmiert.

ThoralfAsmussen · 3. Juni 2023

Sag ich doch ... sollte bekannt sein.

ABER: Du hast ziemlich sicher nicht so ein spannendes / interessantes Rasterizing da drin gehabt. Üblicher wäre wahrscheinlich ein (X,Y) Pärchen per Zufall zu bestimmen und ann per ArcTangens die Streckenlänge der anderen noch fehlenden Dreiecksseite. Wenn die kleiner als der Radius des Viertelkreises ist, liegt es innerhalb, sonst außerhalb.

Martin Hepperle · 4. Juni 2023

... na, na, na, wer wird denn hier den ARCTAN verwenden! Das wäre ja schon Betrug - in FORTRAN ist es üblich, PI=4.0*ATAN(1.0) zu definieren, da braucht es dann keinen Kasinobesuch in Monte Sonstwo mehr.

Man muss sich hier schon auf Addition und Multiplikation beschränken

tofro · 4. Juni 2023

Unsinn

tofro · 4. Juni 2023

Zitat von Martin Hepperle

Man muss sich hier schon auf Addition und Multiplikation beschränken

Und deshalb darf zum "Ist-im-Kreis-Test" gerne auch der alte Herr Pythagoras herhalten... Macht man's geschickt und legt den Kreisradius mit "1" fest, ist das auch nicht besonders schwer zu rechnen...

guidol · 4. Juni 2023

Zitat von ThoralfAsmussen

Vielleicht wirds ja mal ein neuer Benchmark (zumindest für kleine Rechner),
und der Channel Betreiber erlangt so ewigen Ruhm als Mathematiker.

ChatGPT hat dazu folegnden GW-BASIC-Code ausgespukt (der so zu laufen scheint

Code

10 PRINT "MONTE CARLO PI BERECHNUNG"
20 PRINT "=========================="
30 PRINT
40 INPUT "Anzahl der Punkte: ", N
50 PRINT
60 RANDOMIZE TIMER
70 INSIDE = 0
80 FOR I = 1 TO N
90     X = RND(1)
100    Y = RND(1)
110    DISTANCE = SQR(X^2 + Y^2)
120    IF DISTANCE <= 1 THEN INSIDE = INSIDE + 1
130 NEXT I
140 PI = 4 * INSIDE / N
150 PRINT "Ergebnis: ", PI
160 PRINT
170 END

Alles anzeigen

Manchmal schafft das Programm - je nach Zufallszahlen - eine Naeherung auf 3.14 bei 10.000 Versuchen, manchmal braucht es dazu auch 40.000 Versuche

run

MONTE CARLO PI BERECHNUNG

==========================

Anzahl der Punkte: 40000

Ergebnis: 3.1424

ThoralfAsmussen · 4. Juni 2023

Ja, schick. Ganz klassisch - wenn man von dem Umstand absieht, daß das jemand geschrieben hat, der gerade erst den TuringTest bestanden hat; und es immer wieder faszinierend ist, was da aus dem Teil (ChatGPT) so rausfällt. Programmieren als Beruf ist gewissermaßen durch, das wird sich dann wandeln zu "Codedesigner", also jemand, der dem "Automaten" sagt, was das Programm können soll und evtl. was dabei einzuhalten ist.

(Man fragt sich ja wirklich, wo das herkommt und wie das geht ...)

Aber, es macht eben auch nur ganz klassisches Monte Carlo - der Witz am Video oben war aber gerade eben, daß das eben nicht so funktioniert, sondern, daß die Fläche gerastert wird, und nur wenn die Entscheidung für das zufällig gewählte Rasterfeld eindeutig ausfällt (INSIDE vs. NOT INSIDE), ist die Würfelrunde zu Ende. Ansonsten wird quasi in das ausgewählte Rasterfeld "hineingezoomt" und dafür noch einmal gewürfelt (und zwar wieder mit Raster).

Müßte man dem ChatGPT also erstmal vorher noch erklären ...

in der nächsten Ausbaustufe (und evtl. gibt es die schon) wird man dann sagen, daß er/sie/es sich mal das Video anschauen soll und ein dafür passendes Programm in GW BASIC bauen.

Zum (Arc)Tangens: ja zugegeben, ist wahrscheinlich ein bißchen albern an der Stelle; der Pythagoras ist da deutlich besser, durchaus auch im Sinne von anschaulicher.

ThoralfAsmussen · 4. Juni 2023

PS: ich frag mich nämlich eigentlich auch ein bißchen, ob das "so" überhaupt klappt. Irgendwie ist da ja eine implizite Annahme drin, daß er alle Rasterfelder, in die er "reinzoomt" wieder genauso behandeln kann, wie das ursprüngliche Feld (bzw. werden alle "Zoomfelder" gleich behandelt, egal wo sie liegen und wie die Kreislinie darin verläuft). Na ja.

Interessant ist aber mal das Vermengen von Rasterizing, Rekursion, Monte Carlo Ansatz und Binärem Ergebnis für jedes Zufallsfeld. Das Ganze bei Fehlen sämtlicher "teurer" Operationen wie Wurzeln oder Division oder ... haha ... Tangens.

Irgendwie hat das so vom Ansatz auch irgendwie eigenartige Überschneidungen mit solchen Grafikroutinen, etwa für Fills oder Tests auf Außenlinien.

Roland_t29 · 4. Juni 2023

Zitat von ThoralfAsmussen

PS: ich frag mich nämlich eigentlich auch ein bißchen, ob das "so" überhaupt klappt. Irgendwie ist da ja eine implizite Annahme drin, daß er alle Rasterfelder, in die er "reinzoomt" wieder genauso behandeln kann, wie das ursprüngliche Feld (bzw. werden alle "Zoomfelder" gleich behandelt, egal wo sie liegen und wie die Kreislinie darin verläuft). Na ja.

Hallo ThoralfAsmussen : ich habe mir das Video genau angesehen, das Verfahren ist cool und das klappt so. Da steckt keine weitere implizite Annahme drin. Wenn er ein Kästchen als auf dem Kreis liegend findet, multipliziert er die linke untere Koordinate (x_a, y_a) jeweils mit 6 und addiert (getrennt) einen Wurf (w₁, w₂) dazu. Er unterteilt also das noch nicht entschiedene Quadrat in wieder 6*6 Teile, vergleicht jetzt aber (6*x_a + w₁)² + (6*y_a + w₂) mit (6*6)². Er skaliert also in dem Fall auch die Abstandsbedingung mit 6.

Das einzige Problem (das er auch anspricht) ist, dass bei wiederholtem Reinzoomen der Zahlenbereich der Integervariablen schnell überschritten wird:

6⁶ geht gerade noch mit 16 Bit, bei 12mal Reinzoomen ist mit 32 Bit Schluss usw. Das sind Fälle, die selten sind, aber bei Monte-Carlo wegen der hohen Zahl der Versuche halt doch vorkommen können.

Roland

detlef · 4. Juni 2023

Zitat von ThoralfAsmussen

ich frag mich nämlich eigentlich auch ein bißchen, ob das "so" überhaupt klappt.

Programmieren und ausprobieren. Hab ich immer so gemacht, wenn ich einen Algoritmus nicht verstanden habe bzw. nicht wusste, ob er funktioniert.

detlef · 4. Juni 2023

Zitat von guidol

ChatGPT hat dazu folegnden GW-BASIC-Code ausgespukt (der so zu laufen scheint

Das war wohl auch die Version, die ich damals in Information programmiert habe. Jedenfalls waren es nur ein paar Zeilen.

Roland_t29 · 4. Juni 2023

Zitat von detlef

Zitat von ThoralfAsmussen

ich frag mich nämlich eigentlich auch ein bißchen, ob das "so" überhaupt klappt.

Programmieren und ausprobieren. Hab ich immer so gemacht, wenn ich einen Algoritmus nicht verstanden habe bzw. nicht wusste, ob er funktioniert.

Hi Detlef, rustikales Ausprobieren ersetzt keinen Beweis der Konvergenz Da es ein Monte Carlo Verfahren ist, reicht es nicht aus, dass zB. nach 10.000 Versuchen irgendwas in der Nähe von pi rauskommt (Klugscheißmodus aus).

Gruß

Roland

Roland_t29 · 4. Juni 2023

... und je länger ich nachdenke, so kommen doch Zweifel:

Beim klassischen MC-Ansatz ( 2 Zufallszahlen ziehen und mittels Pythagoras prüfen) ist die Kovergenz klar.

Wenn man bei dem Würfelansatz ein "Grenzfeld" trifft, wird ja sooft neu skaliert und wieder gewürfelt, bis eine Entscheidung fällt (was theoretisch lange dauern kann). Ich überschaue gerade nicht, ob das wiederholte Würfeln zur Klärung EINES Falles den Grenzwert verfälscht.

Roland