Jump to content

ukázka [JAVA] Automatická kalkulace Pi


Hip

Recommended Posts

  • Globální moderátor

Ahoj,

náhodou jsem dneska dostal nápad, že bych si chtěl vypočítat Pí. Přeci jen, nedávno byl mezinárodní Pí den. Rozhodl jsem se, že se s vámi podělím a každý může dát svému PC trochu zabrat nad nějakým tím výpočtem. Kód jsem hodil na github zde: https://github.com/woody41/pi-calc

Stačí zkompilovat a spustit přes maven. Je tam jednou zajímavé nastavení a to _round. Tímto nastavujete z kolika desetiných míst se bude Pí počítat. Čím více desetiných míst, tím přesnější výsledek a tím náročnější výpočet. Bohužel se jedná o navazující výpočty, takže mě nenapadlo jak z toho udělat více vláknovou appku aby byl výpočet rychlejší na vícejaderných procesorech. Enjoy a klidně přidejte vlastní kód, třeba jako pull request, pokud to bude dávat smysl, approvnu. Dejte vědět jak rychle vám to běží, je tam i counter na čas!

private static final MathContext _round = new MathContext(10000);

 

Edit: Můj čas:

0.071s - 0.2s na 10 000 desetiných míst
2.825s na 100 000 desetiných míst
106s na 1 000 000 desetincýh míst

na každé desetiné místo je tedy potřeba cca o 3750% více výpočetního výkonu respektive času.

  • Líbí se mi to! (+1) 1
Link to comment
Share on other sites

  • Majitel

Zajímavé téma.. Poté co se mi horko-těžko povedlo zprovoznit tvůj example, jsem zjistil, že tomu vůbec nerozumím :D

Začal jsem tedy s vlastní implementací v C#, jednak protože má Java šílený overhead a druhak jsem to chtěl pochopit alespoň ze základu. Po zkouškách různých iteračních algoritmů, jsem přišel na to, že v C# asi úplně nebude jednoduchý a rozumný pracovat s velkými čísli v iteračních algoritmech (.NET má sice vlastní implementaci BigIntegeru, ale relativně stupidní). Hledal jsem tedy jiné řešení a to ve formě spigotu (https://en.wikipedia.org/wiki/Pi#Spigot_algorithms), který by generoval číslice nezávisle na minulém výsledku, nezasíral by paměť, nepracoval s velkými daty a jen prostě flusal číslici za číslicí. 

Samozřejmě, já jako antimatematik, jsem nebyl absolutně schopen napsat dle vizuálu algoritmu na wiki, funkční kód. A taky jsem byl línej. Tak jsem hledal existující implementace v C# a po bandě iteračních algoritmů jsem konečně našel jeden, který vypadal, že by mohl být spigotový. Nemám sice absolutně šajn o tom, jak ten výpočet probíhá, ale funguje. Zkusím dále ještě rozebrat tu vykuchanou funkci a roznést ji po jádrech, uvidíme kam se s mojí (ne)znalostí matematiky až dostanu.

C# snippet je dostupný zde:

https://gist.github.com/ffredyk/bfbee1e0c9e682349c6b4a119b2dea55

image.png

EDIT: Po bližším zkoumání toho kusu kódu, který mi počítá Pi, si myslím, že se jedná o nějaký hybrid mezi iteračním a spigot řešením. Tedy, že pracuje na iterační logice, ale flusá výsledky po jednotlivých čislicích

Link to comment
Share on other sites

  • Globální moderátor

Tak jsem si přečetl něco o výpočtu Pí, koukal jsem na možnosti výpočtu a zjistil jsem, že jsou nové vzorečky pro výpočet. Zejména třeba:

https://wikimedia.org/api/rest_v1/media/math/render/svg/e2c3d64b5f167d9808a57154c76c5c0a16435d12

 

je vzorec, co vypočítá n-tou hodnotu bez předchozích hodnot.

 

Jinak můj výpočet byl založenej na klasickém původním odvození jak to odvodil Archimédés - vepsané mnohoúhelníky. Má ovšem jednu nevýhodu a to takovou, že odmocnina z 1 je iracionální číslo a Záleží na předchozích výpočtech. Tedy počet desetinných míst v první iteraci je limit pro přesnost finálního výpočtu Pí. Až bude chvilka, zkusím implementovat výše uvedený vzorec. Aktuálně je Pí vypočítané na cca 62.8 bilionů desetinných míst.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...