logo

Výpočet π pomocí simulace Monte Carlo

Když jsem byl na univerzitě, poprvé jsem se dozvěděl o simulaci Monte Carlo jako způsobu výpočtu π \pi π (pí). Jednoduchá – a přesto geniální – myšlenka za tímto konceptem mi prostě vyrazila dech. Počítat nekonečné číslo jako pí nezní pro většinu lidí jako zábava. Přesto mě nepřestává udivovat, když vidím, jak se číslo stále zpřesňuje. Abych si osvěžil staré vzpomínky, rozhodl jsem se implementovat interaktivní simulaci v React a TypeScript.

Let It Rain

Dovolte mi vysvětlit myšlenku simulace Monte Carlo analogií k dešti. Vezměte list papíru a nakreslete na něj jednotkový čtverec (jehož strany mají délku 1). Uvnitř tohoto čtverce nakreslete čtvrtkruh o poloměru 1. Bude to vypadat takto:

Nyní si představme, že na tento jednotkový čtverec prší s dokonalou náhodností. Kapky deště budou rovnoměrně rozmístěny na čtverci jednotky. Některé kapky deště budou ležet uvnitř čtvrtkruhu (tj. modré tečky) a některé budou ležet mimo něj (tj. červené tečky). Do čtvrtkruhu logicky dopadne mnohem více dešťových kapek než mimo něj. Takhle to vypadá s 1000 dešťovými kapkami:

Je zajímavé, že podíl dešťových kapek uvnitř čtvrtkruhu oproti celkovému počtu dešťových kapek se bude neustále měnit, jak budeme generovat další dešťové kapky. Je to dáno zákonem velkých čísel a tím, že dosahujeme stále lepší distribuce. Mějme tento zlomek na paměti, protože jej budeme potřebovat v dalším kroku.

Dejte mi matematiku

Stručně vysvětlím základní matematický princip. Na internetu je spousta dobrých článků pro podrobnější informace.
Metoda je založena na matematickém vzorci pro výpočet plochy jednotkové kružnice (tj. kružnice s poloměrem 1):

Jednotkovou kružnici rozřízneme na čtyři stejné segmenty. Odvozený čtvrtkruh (tj. modrá oblast) má stále poloměr 1 a jeho plocha je definována následujícím vzorcem:

Nyní je zajímavé, že čtvrtkruh dokonale zapadá do jednotkového čtverce (tj. červené oblasti) s délkou hrany 1. Víme, že jednotkový čtverec má obsah 1 × 1 1\times1 1×1 a čtvrtkruh se částečně překrývá s touto oblastí, jak je definována předchozím vzorcem pro A q u a r t e r A_{quarter} Akvart. Musíme předpokládat, že zlomek, do kterého se překrývá – a způsob, jak to udělat – je generováním náhodných bodů v rámci jednotkového čtverce (např. necháme pršet).

Tento zlomek lze definovat jako d r o p s    já n s já d e    t h e    q u a r t e r    c já r c l e t o t a l    n u m b e r    o f    d r o p s    g e n e r a t e d \frac{kapky\;uvnitř\;\;čtvrtina\;kruh}{celkový\;počet\;\;kapek\;vygenerováno} celkový počet kapek vygenerovaných ve čtvrtkruhu​ nebo zkráceně i t \frac{i}{t} ti Odtud můžeme sestavit rovnici se zlomkem plochy čtvrtkruhu na jednotkové čtvercové ploše rovným zlomku kapek uvnitř čtvrtkruhu na celkovém počtu kapek. Tuto rovnici je pak třeba vyřešit pro π \pi π a vede nás k následující rovnici:

Interaktivní simulace

Implementoval jsem interaktivní simulaci v React a Typescript. Aplikace používá Plotly.js ke kreslení jednotkového čtverce, čtvrtkruhu a dešťových kapek. Přidal jsem několik tlačítek pro náhodné generování 1, 10, 100 nebo 1000 dešťových kapek. Kapky deště jsou zbarveny modře, pokud spadají do čtvrtkruhu, jinak jsou zbarveny červeně. K dispozici je také speciální tlačítko označené jako Let It Rain neustále generovat dešťové kapky, jako by pršelo. Po každé aktualizaci se opět vypočítá přibližná hodnota Pi na základě nově vygenerovaných dešťových kapek. Čím více dešťových kapek, tím přesnější je hodnota Pi.

Odkazy

  • Interaktivní simulační aplikace
  • Zdrojový kód na GitHubu
  • Simulace Monte Carlo