Štampač računa PI

Šta je zajedničko programima CorelDraw, Acrobat Distiller, Adobe Photoshop i bilo kom PostScript štampaču? Verovali ili ne, svaki od njih može da izračuna proizvoljan broj decimala broja PI. Pogledajmo kako se ova, naizgled paradoksalna, mogućnost može primeniti...
Bojan Stojanović

DOWNLOAD: pc036pi.zip

Program za izračunavanje broja PI na 1000 decimala, napisan u PostScript-u, može se startovati u većini DTP aplikaciji. Na slici je primer iz Adobe Illustratora 7.

Jedna od mnogih stranica na Internetu posvećenih broju PI


int a=10000,b,c=2800,d,e,f[2801],g;
main(){
  for(;b-c;)f[b++]=a/5;
  for(;d=0,g=c*2;c-=14,
	printf("%.4d",e+d/a),e=d%a)
  for(b=c;d+=f[b]*a,
	f[b]=d%--g,d/=g--,--b;d*=b);
}

Slika 1: Najkraći C program koji računa PI na 800 decimala.

Softver ili hardver uglavnom posmatramo kroz vizuru primene: teško da ćemo pomešati QuarkXPress i grafičku karticu, ili im dodeliti neke zajedničke atribute. Iz tog ugla ne očekujemo da CorelDraw nešto izračuna, a još manje da se laserski štampač upusti u takvu avanturu: za rešavanje matematičkog zadatka na računaru potreban je program i, naravno, programski jezik, ali se taj jezik mora prilagoditi uslovima: da se, na primer, tražilo da Word izračuna PI, problem bi rešio makro napisan u Visual Basic-u.
Jedini programski jezik koji poznaje čitava paleta DTP programa je PostScript. Iako je on specijalizovan za opisivanje grafičkih objekata, on može biti i programski jezik opšte namene. Takva upotreba je sasvim neprimerena, ali nam može poslužiti kao demonstracija skrivene snage PostScript-a i kao originalan način testiranja brzine PostScript RIP-ova.

Prvih 1000 decimala...

Poslednjih godina primetna je orijentacija svih DTP paketa ka "čistom" PostScript-u: sve više aplikacija ima ugrađen PostScript RIP (samim tim i mogućnost interpretacije PostScript koda), a izlazni format programa kao što su Adobe Illustrator ili Macromedia FreeHand je upravo EPS. Program za izračunavanje broja PI će temeljno opteretiti svaki RIP, stavljajući u pogon aritmetičke operatore PostScript-a. Ukoliko aplikacija u kojoj želite da ga isprobate ne podržava fajlove sa ekstenzijom .PS, preimenujte ga u PI.EPS.
Da biste program poslali PostScript štampaču, u DOS režimu ćete okucati COPY PI.PS PRN (ili LPTx). Posle izvesnog vremena (u zavisnosti od broja decimala) na ekranu, papiru ili filmu (ako ste se odlučili da PI računate na osvetljivaču) pojaviće se 3,1415926... Primetimo da u slučaju startovanja programa na štampaču kompletan proračun obavljaju mikroprocesor i PostScript interpreter koji se nalaze u samom štampaču, dakle bez pomoći računara. Program PI.PS, kao i druge programe koje ćemo pomenuti u nastavku teksta možete preuzeti sa SezamPro-a (iz konferencije PcPress/Prilozi, arhiva je pc036pi.ZIP).
Pošto smo se upoznali ovaj neobični način za računanje broja PI, možemo izvući neke konkretne zaključke. Svi testovi su urađeni na Pentium-u 200, a štampači su bili HP LaserJet III sa PostScript kertridžom, HP 5MP, HP 4M Plus i HP 4000. PI je izračunavan na 1000 decimala.
Odmah primećujemo izrazitu superiornost PostScript "rasterizacije" na računaru: HP LaserJet III sa svojih 55 minuta i 50 sekundi deluje kao neka sporovozna 286-ica. Naravno da je procesor Motorola MC 68000, koji je ugrađen u ovaj štampač, daleko sporiji od Pentium-a, ali možda niste imali predstavu koliko ta razlika zaista iznosi. Nominalno veća brzina štampača (izražena brojem stranica u minutu) uvek znači i bržu logiku - HP 4M Plus je dva puta brži od HP 5MP (12 naspram 6 ppm) i posao je završio za približno dvostruko manje vremena. Najzad, najbrži je bio HP 4000, ali je njegovih 61 sekund još uvek daleko od rezultata koje su ostvarili DTP programi i alati.
Detaljne rezultate testa prikazuje tabela 1. Kao softversku referencu, uzećemo Acrobat Distiller 3.0, u koji je ugrađen originalni Adobe RIP, koji je izračunao PI na 1000 decimala za 29 sekundi. Ghostscript je, međutim, isto uradio za samo 11 sekundi, što svedoči o kvalitetnoj implementaciji i dobroj optimizaciji interpretera. Najsporiji Adobe program bio je Photoshop, ali PostScript rasterizacija ionako nije njegov primarni zadatak. Ako eksperimentišete sa povećanjem broja decimala tako što ćete u programu promeniti vrednost promenljive ndigits, imajte na umu da upotrebljeni algoritam ima kvadratni red složenosti, tako da nije pogodan za za zaista veliki broj decimala.
Koliko je ovakav jednostavan benchmark merodavan za testiranje brzine PostScript štampača? Radi se o rudimentarnoj proveri, jer se u programu intenzivno ne koristi ni jedan grafički operator. Realnu ocenu može da pruži jedino baterija testova, specijalno pripremljenih .PS fajlova, koji će prikazati brzinu rada sa rasterskom i vektorskom grafikom, memorijom, fontovima, o čemu ćete moći da čitate u nekom od narednih brojeva "PC"-ja. Međutim, na osnovu prvih utisaka, PI.PS uglavnom prikazuje realan odnos snaga - nikada se nije desilo da štampač koji se izrazito loše pokazao na ovom "ispitu" briljira kada se upotrebe složeniji testovi.

PI na Internetu

Ovaj tekst je zgodna prilika da se sa aspekta moderne računarske tehnologije osvrnemo na fenomen broja PI, koji je već tri milenijuma omiljena matematička konstanta čovečanstva. Na Internetu se danas nalazi ogroman broj stranica posvećen isključivo broju PI, postoje klubovi njegovih obožavalaca, održavaju se takmičenja u "recitovanju" prvih N decimala... Čak i popularni Yahoo ima svoju PI stranicu (www.Yahoo.com/Mathematics/Numbers/Specific_Numbers/Pi) gde možete pretraživati prvih 50 miliona decimala, odnosno pronalaziti prvo pojavljivanje zadatog niza cifara (probajte vaš datum rođenja u obliku ddmmgggg, ja sam se pronašao na 33.355.291. decimali).
Mali pregled istorije matematike govori da su se stare civilizacije u početku zadovoljavale procenom da je obim kruga tri puta duži od njegovog prečnika. Arhimed je, posmatrajući pravilne mnogouglove sa 6*2n stranica opisane i upisane u krug zaključio da se PI mora nalaziti između 223/71 (3.1408...) i 22/7 (3.1428...), čime je dobio prve dve tačne decimale.

[1]
John Machin, 1706.

Tek je razvoj matematike u XVII veku doveo do toga da 1706. godine John Machin obelodani formulu [1] kojom je izračunao PI na 100 decimala. Tada nastupa era nadmetanja i sve tačnijeg računanja broja PI koja traje i danas. Trenutni rekord drže Japanci, Yasumasa Kanada i Daisuke Takahashi sa Univerziteta u Tokiju koji su između 6. i 8. juna 1997. godine izračunali PI na 51.539.600.000 (3*234) decimala, za šta im je bilo potrebno 29 časova i 3 minuta; koristili su superkompjuter Hitachi SR2201 sa 1024 procesora. Kurioziteta radi spomenimo da je William Shanks 1874. godine "peške" izračunao PI na 707 decimala, ali je kasnije ustanovljeno da je samo prvih 527 tačno. Shanks-u je trebalo 15 godina, odnosno za svaku decimalu u proseku nedelju dana.

Machin-ova formula je sve do sedamdesetih godina ovog veka korišćena kao primarna za izračunavanje broja PI u decimalnom razvoju. Veoma je jednostavna za realizaciju i zahteva samo osnovne računske operacije (doduše, nad velikim brojevima); PostScript program koji smo predstavili takođe je zasnovan na ovoj formuli. Međutim, za dvostruko više decimala potrebno je četiri puta više vremena, a utrošak memorije raste linearno. Danas se uglavnom koriste formule koje mnogo bržu konvergiraju, ali su i teže za programiranje. Najpoznatija je formula koju su 1984. objavili Jonathan i Peter Borwein - pogledajte www.cecm.sfu.ca/personal/pborwein/PISTUFF/Apistuff.html. Programi napisani pomoću njihovog i drugih modernih algoritama izvršavaju se u vremenu O(n*ln₃(n)).

Iako se rekordi obaraju na superkompjuterima, vaš PC ima dovoljnu snagu da prvih nekoliko hiljada decimala broja PI izračuna gotovo trenutnom, bez obzira na primenjeni algoritam. Posebno je zanimljiv primer sa slike 1, verovatno najkraći C program koji računa PI na 800 decimala.

Neki PI trendovi

Kao posebnu poslasticu izdvajamo Super_Pi, koji je pravi brzinski šampion: radi se o Windows verziji programa kojim su Takahashi i Kanada 1995. godine izračunali PI na više od četiri milijarde (2³²) decimala. Upotrebljen je Gauss-Legendre algoritam, a na Pentium-u 200 izračunao je 1 M decimala broja PI za nešto više od 20 minuta. Sve je postalo još uzbudljivije kada su 1995. godine David Bailey, Peter Borwein i Simon Plouffe predstavili formulu [2].

[2]
Formula kojom se n-ta "decimala" u brojnom
sistemu sa osnovom 16ⁿ dobija bez izračunavanja
prethodnih n decimala.

Na ovaj način je moguće izračunati PI u brojnom sistemu čija je osnova stepen dvojke (recimo u binarnom ili heksadecimalnom) izuzetno brzo i efikasno, tako što se n-ta cifra može izračunati bez potrebe da se računaju prethodnih n-1 cifara; do njihovog otkrića smatralo se da je ovako nešto nemoguće. Uz to, utrošak memorije je izuzetno skroman (i uz to konstantan), nisu potrebne procedure za aritmetičke operacije nad velikim brojevima i vreme izvršavanja raste gotovo linearno kada se povećava broj "decimala". Korišćenjem ovog algoritma (BBP) septembra 97. izračunato je bilion (10¹²) cifara PI u binarnom brojnom sistemu.
Na nesreću onih koji priznaju samo dekadni sistem, nije ustanovljeno da li postoje polinomi a(n) i b(n) takvi da važi [3].

[3]
Još uvek nije dokazano da li se
PI može predstaviti u ovakvom obliku.

Međutim, Simon Plouffe je 1996. godine objavio algoritam za direktno izračunavanje n-te decimale broja PI korišćenjem formule [4] (www.lacim.uqam.ca/plouffe/Simon/articlepi.html). Ovaj algoritam ima uglavnom teoretski, jer je izuzetno spor, ali je zato utrošak memorije minimalan.

[4]
Pomoću ove formule se n-ta decimala broja PI može
izračunati u brojnom sistemu sa osnovom 10ⁿ
na sličan način kao i pod [2], ali u vremenu O(n²)

Čemu sve to?

Ovo je pitanje koje se uporno postavlja već 3000 godina, uporedo sa obaranjem rekorda u računanju decimala broja PI. Naravno da je za bilo kakvu praktičnu primenu (recimo za astronomske proračune) sasvim dovoljno recimo 50 (ili da budemo velikodušniji 100) decimala. Očigledno je, međutim, da ima nečeg magičnog u tom broju, kada je na njega "uludo" potrošeno toliko miliona sati života raznih ljudi i procesorskog vremena ogromnog broja računara. Osim toga što se koristi kao benchmark superkompjutera, izračunavanje broja PI je često i provera njihove pouzdanosti; tako je 1986. godine program koji je računao PI pronašao bag u jednom IBM-ovom velikom računaru.
U predgovoru knjige PI: A Source Book stoji da je fenomen PI praktično jedina tema koja seže do samih korena matematike kao nauke, a koja zaokuplja i moderna matematička istraživanja. Naša sposobnost za izračunavanjem ovog broja razvijala se uporedo sa razvijanjem raznih matematičkih disciplina, pogotovo numeričke analize i teorije brojeva. Iz tog ugla, ovaj tekst je doprinos jednom neobičnom gledanju na PI - iz DTP perspektive.