Z archivu progresivně mrtvého programátora: Jak vypočítat π s pomocí hodu šipkou

Jak už víte z předchozího dílu série článků „z archivu progresivně mrvého programátora“, jsou počítače vpodsatě úplně tupé mašiny, které dokáží neuvěřitelně rychle sčítat čísla, což z nich dělá ideální oběti pro otrockou práci nezbytnou k řešení složitých matematických a fyzikálních problémů, u kterých neznáme přesná řešení. A protože na 14. 3., kdy měl tento článek původně vyjít, připadá mezinárodní den π, máme teď spolu ideální příležitost ukázat si, jak počítače využít na odhad jeho hodnoty, a to včetně tak obskurní metody, jako je opakované virtuální vrhání šipek na terč.

Nezbytné minimum teorie

Protože předpokládám, že když už někdo čte článek na tak úchylné téma jako je výpočet π, bude o problematice něco vědět, nehodlám zde tvořit novou stránku wikipedie. Pro ty matematikou nepolíbené, kteří sem přeci jen nějakou náhodou zabloudili proto jen stručně. π nelze vyjádřit jako zlomek, je to číslo tzv. iracionální, a jeho desetinný rozvoj ubíhá donekonečna bez opakování vzoru. Přesto, že jeho hodnotu přesně neznáme, lidstvo by bez něj nepostavilo ani kolo od vozu, natož raketu na Měsíc. π je tedy pro lidstvo stejně důležité jako wifi, pivo nebo toaletní papír.

Archimedova aproximace π pomocí mnohoúhelníků

Odhad hodnoty π byl předmětem intelektuálního zájmu lidstva již před více než 2000 lety. První kdo našel spolehlivou metodu určení přibližné, ale i pro dnešní běžné výpočty dostačující, hodnoty π, byl Archimedes, kterého znáte asi především kvůli noření těles do kapalin nebo zrcadlům zapalujícím lodě útočící na Syrakusy. Archimedes využíval metodu vepsaných a opsaných mnohoúhelníků, jejichž obvod dokázal spočítat i bez znalosti goniometrických funkcí, „Kozinovy věty“¹ a jiných moderních výdobytků z 15. století našeho letopočtu.

Vizualizace postupu odhadu hodnoty π pomocí mnohoúhelníků

Archimedes začínal s mnohoúhelníky s malým počtem stran (například se šesti stranami) a postupně zdvojoval jejich počet (12, 24, 48, až 96 stran). S rostoucím počtem stran se oba odhady – jak zespodu, tak shora – blížily skutečné hodnotě obvodu kruhu.

Vypočítat obvod mnohoúhelníku o 6 stranách je snadné, protože ho tvoří rovnostrané trojuhelníky a tím pádem je obvod vepsaného trojuhelníku roven šestinásobku poloměru kruhu, do kterého je vepsán. Obvod opisovaného mnohoúhelníku snadno dopočítáme s Pythagorovou větou (tuhle matematiku najdete v každé učebnici pro základní školy). 

Po několika iteracích zdvojnásobení stran získal Archimedes následující nerovnost:

22371< π < 227

Tato metoda byla vzhledem k tehdejším prostředkům velmi přesná a představovala jeden z nejdůležitějších příspěvků k numerickému určení hodnoty π až do ranného novověku.

Pizza, trojúhelníky a výpočet π 

Ze Syrakus je to do Neapole co by raketou dostřelil, a proto je hlavní město pizzy další logickou zastávkou na naší cestě za různými metodami výpočtu π. Co má společného pizza s π? Zatímco Archimédés pracoval s mnohoúhelníky, v případě pizzy si vystačíme s jednodušší metodou – pravoúhlými trojúhelníky. Pokud postupně kružnici rozdělíme na trojúhelníky, výseče pizzy, s jejich výškami směřujícími ke středu, můžeme π aproximovat pomocí jejich stran. Stačí k tomu obyčejná Pythagorova věta.

Počet stran (polygónu): 12

Odhad PI: -
Skutečné PI: -

Čím více trojúhelníků použijeme, tím přesnější hodnotu získáme. Při stovkách trojúhelníků už se rozdíly mezi délkou ramene a výškou stávají zanedbatelnými a můžeme celý výpočet zjednodušit na pouhý poměr stran obdélníku. Pro lepší pochopení postupu výpočtu poskládáme výseče pizzy pěkně zigzag vedle sebe, přesně tak, jako na další animaci. Ve výsledném obdelníku představuje délka jeho delších stran obvod kružnice, délka kratších stran její průměr a jejich vzájemný poměr pak hodnotu π.

Spustit animaci

n = 0, ramena r = 0, základna a = 0, obvod n-úhelníku = 0, výška h = 0. Odhad π = 0

V každém kroku vykreslíme n rovnoramenných trojúhelníků (dvě strany r, úhel 360°/n), střídavě „nahoru/dolů“. Dva sousední sdílejí celou boční hranu délky r, takže dohromady tvoří lichoběžníky. Když první pravoúhlý trojúhelník přesuneme na konec, dostaneme obdelník.

Tento přístup není jen historickou kuriozitou, na stejném principu pracují některé moderní numerické metody pro výpočet π.

Monte Carlo výpočet PI pomocí trojúhelníku

Představte si, že jsem v hospodě, nebo možná raději v restaurantu na konci vesmíru, a přete se s několika štamgasty o to, jakou hodnotu má π. Jelikož jste všichni už dost nalití, nemůže být o nějakých výpočtech ani řeč, a proto se rozhodnete, že váš spor vyřeší náhoda v podobě vrhání šipek na terč. Tomuto přístupu k řešení problémů se říká metoda Monte Carlo (vidíte, Syrakuzy, Neapol, Monte Carlo, vystačíme si se středomořím), jejímž základem je pravděpodobnost.

Představme si, že na terč nakreslíte rovnostranný trojuhelník a do něj vpíšete kružnici, nebo, jak by řekli příznivci Harryho Pottera, že máte terč tvořený symbolem Deathly Hallows (relikvie smrti). 

Spustit simulaci

Aktuální odhad PI: 0
Počet iterací: 0

Pokud na takový terč začnete házet náhodně (se zavázanýma očima) šipky, pak poměr šipek, které skončí uvnitř kruhu, vůči počtu šipek dopadnuvších do celého trojúhelníku přibližně odpovídá poměru ploch těchto dvou tvarů. Matematicky to můžeme vyjádřit jednoduchou rovnicí.

π ≈ 6 × počet šipek v kruhucelkový počet šipek

Výhoda Monte Carlo metody spočívá v tom, že je neuvěřitelně jednoduchá na realizaci, stačí dostatek náhodných bodů (nebo hodů šipkou). A jaká je její nevýhoda? Přesnost závisí na počtu opakování, takže se vám může večírek nepříjemně protáhnout, a pokud si dáte příliš piv, možná se vám budou ty desítky tisíc hodů dost špatně počítat.

Závěr této kolektivní π-onanie

Každá z výše uvedených metod má své kouzlo. Archimédés a jeho mnohoúhelníky ukazují sílu geometrie, trojúhelníková metoda nám umožňuje π elegantně odvodit bez složitých funkcí a Monte Carlo nám dává možnost ho spočítat bez přemýšlení, třeba u piva s šipkami v ruce.

Dnes už však máme k dispozici daleko sofistikovanější algoritmy, například Gauss-Legendreho metodu nebo rychlou Fourierovu transformaci (na tu se podíváme někdy příště), které umožňují spočítat π s přesností na miliardy desetinných míst. Ale řekněte, kdy naposledy jste v reálném životě potřebovali více než 3.14?

1. Archimedes ale znal práci svého současníka Euklida a jeho věty pro výpočet stran trojúhelníků.