Mi a legegyszerűbb Pi közelítő egyenlet ami nem lassul?

Mindig lassul valamennyire. Ez a konvergencia természetéből adódik. A pontos értéket véges sok tag összeadásával (soroknál) vagy összeszorzásával (produktumnál) nem kapod vissza. A formulák a végtelenben vett határértékként adják a pi (vagy azzal arányos) értéket.

Itt van néhány algoritmus még:

[link]

@01:04 Valóban mindig lassul, sőt mindig exponenciálisan lassul, hiszen ha mindig közelítené, de nem lassulva akkor véges lépés alatt abszolút pontosan elérné a pi értékét, ami lehetetlen.

Viszont amire a kérdező gondolhatott az a számjegyek szerint tekintve nem exponenciálisan lassuló közelítés. Ugyanis ez a 3 módszer számjegyek szerint nézve is exponenciálisan lassuló, vagyis pl 100 jegyre az tíz a 100-on lépésszámmal összemérhető futási ideje van. Nincs az a gép ami kiszámolná úgy.

4 módszert leprogramoztam : [link]

A 4.-ik módszernek kerestem olyat ami gyakorlatilag is használható módszer, az angol wiki-ről néztem : [link]

Mj.:

Ilyen nagy pontosságú számításoknak külön tudománya van. A számítógép alapból nem tud ilyen pontosan számolni, ezt szoftveresen kell megoldani. Tizedes (vagy akár kettedes) tört alakban vesztességgel lehet tárolni a számokat pl az 1/3 számot tizedes tört alakban nem lehet leírni véges sok jeggyel, egy számítógépnek véges sok memóriája van, véges sok számjegyet tud eltárolni, ez kerekítési hibákat okoz előbb utóbb. A sokadik PI jegynél ezért elég fals érték jönne ki, ezért máshogy tárolom az értékeket teljesen pontosan törtként amit kiíráskor tizedes törtre dekódolok. (Meg persze valamelyik formula például pi/4-et közelíti amit pi közelítésre normálok kiíráskor.) Teljesen precíz akkor lettem volna, ha annyi tizedesjegyet írok ki mint ahány tizedesjegyig egyezik pi-vel az aktuális iterációban, viszont ekkor a másik 3 módszer nem látszik hogy "mit csinál". E helyett a törtet dekódolom hasra ütés szerűen 112 bit pontosságú lebegőpontos értékre és ezt írom ki tizedes törtként, persze belsőleg nem ezzel az értékkel számolok a kerekítési hibák elkerülése miatt.

@09:24

Ott nem a számábrázolás volt a fő probléma, hanem az, hogy gyakorlati szempontból rossz algoritmust választott a tanárod, ugyanis ahhoz túl lassan közelíti. (Igaz temérdek tagot összeadva halmozódhat a hiba, lehetne erről becsléseket csinálni, hogy mikor milyen kerekítési hiba lépne fel.)

Ha az általam válaszott arcus sinus-os közelítő sorfejtés szerint csináltátok volna akkor kb. 8-10 jegy pontosságig eljutottatok volna, tovább nem a számábrázolásból következő kerekítési hibák miatt. A pontosság függ a hardvertől, a választott lebegőpontos számtípustól, még attól is függhet, hogy hogyan van leprogramozva.

Az nagyon ki van optimalizálva, le a kalappal a készítők előtt.

Az is lassul csak lassan. Úgy értem, hogy kiszámoltam m db jegyig és n*m db jegyig több mint n-szer annyi ideig fog tartani. Pontosabban megfelelő n-ek és m-ek esetén, kicsi m esetén nem teljesülne az overhead miatt. Pl nálam m=500 millió jegyig kb 6x annyi ideig futott mint 100 millióig.

Olyan meg nincs, hogy nem lassul elvileg sem. (Azt nem tudom hogy hol a határ hogy meddig lehetne mérsékelni a lassulást.) Ez belátható az alábbi módon:

A számítógép bonyolult működése helyett egyszerűség kedvéért egy véges állapotú automatát vegyünk. (Mj. a számítógép is egy ilyen automata.)

Szorzás, osztás stb műveletek sorozatát végzi el ez az automata melyből végül "kipotyognak" a pi jegyei. A műveletek során megváltoznak bizonyos változók a programban, ami nem más minthogy más állapotba lépett a gép. Induláskor kezdő állapotba van, végül amikor kiszámolta a pi-nek adott számú jegyét akkor van végállapotba. A kezdő és végállapot között különböző állapotokat vesz fel. (Az aktuális állapotot a program által használt változók határozzák meg valamint az utasításszámláló hogy épp hol tart a kód végrehajtásában)

Tegyük fel, hogy minden állapotváltozáshoz t időhosszúság szükséges ami legyen egy időegység. Mivel optimális az pi közelítő algoritmusunk, dehát nem lassul ezért n darab jegy kiszámításához n*c időegység szükséges (c egy konstans amit nem definiálok, nem is lényeg mennyi). 2*n jegyjez 2*n*c időegység szükséges vagyis m*n jegyjez m*n*c idő szükséges. A programunknak véges sok állapota lehet ami azt jelenti, hogyha elkezdjük nagyon nagyon sokáig számolni a pi-t addig mondjuk "amíg nem szólok hogy stop" akkor előbb utóbb ugyan abba az állapotba kerül a programunk amibe már volt, hiszen véges sok állapota van vagyis onnantól kezdve bizonyos nagyságú szakaszon elkezdenek ismétlődni a pi jegyei. Ami csak akkor lehet, ha a pi racionális, de tudjuk hogy nem az. Vagyis szükségképpen olyan állapotváltoztatásra is szükség van ami nem t időegységű. A precíz és nehezen érthető kiegészítés helyett egy példát mondok.

Legyen egy olyan programunk ami egy számlálót növel egyesével 0-tól kezdve valameddig. A számláló BigInt típusú azaz tetszőlegesen nagy lehet. Egy növelés az egy állapotváltoztatás. Egy időegységbe telik a növelés következtében egy byte-ját megváltoztatni. Ezért 0-255 között egy időegységbe telik minden növelés. Mennyi időegység lehet a legtöbb egy növelésnek? Nincs ilyen, akármilyen nagy is lehet, megfelelően nagy szám esetében. Sőt a memóriakorlátot sem lehet mondani, hiszen az is nőhet bármely korláton túl, de annyit lehet mondani hogy a program memóriaigénye a futási idő logaritmusával összemérhető.