Štampač računa PI

Softver ili hardver uglavnom posmatramo kroz vizuru primene: teško da ćemo pomešati QuarkXPress i grafičku karticu. 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 tražilo da Word izračuna p, problem bi rešio makro napisan u Visual Basic-u.

Jedini programski jezik koji poznaje čitava paleta DTP programa je PostScript. Iako 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 snage PostScript-a i kao 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 i Macromedia FreeHand je upravo EPS. Program za izračunavanje broja p ć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 na ekranu, papiru ili filmu pojaviće se 3,1415926... Program PI.PS, kao i druge programe koje ćemo pomenuti možete preuzeti sa SezamaPro iz konferencije PcPress/Prilozi, arhiva je PI.ZIP.

Pošto smo upoznali ovaj neobični način za računanje broja p, možemo izvući zaključke. Svi testovi su urađeni na Pentium-u 200, na štampačima: HP LaserJet III sa PostScript kertridžom, HP 5MP, HP 4M Plus i HP 4000. p 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 njegov 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 p 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.

p na Internetu

Na Internetu se danas nalazi ogroman broj stranica posvećenih isključivo broju p, postoje klubovi njegovih obožavalaca, održavaju se takmičenja u „recitovanju“ prvih N decimala... Čak i popularni Yahoo pretraživač ima svoju p 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 p mora nalaziti između 223/71 (3.1408...) i 22/7 (3.1428...), čime je dobio prve dve tačne decimale.

Tek je razvoj matematike u XVII veku doveo do toga da 1706. godine John Machin obelodani formulu [1] kojom je izračunao p na 100 decimala. Tada nastupa era nadmetanja i sve tačnijeg izračunavanja broja p 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 p 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 p na 707 decimala (prvih 527 tačno). Shanks-u je trebalo 15 godina.

Machin-ova formula je sve do sedamdesetih godina ovog veka korišćena kao primarna za izračunavanje broja p u decimalnom razvoju. Veoma je jednostavna za realizaciju i zahteva samo osnovne računske operacije; 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že 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×ln3(n)).

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

Neki p 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 p na više od četiri milijarde (232) decimala. Upotrebljen je Gauss-Legendre algoritam, a na Pentium-u 200 izračunao je 1 M decimala broja p 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]. Na ovaj način je moguće izračunati p izuzetno brzo i efikasno, u brojnom sistemu čija je osnova stepen dvojke , 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 skroman, nisu potrebne procedure za aritmetičke operacije nad velikim brojevima i vreme izvršavanja raste skoro linearno sa povećanjem broja „decimala“. Korišćenjem ovog algoritma (BBP) septembra 97. izračunato je bilion cifara p.

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]. Simon Plouffe je 1996. godine objavio algoritam za direktno izračunavanje n-te decimale broja p korišćenjem formule [4] (www.lacim.uqam.ca/plouffe/Simon/articlepi.html).

Čemu sve to?

Ovo je pitanje koje se uporno postavlja već 3000 godina, uporedo sa obaranjem rekorda u računanju decimala broja p. Naravno da je za bilo kakvu praktičnu primenu sasvim dovoljno recimo 50 (ili 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 i procesorskog vremena.

U predgovoru knjige p: A Source Book stoji da je fenomen p 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čunavanje 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 p – iz DTP perspektive.

Prilozi:

pc036pi.zip (344,83 kB)

© 1995-2024 PC Press. Sva prava zadržana.