GradientTop
PC
Vodeći IT časopis u Srbiji
PC #261 > Tehnovizija
ARHIVA BROJEVA | O ČASOPISU | POSTANI SARADNIK | PRETRAGA
preview
Bag tridesetogodišnjak
Dejan Ristanović
Živimo s kompjuterima, pa onda živimo i s bagovima. Neki vas namuče pa ih najzad otklonite, a mnogi ostanu skriveni zauvek. Ili makar 30 godina... Novogodišnja priča se bavi jednim takvim bagom iz davnih vremena, koji nas je sustigao kad smo ga najmanje očekivali
- PC #261 u prodaji po ceni od 110 din
broj

Bag tridesetogodišnjak

image

Kada bih podesio vremeplov na decembar 1988. godine, možda bih ugledao 30 godina mlađeg sebe kako sedi ispred amber monitora i tastature svog IBM PC AT kompatibilnog računara u koji je upravo ugrađen Seagate ST-4096 hard-disk od čitavih 80 MB (da, megabajta... jesam na tog džina potrošio 1850 maraka, ali sam barem znao da imam prostora koliko u životu neću uspeti da popunim). Posla je bilo mnogo, pisao sam Turbo Pascal program za prelom „Indeksa poslovnog vodiča SFRJ“, privredne publikacije „Narodne knjige“ od oko 900 strana koje je trebalo štampati na pausu, koristeći nedavno kupljeni HP LaserJet II. Taj ogroman i hitan posao sam ipak morao da prekinem da bih završio tekstove za novogodišnje „Računare“ pošto sam, možete misliti, kasnio (tu 30 godina nije ništa promenilo). Nakon pisanja prikaza SoftCraft kolekcije fontova, poređenja programa GrafPlus za „hvatanje“ sadržaja ekrana s sistemskim PrtScr tasterom i opisivanja načina da se prevaziđe limit od 64 KB memorije u Turbo Pascal programima (za imenike koje sam prelamao 64 KB definitivno nije bilo dovoljno), ostale su mi još „Dejanove Pitalice“. Bila je to rubrika koju sam istovremeno i mnogo voleo i mnogo mrzeo, naročito kada treba smisliti još jedan originalni problem koji se rešava pomoću računara i koji kao rezultat daje jednu brojku (takva je bila koncepcija rubrike). I još je problem trebalo da bude prigodan, novogodišnji...

PI na puuuuno decimala

Broj 1989. u matematičkom smislu nije ništa posebno – mada deluje prosto, nije prost (9×13×17=1989), nije savršen, nije palindrom... Posle malo mozganja pade mi na pamet da bih ga mogao potražiti među decimalama broja e ili broja π. Najzad, profesori matematike, dok objašnjavaju transcendentne brojeve, kažu da taj beskonačni niz cifara sadrži bilo šta, možda i čitav „Rat i mir“ (u šta i danas veoma sumnjam, uz svo uvažavanje beskonačnosti), pa se valjda negde nađe i broj 1989.

S obzirom na opštu gužvu u kojoj sam se nalazio, teško da bih se usudio da pišem program koji računa puno decimala broja π, ali sam srećom mogao da se oslonim na svoju programersku prošlost. Kada bih opet zavrteo vremeplov i vratio se još desetak godina unazad, zatekao bih mnogo mlađeg sebe kako se šunja kroz hol hotela „Toplice“ u ulici 7. jula (danas se zove Royal Inn i nalazi se u ulici Kralja Petra) u nadi da ga portiri neće primetiti dok ne stigne u „skriveni“ deo, gde se nalazio PDP 11 računar. Ljubazno osoblje računskog centra beogradskih hotelijera me je, kad god ima slobodnih resursa, puštalo da se igram na njihovom kompjuteru (hvala!) tj. da pišem programe u FORTRAN-u, koji je bio jedini raspoloživi jezik. Programi su bili jako „korisni“: logički problemi, matematičke igrice i raznorazna numerika; izračunao sam, recimo, 1000 decimala broja e, što je zvučalo kao nerešiv problem za moj tadašnji programabilni kalkulator TI-59, u čiju memoriju od oko 900 bajta tih 1000 decimala ne bi ni stalo. Pošto sam slavno savladao broj e, logično je bilo da računam i broj π, ali to nije išlo baš lako – neke formule koje sam znao, recimo π=4*arctan(1), su sporo konvergirale, pa se čak i „veliki i moćni“ PDP zagrcnuo.

Internet generacije ne mogu ni da zamisle koliko je tada bilo teško doći do informacija, naročito kod nas gde literature nije bilo – časopisi se ne uvoze, sve knjige su večito odnete iz biblioteka, a malo toga što ima po knjižarama je preskupo za učenički budžet. Najzad sam, ne znajući šta bih drugo, pitao mog profesora analize u Matematičkoj gimnaziji. Života (Žika) Joksimović je bio sjajan profesor koji se uvek trudio da nas podstakne da gledamo i van nastavnog plana, ali je i on morao da zatraži nekoliko dana kako bi razmislio o problemu. Na sledeći čas je doneo cedulju s formulom koju je 1706. godine objavio britanski matematičar John Machin: π = 16*arctan(1/5) – 4*arctan(1/239). Formula brzo konvergira i prilično se lako programira, pa sam ubrzo iskoristio snagu PDP-ja i izračunao 1000 decimala broja π (John Machin nije imao kompjuter, pa je π računao „na ruke“ i stigao do sasvim solidnih 100 tačnih decimala). Mogao sam da izračunam i mnogo više cifara, ali nije trebalo testirati strpljenje programera iz hotela „Toplice“ i opterećivati PDP. Sam program i 1000 decimala broja π odštampao sam na linijskom štampaču (ko se seća širokog papira s perforacijom čiji je svaki drugi red bio obojen bledo-zeleno?) i sačuvao to blago.

Cifru po cifru...

image

I tako sam zaronio u prašnjavi orman, pronašao deceniju star listing i počeo da tragam za nizom 1, 9, 8, 9. Kako sam prelazio s reda na red tako su nade da ću brzo i lako doći do Pitalice opadale (imam li ja negde FORTRAN kompajler za moj AT?) a onda, na sramotu Marfijevih zakona, nađoh 1989 na samom kraju listinga: 1 iz 1989 je 996. decimala broja PI! Zvučalo je kao dobro pretskazanje, pa sam završio tekst, odštampao ga i sledećeg dana odneo u Redakciju (bilo je to vreme pre modema), podnevši sve grdnje zbog „još jednog“ kašnjenja.

Dva meseca kasnije „Indeks poslovnog vodiča“ je bio davna istorija, uveliko sam radio na publikaciji „YUGO-ŽIRO 90“ i nekakvom „Katalogu kukuruza“, na kome je novi HP ScanJet Plus došao do punog izražaja (doduše tek pošto sam instalirao Windows 1.1). A i kasnio sam s tekstovima za „Računare“. Sa Pitalicama barem nije bilo mnogo posla – umesto uobičajene pune torbe odgovora, doneo sam samo četiri pisma – zadatak su rešili Nenad Barbutov iz Zagreba, Ištvan Boroš iz Subotice, Andrija Dinić iz Teslića i Siniša Đureković iz Zagreba. Iako su pronašli niz 1989 na 996. decimali (njegovo sledeće pojavljivanje nije daleko, već na 1236. decimali), svi ti programi su bili prilično spori i zahtevali su sate rada ozbiljnih računara.

Zato smo produžili rok i mesec dana kasnije dobili zaista brz program koji je napisao Leo Bosnić iz Zadra – na mom AT-u program je za 3 minuta i 22 sekunda izračunao 1320 decimala broja π. Listing je objavljen u jubilarnim Računarima 50, maja 1989. godine. Time je 38. Pitalica uspešno zaokružena i otišla je u istoriju, sačuvana jedino u arhivi „Računara“ na sajtu pc.sux.org i na nekoj mojoj disketi gde je decenijama bezuspešno čekala da od svih Pitalica napravim knjigu.

A onda...

Vratimo se u sadašnjost, ili makar u 5. oktobar 2018. godine kada mi je stigla poruka od Saše Zemana, takođe uspešnog rešavača Pitalica, koji je radio na matematičkoj biblioteci kojom bi se omogućila tačnost izračunavanja raznih matematičkih funkcija na željeni broj decimala. Setio se broja π i Računara 50, otkucao program i koristio ga da potvrdi sopstvene proračune. A onda, iznenađenje: pojavila se razlika u dve cifre – crvena trojka u našem listingu treba da bude 2, a crvena dvojka treba da bude 1. Danas je lako naći milion decimala broja PI na Internetu i potvrditi da program objavljen u Računarima 50 ima bag.

Bag mi je u prvi mah delovao potpuno neverovatno. Razumeo bih da program greši od neke cifre na dalje, ali da dve cifre u sredini budu veće za jedan... čuda matematike i kompjuterskih nauka. Da bi se program isprobao trebalo je ili pokrenuti originalni Turbo Pascal 5.5, što ne ide na 64-bitnom Windows-u (eventualno može da se koristi spori DOSBox, ili virtuelna 32-bitna mašina), ili ga konvertovati u Free Pascal, što nije težak zadatak. Nada da je problem negde u matematičkim bibliotekama Turbo Pascal-a je brzo pala u vodu – i Free Pascal je davao isti, pogrešan rezultat. I, šta sad? Naravno da nisam mogao ostaviti „usnuli bag“; zagonetka mora da se reši.

Gruba analiza programa ukazala je na poreklo greške. Program računa arcus tangens klasičnim razvojem u red, četiri po četiri decimalna mesta (četiri cifre se čuvaju kao jedan integer između 0 i 9999, da bi rad bio malo brži), a broj iteracija se minimizuje da bi se štedelo vreme (druga su to vremena bila...) Moguće je da ponekad iteracija ne odredi tačno četvrtu cifru, ali kako to izbeći? Koliko iteracija treba dodati?

Samo dva znaka

image

Znajući da sam već dovoljno „zabrljao“ pre 30 godina što sam prokontrolisao samo prve i poslednje cifre listinga (a i ko bi poredio 1000 cifara na ruke...), potražio sam pomoć „glavnog krivca“, gospodina Bosnića. Uz nešto guglanja i jednu srećno pretpostavljenu adresu, ubrzo smo uspostavili kontakt. Prva reakcija je bila upravo ono što se i očekuje od entuzijaste iz starih dobrih vremena: „auuu bruke, no svejedno ste me razveselili javljanjem“. Razmenili smo par poruka, isprobali nekoliko izmena i najzad je Leo otklonio bag – crveno downto nn u listingu treba zameniti s downto 1 – tako će iteracija u svakom prolazu ići do kraja, i greške ne može da bude. Doduše izgubiće se malo vremena, ali valjda su računari za 30 godina napredovali dovoljno da to više nije bitno.

Sam Leo Bosnić navodi da njegovo rešenje ne bi moglo da izračuna „beskonačno“ decimala broja PI, kada bi se konstanta n=332 na početku programa povećala. Kod računanja arctan(1/5) sledeći član niza se računa na osnovu prethodnog. Recimo da je zadnji izračunati član 1/(177*(5177)); sledeći (za 179) bi se računao tako što se prethodni član pomnoži sa 177, pa onda podeli sa 179, i sve podeli sa 25. Tamo negde oko 50000-tog mesta, kada se neki član množi s 29999 pa onda deli s 30001, mogle bi se pojaviti aritmetičke greške samog Turbo Pascal-a.

image

Modernizacija

Kad smo već čekali tri decenije, da vidimo ima li šta novo s računanjem broja PI. Ponovo ću se osloniti na iskustvo Saše Zemana, koji kaže da je u doba postavljanja ove Pitalice trebalo koristiti moderniju formulu, staru „samo“ četvrt veka. U doba kada sam bio u školi, pa i mnogo posle toga, niko nije ni pominjao indijskog matematičara Ramanujana (Srinivasa Ramanujan, 1887-1920); danas svi znaju za njega zahvaljujući pre svega filmu The Man Who Knew Infinity. Ramanujan je smislio neke veličanstvene trikova s brojevima. Umesto formule s arcus tangensima, trebalo je koristiti Ramanujanovu ideju izloženu u radu Modular Equations and Approximations to PI iz 1914. godine (sam rad ćete lako naći na Internetu; e sad koliko ćete ga razumeti...)

Formula u dnu stupca zvuči mnogo komplikovanije od ranije, ali daje devet tačnih cifara već posle dve iteracije. Serije Ramanujan-Sato su bile inspiracija braći Chudnovsky za formulu koja još brže konvergira, na osnovu koje su izračunali broj PI na milijardu tačnih decimala, upravo 1989. godine koja je počela 38. Pitalicom. Danas imamo Bailey-Borwein-Plouffe (BBP) formulu iz 1995. godine koja omogućava određivanje n-te decimale broja PI bez računanja prethodnih decimala. Prepuštam čitaocima da nešto od ovih ideja isprobaju u praksi i da nam pišu o tome. Pazite samo da ne napravite bag koji ćemo morati da otklanjamo tamo negde 2049. godine...

Za kraj, potražite i 2019 među decimalama broja PI – nećete morati da idete daleko. Srećna Nova godina!

image
SLEDEĆI TEKST U PC #261
nopreview
Uvodnik
Dejan Ristanović


.

PC
Twitter Facebook Feed Newsletter