Pi berekenen met random

[tempelier]

Het is op de computer vrij eenvoudig om een schatting van de grootte van Pi te maken door middel van toeval.
 
Het principe is kinderlijk eenvoudig:
 
1. Neem een vierkant met daar binnenin een cirkel. (met bekende maten)
 
2. Deel het vierkant in in punten. (dus ook de cirkel)
 
3. Laat met een (geschikte) random generator heel veel punten in dat vierkant aanwijzen.
 
4. Uit de verhouding van het aantal aangewezen punten binnen het vierkant en binnen de cirkel laat zich nu Pi berekenen.
 
======
 
Dit is al een heel oud trucje en dus niet van mij.
 
Onlangs echter vroeg ik me af hoe het zit met de betrouwbaarheid van de gevonden waarde.
Die hangt natuurlijk af van: het aantal punten , de afmetingen , het aantal aanwijzingen.
 
Het lukt met niet dat naar een bruikbaar iets om te zetten.
Het ingewikkelde komt omdat de punten die worden aangewezen vierkanten vormen waar de cirkel als het ware tussendoor loopt.
Dus veel punten van de cirkel behoren niet tot punten die kunnen worden aangewezen.
Intuïtief zou ik zeggen dat bovenstaande een soort bovengrens aan de nauwkeurigheid legt los vaan het aantal aanwijzingen.
 
Waarschijnlijk zie ik iets eenvoudigs over de kop. (wat me wel vaker gebeurd)
 
PS.
De methode is ietwat ingewikkelder dan ik heb opgeschreven, maar dat heb ik voor de leesbaarheid weggelaten.

[Professor Puntje]

Bestaat de cirkel "volgens de computer" dan eigenlijk uit een op de echte cirkel liggende rondlopende keten van vierkantjes? 
 
Wat doet de computer vervolgens met punten die op zo'n vierkantje vallen waar de echte cirkel doorheen loopt? Gelden die als binnen, buiten of op de cirkel?
 
 

[tempelier]

Het middelpunt is bekend dus ook welke punten binnen en buiten de cirkel vallen.
Het handigste is om de punten die precies op de cirkel vallen niet mee te tellen.
 
De rand van wat geteld wordt als binnen de cirkel is dus inderdaad iets trapachtigs.

[Professor Puntje]

Dan zou je dus voor zéér grote aantallen punten niet de verhouding van de cirkeloppervlakte en de oppervlakte van het omgeschreven vierkant vinden maar de verhouding tussen de oppervlakte van het ingeschreven trapjesoppervlak van de cirkel en het omgeschreven vierkant van de cirkel. De fout die je maakt is dan ongeveer de helft van de oppervlakte van de op de cirkel liggende rondlopende keten van vierkantjes.

Dit uiteraard nog afgezien van beperkingen in het aantal te berekenen decimalen van pi dat de computer maximaal aan kan.

[tempelier]

Aan zoiets heb ik ook gedacht, maar het is lastiger dan het lijkt om het echt gedegen om te zetten.
 
Ook loop je dan het gevaar gewoon een andere methode te gebruiken, want met het uit tellen van de vierkantjes ben je min of min als klaar.
Want het gaat dan op een soort Riemansommen lijken wat net niet de bedoeling was.

[klazon]

Ik heb niet goed in beeld hoe deze methode werkt. Kan je het met een plaatje verduidelijken?

[Emveedee]

Waarom je je cirkel in punten verdeeld begrijp ik niet. Ik ken de methode als volgt:

• Genereer paren van willekeurige getallen tussen 0 en 1.
• Tel alle paren die je genereert, en alle paren waarvan de som van de kwadraten <= 1
• De verhouding tussen die twee getallen is nu (ongeveer) pi/4.

Natuurlijk ben je gelimiteerd door de precisie van je variabelen, in het geval van een double (64 bits) heb je al 15 decimalen nauwkeurigheid. Ik heb even geen concrete berekening ervoor, maar ik denk dat voordat die precisie roet in het eten gooit, je echt gigantisch veel paren moet trekken.
 
 
Hier heb ik in python een voorbeeldje gemaakt: http://bit.ly/2CfncFv
Als je klikt op run bovenin, komt rechts de output van het script te staan.
 
Deze methode van benaderingen berekenen m.b.v. willekeurige getallen heet overigens Monte Carlo. Wellicht dat dat helpt bij het zoeken.

[tempelier]

Ik heb dat gedaan om het wat visueler te maken voor het overige is de methode die je gebruikt in principe het zelfde.
 
Helaas heb ik niet gevonden wat de nauwkeurigheid is en daar ging het me om.
 
Maar toch bedankt voor het meedenken.

[Professor Puntje]

Over de absolute nauwkeurigheid kun je met een toevalsmethode ook niets zeggen omdat het in principe mogelijk blijft dat je (door aanhoudend ongunstig vallende punten) een volledig foute uitkomst vindt. Is het je om de kans te doen dat de uitkomst binnen zekere gekozen grenzen juist is?

[klazon]

Ik heb dat gedaan om het wat visueler te maken....

Als je het echt visueel wil maken, laat dan een plaatje zien. Want ik snap nog steeds niet wat je aan het doen bent.

[Emveedee]

mc_pi 962 keer bekeken

 
Je kiest willekeurig punten in een vierkant. Door te tellen hoeveel punten er op afstand <= 1 vanaf de oorsprong liggen (in het rood), kun je een benadering van de oppervlakte van een cirkel berekenen (en dus van pi).

[klazon]

Oke, nu is het me duidelijk. Maar waarom worden die punten willekeurig gekozen? Ik zou eerder kiezen voor punten in een regelmatig vierkantspatroon.

[tempelier]

Oke, nu is het me duidelijk. Maar waarom worden die punten willekeurig gekozen? Ik zou eerder kiezen voor punten in een regelmatig vierkantspatroon.

De mogelijke punten zitten in een vierkant patroon. (heel dicht op elkaar)
 
De aangewezen punten zullen niet al die punten bevatten, vooral als er niet te veel punten worden aangewezen.

[klazon]

Nu wordt het weer geheimtaal. Of juist een open deur. Logisch, als je niet al te veel punten aanwijst zal je niet alle punten aanwijzen.

[tempelier]

Nu wordt het weer geheimtaal. Of juist een open deur. Logisch, als je niet al te veel punten aanwijst zal je niet alle punten aanwijzen.

Dan krijg je het patroon als in het tekeningetje.
 
Natuurlijk kun je de computer laten doordraaien dan zal bijna elke punt wel aangewezen worden en een hoop punten meerdere malen.
Dan lijkt het vlak geheel gevuld want in het plaatje is de pixel afstand de kleinste die te tekenen is.