Kintli Lajos (lajos.kintli@gmail.com), 2011.03.14 A Pi (3.1415926...) kiszamitasa a HT1080 iskolaszamitogepen =============================================================================== A kor keruletenek as atmerojenek aranyakent ismert allando, a PI meghatarozasa mindig is foglalkoztatta az embereket. Nagyjabol a HT1080 iskolaszamitogep elterjedesenek eveire nyulik vissza az a hir, hogy mar 2 millio jegyre szamitottak ki PI erteket az akkori csucsszamitogepekkel. Talan ennek hatasara is kaptuk hazi feladatul a gimnazista evek szamitastechnika szakkoren, hogy az iskolaszamitogeppel is kisereljuk meg kiszamitani PI-t. Nekem az akkori ismeretekkel az "arc tg" (arcus tangens) sorfejtese tunt legcelravezetobbnek. Egyertelmu volt, hogy az arc tg(1) gyakorlati szempontbol nem jelentene megoldast, hisz a sorfejtesben tul sok tagot kellene figyelembe venni, s a tul lassu konvergencia mellett a szamitasi pontatlansag is elrontana a vegeredmenyt. A problema megoldasan toprengve vettem eszre, hogy az arctg(1) felirhato az arctg(1/2) es arctg(1/3) osszegekent, ami mar a gyakorlatban is jol mukodo algoritmust eredmenyez. Ez alapjan irtam meg gepi kodban a programot. A megvalositas olyannyira elnyerte tanaraim tetszeset, hogy batoritasukra segitsegukkel egy cikk is megjelent az eredmenyrol: folyoirat: "A Matematika Tanitasa", 1986. augusztusi szam (33. evfolyam, 4. szem, 121-124 oldal). cikk cime: "A pi meghatarozasa szamitogeppel" Sajnos az eredeti program elveszett, de az algoritmust felidezve sok ev utan ujrairtam. Ra kellett azonban jonnom, hogy az akkor hasznalt algoritmus bar mukodokepes volt, de egyeltalan nem volt optimalis. Az akkori programmal 40 orat vett igenybe 1000 jegy szamitasa, mikozben csak kicsit optimalizalva a futasi ido kozel 7 percre csokkentheto (s ez egy emulatoron keresztul kb. 1 masodperc alatt lefuttathato egy mai PC-n). A programnak 3 verziojat is kozreadom: 1, PI.ASM a leggyorsabb futasu szeles korben elterjedt Machin nevehez kotodo Pi/4=4*arctg(1/5)-arctg(1/239) formulat hasznalo program. Az oszto algoritmus dinamikusan az oszto nagysaga alapjan 7, 8, 15 vagy 16 bitesre agazik el 2, PI_CIKK.ASM a cikkben hivatkozott pi/4=arctg(1/2)+arctg(1/3)-t hasznalo ujrairt program, meglehetosen lassu. Nem teljesen egyezik meg az eredeti programmal. 3, PI_2_3.ASM optimalizaltabb, szinten a pi/4=arctg(1/2)+arctg(1/3)-t hasznalo program. Ket - egy 7 bites valamint egy 16 bites szammal valo - oszto algoritmust tartalmaz (~19600 szamjegy szamitasaig hasznalhato). Mindharom program 3 formatumra is le lett forditva: - Intel HEX - CAS - CMD =============================================================================== A program futtatasa a FastZ80 emulator legujabb verziojaban javasolt: (letoltheto: http://ht.homeserver.hu/html/emulatorfastz80.html) 1, Inditsuk el az emulatort 2, a "READY ?" utan ussunk le egy "Enter"-t 3, hasznaljuk a "File" -> "Load..." menut, s valaszuk ki a futtatni kivant programot (pl "PI.HEX") 4, a program elindul s megjelenik az alabbi kerdes "PI SZAMITASA: JEGYEK SZAMA ?", ahol adjuk be a szamitando jegyek szamat (pl. 10) es ussunk le egy "Enter"-t 5, a program kiszamitja es kiirja a kepernyore a valaszt: pl. "3.14159 26535". =============================================================================== Megjegyzesek: - mindharom program egysegesen az arcus tangens sorfejtesere epit: arc tg(x)=x - x^3/3 + x^5/5 - x^7/7 + x^9/9 - x^11/11 + ..., ami 1/x reciprok ertekekre az alabbiak szerint nez ki: arc tg(1/x)=1/x - 1/x^3/3 + 1/x^5/5 - 1/x^7/7 + 1/x^9/9 - 1/x^11/11 + ... Mindegyik valtozat 2-es szamrendszerben szamol, majd az eredmenyt tizes szamrendszerbe valtja at. A programban 3 sokbites regiszter kezelese lett megoldva, (reg1) a sorfejtes osszeget tartalmazza, (reg2) az 1/x^(2n+1)-t, (reg3) pedig az 1/x^(2n+1)/(2n+1)-et. Az algoritmusban (reg2)-t 1/x-rol kell inditani, majd minden tovabbi lepesnel x^2-tel tovabb osztani, (reg3) (reg2)-bol (2n+1)-gyel valo osztassal szarmaztathato. Az egyes regiszterek tartalma fixpontos szamabrazolassal jeleniti meg a szamok tortreszet, mikozben az egesz resz 0. - a PI_CIKK-ben szereplo algoritmus mindig fix hosszusagu szamokkal szamol, osztaskor a regiszter tartalmat teljes hosszban 1 bittel balra forgatja, majd a tulcsordulas bitet a 16 bites HL regiszterben gyujti, s ebbol vizsgalja meg, hogy az oszto kivonhato-e. Az optimalizalt algoritmus ket ujitast vezet be (PI, PI_2_3). Egyresz byte-onkent megy vegig a szamokon, csak a byte-on belul vegzi az 1 bites forgatast, masreszt dinamikusan kezeli a regiszterek hosszat: a sorfejtesben a tagok egyre kisebb szamokat tartalmaznak, igy felesleges a regiszterek elejen keletkezo nullakkal szamolni. Ez a nem tul bonyolult optimalizalas tobb mint 300-szoros sebessegnovekedest eredmenyez 1000 szamjegy kiszamolasanal! - a PI_2_3 az arcus tangens sorfejtes tagjainak szamitasanal a (2n+1)-gyel valo osztasok 16 biten tortennek meg. Ez limitalja a szamitasokat. A 2^(2n+1)=10^x osszefuggesbol az x=(2n+1)*log(2), melynek maximuma a 16 bites szamabrazolas miatt x=65535*log(2), azaz x=19728. A program elvileg ennyi szamjegy szamitasaig hasznalhato, illetve gyakorlatban egy kicsivel kevesebbig. Hasonloan a PI_CIKK-ben levo oszto algoritmus 15 bites, igy ott az elvi maximum x=32767*log(2), x=9863 lenne a szamithato jegyekre, de ennek a program tul lassu volta miatt nincs jelentosege. A log(2) ketto tizes alapu logaritmusa, log(2)=0.30103. - a PI_2_3 programot tovabb lehetne gyorsitani, ha kihasznalnank, hogy 1/2^(2n+1) kettes szamrendszerben kerek szam, a valasztott szamabrazolasban csupan 1 bit 1-es, a tobbi nulla. Ehhez viszont meg kellene kettozni az altalanos arc_tg eljarast. - a program indulaskor keri a szamitando tizedes jegyek szamat. Nincs vedelem a tul nagy szamok beadasara. Nagyjabol ugy lehet szamolni, hogy a program 1 szamjegy szamitasahoz regiszterenkent 1/log(256) -> 0.41524 byte-ot hasznal, ami a 3 regiszterrel szamolva 3/log(256) => 1.2457 byte-nak felel meg. Figyelembe veve a program betoltesi helyet, a memoria vegen helyet foglalo stacket, ez nagyjabol 9000 szamjegy szamitasara elegendo a 16 KByte memoriaval rendelkezo gepen, illetve 35000 szamjegyre a 48 KByte-os gepen. (Kicsit novelheto, ha a programot a memoriaban elobbre toltenenk be.) - sok szamjegyre valo szamitas idoigenyes feladat. Celszeru az emulatort a leggyorsabb uzemmodban hasznalni (pl. FastZ80 "Machine" -> "Full speed" menu, vagy F8 gyorsbillentyu). - a programba beepitesre kerult a FastZ80 idozitojenek vezerlese, amivel egyszeruen kinyerheto a pontos szamitasi ido. Az idoeredmeny a "Machine" -> "Show Timer/Counter" menuponttal kerheto le vagy F12-es gyorsbillentyuvel. - nehany jellegzetes futasi idoeredmeny A lenti tablazatban osszefoglaltam nehany futasi eredmenyt. A Z80 ido az eredi gep idejet mutatja ora:perc:masodperc alapon, a FastZ80 ido pedig a FastZ80 emulator "full speed" modjanak futtatasi ideje. Ez utobbi egy Intel E3300-as 2.5GHz-es processzorral felszerelt PC-n lett merve, ami nagyjabol 670-szeres sebessegel futtatja a program futasanak jelentos reszet kitevo oszto algoritmust. Sot a PI_CIKK programnal mutatott Z80 MHz ertek 1536 koruli, ami 865-szoros eredeti gepsebesseget ad. Referencianak a tablazatba foglaltam a cikkben fellelheto nehany futasi eredmenyt is. program jegyek Z80 ido utolso 10 jegy FastZ80 ido ----------------------------------------------------------------------------- (CIKK) 10 00:00:00 14159 2653# (CIKK) 100 00:02:58 34211 70### (CIKK) 1000 40:09:?? 21642 01976 PI_CIKK 10 00:00:00 14159 26535 < 1 sec PI_CIKK 100 00:02:47 34211 70679 ~ 1 sec PI_CIKK 1000 40:30:44 21642 01988 ~ 169 sec PI_2_3 10 00:00:00 14159 26535 < 1 sec PI_2_3 100 00:00:04 34211 70679 < 1 sec PI_2_3 1000 00:07:04 21642 01988 ~ 3 sec PI_2_3 10000 11:40:12 52563 75666 ~ 61 sec PI 10 00:00:00 14159 26535 < 1 sec PI 100 00:00:01 34211 70678 < 1 sec PI 1000 00:02:44 21642 01988 ~ 1 sec PI 10000 04:40:24 52563 75674 ~ 25 sec PI 20000 18:43:43 04907 55177 ~ 98 sec PI 30000 42:13:59 94510 82490 ~ 223 sec PI 35000 57:37:02 17276 31632 ~ 304 sec - a program az eredeti HT1080 ROM specifikus szubrutinokra hivatkozik (pl. billentyu olvasasa es karakter kiirasa kepernyore), igy csak az azzal mukodo emulatorban futtathato (vagy eredeti gepen) - a CAS allomanyokban egysegesen a "PI" programnev lett hasznalva - mindegyik program a 0x5000 hexadecimalis cimre toltodik be, igy a SYSTEM parancsnal a /20480 kiadasaval indithato, ha ez automatikusan nem tortenne meg az emulatorban - a program a jobb regiszterkihasznalas erdekeben hasznal nehany nem dokumentalt Z80 utasitast is. Nem garantalt, hogy mindegyik emulator futtatja. A HT1080Z es FastZ80 emulatorral mukodik, de pl. a Real80PRO 2.5.5 valtozataval lefagy. - a programbol kilepni a szambevitel kozben a szokoz billentyu leutesevel lehet =============================================================================== Sok sikert a program kiprobalasahoz, tanulmanyozasahoz!