Otkrivamo: Broj Pi kroz vekove

Računanje matematičkih konstanti na željeni broj decimala danas je rutinsko i, uz savremeni hardver, veoma brzo. U pionirskima danima računara nije bilo tako, a naročito ne pre njihove pojave, kada su matematičari jedino mogli da zamišljaju mašinu koja bi sav posao uradila umesto njih. Pogledajmo kako se računala vrednost broja π kroz istoriju do danas!

Podsetimo se nakratko teksta „Bag tridesetogodišnjak“ iz PC#261. Igrom slučaja, dok sam radio na razvoju biblioteke koja bi omogućila računanje matematičkih funkcija na danas prilično zastarelim mikrokontrolerima baziranim na 8‑bitnoj arhitekturi, veoma interesantan izazov bio je da se napiše biblioteka za računanje matematičkih funkcija na proizvoljan broj tačnih decimala (onoliko koliko specifični mikrokontroler dozvoljava, s obzirom na limitiranu memoriju i brzinu). Seto sam se da je u časopisu „Računari“ nekada davno objavljen program za računanje broja π na 1000 decimala. Iako sam koristio moderniju formulu koja brže konvergira, ipak sam iskoristio taj program za testiranje tačnosti, pošto se tada, u tom programu, koristila veoma dobro poznata Machin‑ova formula, kako bih potvrdio tačnost novih funkcija. Neverovatna greška u samo dve cifre pojavila se posle izvršenja objavljenog programa Lea Bosnića. I posle detaljne provere izvora i rezultata koji je objavljen u časopisu kao prilog, bilo je jasno da je reč o bagu.

Iako je to bio prilično mizeran bag, slučajno otkriven sa zakašnjenjem od gotovo trideset godina i jednostavno ispravljen, postavlja se jedno prilično interesantno pitanje – kako je matematičarima iz doba bez računara uspevalo da izračunaju broj π na „skoro“ isti broj decimala kao u pomenutoj Dejanovoj pitalici?

Razotkrivanje tajne broja π počinje još od starih Vavilonaca (20 vek p.n.e.), koji su samo uz pomoć „štapa i kanapa“ eksperimentalno došli do vrednosti 3.

To „skoro“ znači red veličine manji, ali je i to tada bio neverovatan uspeh i nikako se ne bih usudio da umanjim tadašnja dostignuća do kojih se došlo bez ikakvih pomagala osim table, krede i često višegodišnjeg, pa i decenijskog napornog rada.

U vreme starih Vavilonaca

Razotkrivanje tajne broja π počinje još od starih Vavilonaca (20 vek p.n.e.), koji su samo uz pomoć „štapa i kanapa“ eksperimentalno došli do broja 3. Čak se navodi da postoji jedna vavilonska ploča koja ukazuje i na aproksimaciju 3 i 1/8 (3,125). Aproksimacija starih Egipćana bila je 3,1605 (Rhind‑ov papirus, 1650 p.n.e.).

Prvo značajnije izračunavanje broja π počinje geometrijskim pristupom Arhimeda (287‑212 p.n.e.), koji je ucrtavao pravilne poligone van i unutar kruga i, primenjujući Pitagorinu teoremu, došao do bolje aproksimacije 223/71 < π < 22/7 (3,1408 < π < 3,1429) pomoću 96 poligona. Od tada je π poznat i kao Arhimedova konstanta. Moderna interpretacija Arhimedovog pristupa bila bi sledeća (n je broj stranica poligona):

Posle Arhimeda i nekoliko uspešnih pokušaja, najznačajniji je bio napor Liu Hui (4. vek), koji je došao do 3,141024 < π < 3,142074, odnosno približno 3927/1250 ili 3,1416. Kineski matematičar Zu Chongzhi (429‑500) došao je sličnim metodom, uz daleko veći broj stranica poligona (pominje se 24576), do 355/113 (3,14159292035), što je tačno na neverovatnih šest decimala.

Ludolph van Ceulen (1540‑1610) proveo je veliki deo svog života (pominje se čak trećina) računajući broj π na što veći broj decimala na sličnom principu kao i prethodnici. Izračunao je tačno π na 20, potom na 32, dok je njegov učenik Snel izračunao π na 35 tačnih decimala. Zbog te zasluge i neverovatnog uloženog truda, po njemu je broj π svima poznat i kao Ludolfov broj.

Posle toga se pojavljuju prvi beskonačni nizovi i formule za računanje broja π velikog broja matematičara: Vijeta, Valasa, Lajbnica, Ojlera, Rimana… Christoph Grienberger (1561-1636) daje 1630. π na 38 tačnih decimala i narednih sedamdesetak godina nije bilo pomaka, dok engleski matematičar i astronom Abraham Sharp (1653‑1742) nije 1699. izračunao π na 71 decimalu koristeći arctan seriju, koju su nezavisno otkrili Gregori (1671) i Lajbnic (1674):

Do ove formule je zapravo prvi došao indijski matematičar Madhava iz Sangamagrame (1350‑1425), pa se osim naziva Gregori‑Lajbnicova, koristi i Madhava‑Lajbnicova ili Madhava‑Gregorijeva formula, zavisno od izvora. Serija za π je upravo specijalan slučaj pomenute serije za računanje arctan funkcije:

Jedna od interesantnijih serija koju je objavio indijski matematičar i astronom Nilakantha (živeo je od 1445 do 1545) konvergira daleko brže od prethodne:

Ojler‑Rimanova zeta funkcija

Prvi matematičar koji je uveo grčko slovo π za odnos obima i prečnika kruga bio je William Jones u radu iz 1706, ali su oznaku π matematičari masovno prihvatili tek posle njene popularizacije u dva Ojlerova rada iz 1736. i 1748. Osim toga, Ojler (Leonhard Euler, 1707‑1783) je dao veliki doprinos u mnogim oblastima matematike, astronomije i mehanike i smatra se jednim od najvećih matematičara svih vremena.

Jedna od najpoznatijih Dirichlet‑ovih serija (Johann Peter Gustav Lejeune Dirichlet 1805‑1859) jeste i čuvena Ojler‑Rimanova zeta funkcija:

Pre Dirichlet‑ove generalizacije, slične beskonačne serije bile su predmet i Ojlerovog interesovanja, koji je 1735. rešio čuveni bazelski problem, nakon čega je izračunao i doveo u vezu sa brojem π ovu seriju:

Ovde je interesantno navesti da se zeta funkcija može izraziti i sumom recipročnih stepena prostih brojeva, što je takođe Ojlerov doprinos:

…gde je p niz prostih brojeva, a s=2 u slučaju računanja broja π po prethodnoj formuli.

Kako do tada još uvek nije bila poznata kompleksna analiza, nemački matematičar Riman (Bernhard Riemann, 1826‑1866), proširuje 1859. zeta funkciju i na kompleksne brojeve i postavlja čuvenu hipotezu koju još uvek niko nije uspeo da dokaže ili opovrgne. To je danas poznat kao jedan od milenijumskih problema, za čije rešenje se nudi nagrada od čak milion dolara.

John Machin

Svim prethodnim formulama za izračunavanje broja π zajedničko je da veoma sporo konvergiraju. Tek je John Machin (1686‑1751) dokazao formulu koja otvara mogućnost bržeg izračunavanja. Machin je 1706. izračunao π na 100 tačnih decimala, što je do tada bila nedostižna granica. Njegova najpoznatija formula je:

Za potrebe ovog teksta, nazovimo ovu formulu referentnom. Konvergira sa 1,4 cifara po iteraciji i upravo je ona dugo korišćena za proveru gotovo svih kasnije nastalih. Računanje funkcije arctan obavljano je pomoću Gregori‑Lajbnicovog beskonačnog niza. Kako funkcija daleko brže konvergira što je argument bliži nuli, nastale su razne serije nazvane po Machin‑u. Neke od tih formula uspešno su se koristile za obaranje rekorda pre i posle 2000. godine, testiranjem i prvih superkompjutera, kao što je sledeća:

Ovu formulu dao je Kikuo Takano 1982. godine i s njom je Yasumasa Kanada oborio rekord na 1.2411×1012 tačno izračunatih decimala 2002. godine na Hitachi superkompjuteru.

Ramanujan

Vratimo se sada malo u prošlost, tačnije na početak 20. veka. Potpuno nepoznat matematičkim krugovima, pojavio se Indijac Srinivasa Ramanujan (1887‑1920), s neverovatnim formulama i teoremama u teoriji brojeva. Kao izuzetno nadaren dečak, poslat je u školu u Madras sa svega sedam godina, a kasnije kao mladić, na nagovor svojih kolega, počeo je da šalje svoje formule i radove u Evropu. Papiri sa formulama uglavnom su mu vraćani, pošto za većinu Ramanujan nije izvodio dokaze, sve dok poznati matematičar G. H. Hardy nije uvideo njihovu genijalnost, pa ga je pozvao da dođe u Englesku kako bi nastavio svoje školovanje i dao doprinos matematici, što je Hardy svojim parama finansirao.

Ramanujan je u svom radu Modular equations and approximations to π, koji je objavljen 1914, dao i nekoliko formula sa aproksimacijom broja π do šest tačnih decimala, ali i do tada potpuno nove formule. Pored toga što je bio matematički samouk i veoma mlad, pokazao je neverovatnu matematičku percepciju i kasnije dao veliki doprinos u matematičkoj analizi i teoriji skupova. Gotovo ne započevši svoje formalno matematičko obrazovanje u Evropi usled niza zdravstvenih problema, vratio se u rodnu Indiju, gde je i preminuo u 32. godini. Hardy je insistirao da se sakupe i objave svi njegovi radovi i rukopisi, što je i urađeno. Nažalost, rad posvećen broju π, kao i većina njegovih formula koje su date bez izvođenja dokaza i mogućnosti praktične provere tačnosti, pale su u zaborav sve do 1986, kada su Browein i Bailey analizirali njegove radove i pronašli formule za π. Uz malo modifikovanu formulu, dokazali su da je tačna:

Ova formula daleko brže konvergira (osam cifara po iteraciji) od svih Machin‑ovih serija i bila je inspiracija braći Chudnovsky za još bolju formulu, koja konvergira sa 14 cifara po iteraciji. Tako su 1989. godine oborili nekoliko rekorda i prevazišli magični limit od milijardu decimala:

Bivša YU i broj π

Interesantno je svakako pomenuti Jovana Puzovića, danas redovnog profesora Fizičkog fakulteta u Beogradu, koji je 1983. godine objavio da je na kalkulatoru TI‑59 uspeo da izračuna 1188 decimala broja π, koristeći Machin‑ovu referentnu formulu. Program se izvršavao 62 + 18 sati u fast režimu kalkulatora, uz snimanje međurezulata na magnetnim karticama. Prema sećanjima urednika ovog časopisa, Jovan je svoj program za TI‑59 poslao Galaksijinom klubu korisnika programabilnih kalkulatora i program je uvršćen u katalog.

Pošto je Dejan (Ristanović, gl. odg. ur. PC Press-a, prim. ur) uvideo da program ima izuzetne performanse, poslao ga je američkom časopisu TI PPC Notes. Urednik tog časopisa, Palmer O. Hanson, Jr. se veoma pohvalno izrazio o programu i objavio ga u v8n1p21‑22 (januar 1983). To se lepo uklopilo u prijateljsko takmičenje sa korisnicima HP kalkulatora koje je počelo još u junu 1980. kada je u PPC Calculator Journal‑u objavljen program koji računa 1160 decimala broja π za 15.25 časova. Takmičenje se nastavilo sve do 2004. godine.

BBP formula

Veliki obrt oko postupka vezanog za izračunavanje broja π desio se 1996, kada su David H. Bailey, Peter Borwein i Simon Plouffe došli do formule kojom se direktno računaju heksadecimalne cifre broja π na željenoj poziciji. Postoje varijante formule s različitim brojem članova, čime se postižu izuzetno visoke performanse na multi‑core procesorima, odnosno superkompjuterima.

BBP formula – 4 člana:

BBP formula – 7 članova:

Kompletan postupak opisan je u radu The BBP Algorithm for π, David H. Bailey iz 2006. BBP formule se uglavnom koriste za proveru rezultata dobijenog pomoću Chudnovsky agloritma. Pomenućemo da postoje odgovarajuće formule za računanje nekih drugih konstanti na proizvoljan broj decimala, kao što su ln(2) i ln(10).

Zašto nas π toliko fascinira

Počevši od Arhimeda pa sve do pojave prvih mehaničkih i elektronskih računskih mašina, matematičari su se poprilično namučili izračunavajući π na što veći broj tačnih decimala, iako se to većini možda čini kao uzaludan napor. Neki matematičari bili su naprosto opsednuti brojem π – Ludolf je skoro trećinu svog života proveo računajući broj π!

William Shanks (1812‑1882) je pored računanja konstanti e i γ na što veći broj decimala, tabele prostih brojeva do 60.000, uložio i dvadesetak godina uz manje prekide i provere, računajući π do 707 decimala i rezultat objavio 1874, primenjujući referentnu Machin‑ovu formulu. Godine 1944. je, proverom pomoću mehaničkih kalkulatora, D. F. Ferguson dokazao da je od toga 527 cifara tačno, koristeći formulu:

Sam D. F. Ferguson je izračunao π na 620 decimala i do 1949. rekord je nekoliko puta obaran. Poslednje takvo izračunavanje bilo je na 1120 decimala, kada je saradnik bio John Wrench.

Pojavom prvog elektronskog računara 1949. (ENIAC), rekord se povećao na 2037 decimala, a kasnije je broj cifara vrtoglavo rastao pojavom tranzistora, prvih integrisanih kola, mikroprocesora i, naročito, pojavom superkompjutera.

Koliko je računanje broja π bilo popularno, dokazuje i to da se svake godine obeležava dan broja π, 14. mart, treći mesec u godini, što reprezentuje 3,14. Na taj dan, običaj je da se entuzijasti takmiče u tome ko će više zapamćenih decimala tačno izrecitovati, podseća se na koliko je sve načina π izračunavan tokom istorije, ali i jede pita (pie na engleskom). Ginisov rekord drži Suresh Kumar Sharma iz Indije, koji je 2015, sa svojih 20 godina, izrecitovao tačnih 70.030 cifara za 17 sati.

Počevši od Arhimeda pa sve do pojave prvih mehaničkih i elektronskih računskih mašina, matematičari su se poprilično namučili izračunavajući π na što veći broj tačnih decimala, iako se to većini možda čini kao uzaludan napor

Poslednji svetski rekord u izračunatom broju decimala oborila je baš na dan broja π, 14. marta 2019. Emma Haruka Iwao, Japanka zaposlena u Google‑u – izračunato je 31.415.926.535.897 decimala, što je π×1013 decimala. Računanje je trajalo 121 dan (počevši od 22. septembra 2018. u 06:49:32 do 21. januara 2019. u 09:40:50) na 26 Google Cloud virtuelnih mašina sa 170 TB memorije, koristeći program y‑cruncher i Chudnovsky algoritam. Rezultat je proveren za 20 sati i to dvostruko: 7‑članim i 4‑članim BBP formulama. Program y‑cruncher napravio je Alexander J. Yee, koji je započeo da ga piše pre nekih 10 godina. Program optimizuje izvršavanje Ramanujanove i Chudnovsky formule i iskorišćava multi‑core i multi‑thread sposobnosti današnjih procesora. Detalji se mogu pogledati ovde i ovde.

Google je sve izračunate decimale objavio na svojim serverima i može im se pristupiti putem ovog servisa. Pitanje je samo da li će ikada ikome i biti potrebne…

Kome je uopšte potrebno toliko cifara?

Ako je π na sedam decimala dovoljan za grešku manju od jednog metra za obim Zemlje, a osamdesetak decimala dovoljno dobro za astronomske proračune u celom univerzumu, kakva je draž i svrha fascinacije brojem π i računanje drugih matematičkih konstanti na toliko decimala? Realno gledajući, neka konkretna svrha ne postoji, osim testiranja superkompjutera i postavljanja rekorda.

Najava je da će do 2020. godine Moore‑ov zakon prestati da važi s dosadašnjom tehnologijom, ali kako se danas uveliko koriste multi‑core procesori, moguće je da ćemo svi mi u veoma bliskoj budućnosti (i verovatno uz novu tehnologiju izrade procesora) imati jeftine superkompjutere na stolu, pa će uz toliku procesorsku snagu i nekada nezamislivoj količini radne memorije, obaranje rekorda u izračunatim decimalama raznih konstanti postati potpuno besmisleno.

Draž svakako ostaje nostalgičarima i programerima „starog kova“ da pogodne formule i algoritme prilagode i primene u svojim projektima, naročito s jeftinijim mikroprocesorima i mikrokontolerima, koji se danas i koriste u kalkulatorima, mobilnim telefonima i tabletima.

Autor: Saša Zeman