tvie s kazhdoj cepochkoj v raspredelitele proishodit cherez chetyrehslovnyj zagolovok, soderzhashchij ukaza- teli na nachalo cepochki, ee konec, sleduyushchee mesto dlya zapisi i sleduyushchee mesto dlya chteniya. Svyaz' mezhdu raspredelitelem i dc osushchestvlyaetsya cherez ukazateli k etim zagolovkam. Raspredelitel' pervonachal'no imeet odnu bol'shuyu cepochku v spiske svobodnyh cepochek. Vse zagolovki, isklyuchaya odin, ukazyvayushchij na etu cepochku, imeyutsya v spiske svobodnyh zago- lovkov. Zaprosy na cepochki vypolnyayutsya po razmeru. Razmer fakticheski vydelyaemoj cepochki, est' blizhajshaya sleduyushchaya ste- pen' dvojki. Kogda vypolnyaetsya zapros na cepochku, rasprede- litel' sperva proveryaet svobodnyj spisok, chtoby uvidet', est' li tam cepochka nuzhnogo razmera. Esli nichego ne najdeno, raspredelitel' ishchet bolee dlinnuyu cepochku i rasshcheplyaet ee do teh por, poka ne poluchitsya cepochka nuzhnogo razmera. Ostavsha- yasya chast' cepochki pomeshchaetsya v svobodnyj spisok. Esli ne - 23 - imeetsya cepochek bol'shego razmera, raspredelitel' pytaetsya ob®edinit' svobodnye cepochki men'shego razmera v odnu bol'- shuyu. Tak kak vse cepochki yavlyayutsya rezul'tatom rasshchepleniya bol'shih cepochek, kazhdaya cepochka imeet sosednyuyu s nej v pamyati i, esli sosednyaya cepochka svobodna, to, chtoby uveli- chit' cepochku, mozhno trebuemuyu cepochku ob®edinit' s sosednej. Pri bezuspeshnoj popytke najti cepochku podhodyashchej dliny posle ob®edineniya, raspredelitel' zaprashivaet u sistemy svo- bodnoe mesto. Kolichestvo pamyati v sisteme yavlyaetsya edinst- vennym ogranicheniem na razmer i kolichestvo cepochek v dc. V raspredelitele imeyutsya programmy dlya chteniya, zapisi, kopirovaniya cepochek, sdviga v nachalo, sdviga vpered na shag i sdviga nazad na shag po cepochkam. Vse manipulyacii s cepoch- kami vypolnyayutsya, ispol'zuya eti programmy. Programmy chteniya i zapisi uvelichivayut ukazatel' chteniya ili ukazatel' zapisi tak, chto simvoly cepochki chitayutsya ili pishutsya podryad seriyami vyzovov chteniya ili zapisi. Ukazatel' zapisi yavlyaetsya, po sushchestvu, ukazatelem na konec soderzhashchej informaciyu chasti cepochki i pri popytke prochitat' informaciyu, nahodyashchuyusya za etim ukazatelem, chtenie okazhetsya bezuspeshnym, a programma chteniya v kachestve otveta vernet priznak konca cepochki. Popytka zapisat' za konec cepochki vynudit rasprede- litel' zaprosit' bol'shee prostranstvo i zatem skopirovat' staruyu cepochku v bol'shij blok. 2.2.3. Vnutrennyaya arifmetika Vse arifmeticheskie dejstviya vypolnyayutsya v celyh chislah. Operandy (ili operand), trebuyushchiesya dlya vypolneniya dejstviya izvlekayutsya iz glavnogo steka i u nih otbrasyvaetsya toch- nost', hranyashchayasya vmeste s chislom. Dlya togo, chtoby poluchit' rezul'tat vypolneniya programm vnutrennej arifmetiki s podho- dyashchej tochnost'yu, k operandam dobavlyayutsya nuli ili otbrasyva- yutsya lishnie cifry. Naprimer, esli tochnost' operandov raz- lichna, i trebuetsya vyravnivanie, kak eto byvaet pri slozhe- nii, k operandu s men'shej tochnost'yu dobavlyayutsya nuli. Posle vypolneniya trebuemoj arifmeticheskoj operacii pered tem, kak zanesti rezul'tat v stek, v konec chisla dobavlyaetsya znachenie ego tochnosti Registr, nazyvaemyj scale, ispol'zuetsya v bol'shinstve arifmeticheskih operacij; scale opredelyaet kolichestvo desya- tichnyh cifr v arifmeticheskih vychisleniyah. Znachenie scale mozhet byt' ustanovleno v velichinu, raspolozhennuyu v verhushke steka, s pomoshch'yu komandy k. Dlya togo, chtoby zanesti znachenie scale v stek, ispol'zuetsya komanda K. scale dolzhno byt' ne men'she nulya i men'she 100. Pri opisanii kazhdoj arifmeticheskoj operacii budet pokazano tochnoe vliyanie scale na vychisleniya. - 24 - 2.2.4. Slozhenie i vychitanie Tochnosti predstavleniya dvuh chisel sravnivayutsya, i k chislu s men'shej tochnost'yu dobavlyayutsya posleduyushchie nuli dlya togo, chtoby uravnyat' tochosti oboih chisel. Esli raznica toch- nostej nechetna, to chislo s men'shej tochnost'yu umnozhaetsya na 10. Tochnost' rezul'tata ustanavlivaetsya zatem v velichinu, ravnuyu bol'shej iz dvuh tochnostej. Vychitanie proizvoditsya invertirovaniem znaka chisla dlya togo, chtoby vychitanie zamenit' na slozhenie. Slozhenie vypolnyaetsya cifra za cifroj, nachinaya s mladshih razryadov k starshim. Perenos rasprostranyaetsya obychnym sposo- bom. Rezul'tiruyushchee chislo beretsya v kanonicheskoj forme, pri kotoroj mozhet potrebovat'sya ubrat' lidiruyushchie nuli ili, dlya otricatel'nyh chisel, zamenit' starshie cifry "99 -1" na "-1". V lyubom sluchae cifry, kotorye ne popadayut v interval 0-99, dolzhny byt' privedeny v etot interval, putem rasprostraneniya perenosa ili zaimstvovaniya iz drugih razryadov. 2.2.5. Umnozhenie Tochnosti dvuh operandov zapominayutsya i otbrasyvayutsya. Oba operanda delayutsya polozhitel'nymi. Zatem vypolnyaetsya umnozhenie sposobom cifra za cifroj. Pervoe chislo umnozhaetsya na kazhduyu cifru vtorogo chisla, nachinaya s mladshego razryada. Promezhutochnye rezul'taty nakaplivayutsya v chastnye summy, sum- mirovanie kotoryh daet okonchatel'nyj rezul'tat. Rezul'tat zanositsya v kanonicheskoj forme, a ego znak opredelyaetsya iz znakov operandov. Tochnost' rezul'tata ustanavlivaetsya ravnoj summe toch- nostej dvuh operandov. Esli eta tochnost' bol'she, chem znache- nie vnutrennego registra scale, a takzhe bol'she, chem tochnosti oboih operandov, to tochnost' rezul'tata ustanavlivaetsya v maksimal'noe iz etih treh znachenij. 2.2.6. Delenie Tochnosti oboih operandov otbrasyvayutsya. U delimogo otb- rasyvayutsya lishnie cifry ili dobavlyayutsya nedostayushchie nuli, chtoby sdelat' tochost' rezul'tata celogo deleniya ravnoj zna- cheniyu vnutrennej peremennoj scale. Znaki zapominayutsya i otbrasyvayutsya. Delenie vypolnyaetsya takzhe, kak esli by ono vypolnyalos' vruchnuyu. Vychislyaetsya raznica dlin oboih chisel. Esli deli- tel' dlinnee delimogo, vozvrashchaetsya znachenie nol'. V protiv- nom sluchae dve starshie cifry delimogo delyatsya na starshuyu cifru delitelya. Rezul'tat etogo dejstviya ispol'zuetsya kak pervaya (starshaya) cifra chastnogo. Probnaya cifra umnozhaetsya na delitel', i rezul'tat vychitaetsya iz delimogo, i dlya - 25 - polucheniya ocherednoj cifry chastnogo process povtoryaetsya do teh por, poka ostatok delimogo ne stanet men'she delitelya. V konce processa cifry chastnogo perevodyatsya v kanonicheskuyu formu i, esli eto neobhodimo, proishodit rasprostranenie perenosa. Znak opredelyaetsya iz znakov oboih operandov. 2.2.7. Nahozhdenie ostatka Dlya nahozhdeniya ostatka vyzyvaetsya programma deleniya, i vypolnyaetsya delenie tak, kak eto bylo opisano v predydushchem razdele. Vozvrashchaemyj rezul'tat - est' ostatok ot deleniya posle zaversheniya processa deleniya. Znak ostatka imeet takoj zhe znak, chto i delimoe. Tochnost' ostatka ustanavlivaetsya v maksimal'nuyu iz velichin tochnosti delimogo i tochnosti chast- nogo plyus tochnost' delitelya. 2.2.8. Vychislenie kvadratnogo kornya Iz operanda ubiraetsya tochnost'. Esli neobhodimo, dobavlyayutsya nuli dlya togo, chtoby poluchit' v rezul'tate tre- buemuyu tochnost'. Dlya vychisleniya ispol'zuetsya metod N'yutona s posleduyushchej aproksimaciej po pravilu: x[n+1] = 1/2 (x[n] + y / x[n]) Nachal'noe predpolozhenie beretsya iz rascheta, chto kvadratnyj koren' raven starshim dvum cifram. 2.2.9. Vozvedenie v stepen' Razreshaetsya vozvedenie v stepen' tol'ko s celym pokaza- telem stepeni. Esli pokazatel' stepeni raven nulyu, to rezul'tat raven edinice. Esli pokazatel' stepeni otricate- len, to on delaetsya polozhitel'nym, a na osnovanie delitsya edinica. SHkala rezul'tata otbrasyvaetsya. Celyj pokazatel' stepeni rassmatrivaetsya kak dvoichnoe chislo. Osnovanie posledovatel'no vozvoditsya v kvadrat, a rezul'tat poluchaetsya kak proizvedenie rezul'tatov etih voz- vedenij osnovaniya, kotorye sootvetstvuyut poziciyam v dvoichnom predstavlenii pokazatelya stepeni. CHtoby sdelat' tochnost' rezul'tata takoj zhe, kak i pri umnozhenii (kotoroe na samom dele i vypolnyalos'), otbrasyvaetsya neobhodimoe kolichestvo cifr. 2.2.10. Perevod vvodnyh chisel i vhodnaya sistema schisleniya CHisla preobrazuyutsya vo vnutrennee predstavlenie po mere ih schityvaniya. Tochnost' hranitsya s chislom i yavlyaetsya koli- chestvom desyatichnyh cifr posle zapyatoj. Pered otricatel'nymi chislami stavitsya znak "_" (podcherk). SHestnadcatirichnye cifry A-F sootvetstvuyut chislam 10-15, nezavisimo ot vhodnogo osnovaniya sistemy schisleniya. Dlya izmeneniya osnovaniya sistemy schisleniya vvodimyh chisel ispol'zuetsya komanda i. |ta - 26 - komanda izvlekaet iz steka, usekaet rezul'tiruyushchee chislo do celogo i ispol'zuet ego kak osnovanie sistemy schisleniya dlya posleduyushchego vvoda chisel. Pervonachal'no vhodnaya sistema schisleniya - desyatichnaya. Komanda I zanosit znachenie osnova- niya sistemy schisleniya vvodnyh chisel v stek. 2.2.11. Vyvodnye komandy Komanda p vyzyvaet pechat' verhushki steka. Pri etom ver- hushka steka ne izvlekaetsya. Dlya togo, chtoby vyvesti soderzhi- moe vseh vnutrennih registrov i vsego steka, ispol'zuetsya komanda f. Dlya togo, chtoby izmenit' osnovanie sistemy schis- leniya vyvodnyh chisel, ispol'zuetsya komanda o. Po etoj komande izvlekaetsya verhushka steka, usekaetsya do celogo i eto znachenie ispol'zuetsya v dal'nejshem kak osnovanie sistemy schisleniya dlya vyvodnyh chisel. Sistema schisleniya dlya vyvod- nyh chisel pervonachal'no ustanovlena v desyatichnuyu. Komanda O zanosit znachenie osnovaniya sistemy schisleniya dlya vyvodnyh chisel v stek. 2.2.12. Vyhodnoj format i vyhodnaya sistema schisleniya Vhodnaya i vyhodnaya sistemy schislenij vliyayut tol'ko na interpretaciyu chisel pri vvode i vyvode, no ne vliyayut na arifmeticheskie vychisleniya. Bol'shie chisla vyvodyatsya po 70 cifr na stroke. Esli stroka imeet prodolzhenie, to na eto ukazyvaet znak \ (obratnaya kosaya cherta) v konce stroki. Mozhno rabotat' s lyubymi sistemami schisleniya, hotya ne vse dostatochno celesoobrazny. V chastnosti, naprimer, polezna sistema schisleniya s osnovaniem 1000, pri kotoroj vyvodimye chisla pechatayutsya gruppami po tri cifry. Vos'merichnaya i shestnadcatirichnaya sistemy schisleniya ispol'zuyutsya dlya pere- voda v i iz etih sistem schisleniya. 2.2.13. Vnutrennie registry CHisla ili cepochki mogut byt' zapomneny vo vnutrennih registrah ili zagruzheny v stek iz registrov, ispol'zuya komandy s i l. Po komande sx proishodit izvlechenie zacheniya verhushki steka i zapominanie ego v registre x. x mozhet byt' lyubym simvolom. Po komande lx proishodit zapis' znacheniya registra x v verhushku steka. Komanda l ne izmenyaet soderzhi- moe registra, a komanda s ego izmenyaet. 2.2.14. Stekovye komandy Komanda c chistit stek. Komanda d dubliruet chislo v ver- hushke steka. Komanda z zanosit v stek dlinu steka. Komanda X zamenyaet chislo v verhushke steka ego tochnost'yu. Komanda Z zamenyaet verhushku steka ego dlinoj. - 27 - 2.2.15. Opisaniya i vyzovy funkcij Stroka iz simvolov v kode KOI-8, zaklyuchennaya v kvadrat- nye skobki, zanositsya v stek. Komanda q prekrashchaet rabotu ili, pri vypolnenii po stroke, umen'shaet uroven' vlozhennosti na dva. 2.2.16. Vnutrennie registry - programmirovanie na dc Dlya togo, chtoby programmirovat', rabotaya s programmoj dc, mozhno pol'zovat'sya komandami zagruzki i zapominaniya l i s, zapominaniya strok "[]", komandoj vypolneniya x, komandami proverki <&lt;, >&gt;, =, !<&lt;, !>&gt;, != Komanda x rassmatrivaet ver- hushku steka kak komandu programmy dc i vypolnyaet ee. Komandy proverki sravnivayut dva verhnih elementa steka, i, esli uslovie spravedlivo, to vypolnyaetsya registr x, kotoryj sleduet za operaciej otnosheniya. Naprimer, dlya togo, chtoby napechatat' chisla 0-9, nado nabrat' sleduyushchuyu programmu: [lip1+ si li10>&gt;a]sa 0si lax 2.2.17. Stekovye registry i massivy Sleduyushchie komandy byli razrabotany dlya ispol'zovaniya ne lyud'mi, a kompilyatorom. Oni ohvatyvayut stekovye registry i massivy. Krome steka, s kotorym rabotayut komandy, dc imeet takzhe neskol'ko individual'nyh stekov dlya kazhdogo registra. |ti registry operiruyut s komandami S i L. Sx zanosit verhnee znachenie glavnogo steka v stek dlya registra x. Lx izvlekaet znachenie iz steka registra x i zanosit rezul'tat v osnovnoj stek. Komandy s i l takzhe rabotayut s registrami, no ne kak so stekami. l ne izmenyaet verhushku registrovogo steka, a s razrushaet to, chto tam nahodilos' ranee. K komandam dlya raboty s massivami otnosyatsya : i ;. :x izvlekaet znachenie steka i ispol'zuet ego kak indeks k mas- sivu x. Sleduyushchij element steka zapominaetsya v elemente mas- siva x s etim indeksom. Indeks dolzhen byt' bol'she nulya i men'she 2047. ; - eto komanda dlya zagruzki osnovnogo steka iz massiva x. Znachenie verhushki steka - eto indeks v massive x, otkuda dolzhna proizojti zagruzka. 2.2.18. Prochie komandy Komanda ! interprtiruet ostatok stroki kak komandu DEMOS i peredaet ee sisteme dlya vypolneniya. Drugaya komanda kompilyatora - Q. |ta komanda ispol'zuet verhushku steka kak chislo urovnej rekursii, kotoroe nado propustit'. - 28 - 2.3. Vybor reshenij Osnovnoj prichinoj ispol'zovaniya raspredelitelya dinami- cheskoj pamyati bylo to, chto programma obshchego naznacheniya mogla byt' (i byla na samom dele) ispol'zovana dlya mnozhestva dru- gih zadach. Esli zaranee ne izvestno, kakova budet dlina cepochki, raspredelitel' prinimaet znachenie dlya vvoda i kom- pilyacii (t.e. komandy, zaklyuchennye v kvadratnye skobki [...]). Rezul'tat byl takov, chto pri skromnoj stoimosti vo vremya vypolneniya vse soobrazheniya po povodu raspredeleniya cepochek i razmerov cepochek byli udaleny iz ostavshejsya chasti programmy, i otladka stala bolee legkoj. Ispol'zuemyj metod tratil primerno 25% dostupnoj pamyati. Vybor chisla 100 kak osnovaniya sistemy schsleniya dlya vnutrennej arifmetiki po-vidimomu ne imeet yavnogo preimu- shchestva. Krome togo, osnovanie sistemy schisleniya ne dolzhno prevyshat' 127 iz-za apparatnyh ogranichenij; i pri stoimosti 5% pamyati otladka stala mnogo legche, a desyatichnyj vyvod sushchestvenno bystree. Prichina sozdaniya arifmetiki stekovogo tipa - dat' voz- mozhnost' vsem komandam dc ot slozheniya do vypolneniya podprog- ramm po-sushchestvu vypolnyat'sya odinakovo. Rezul'tatom yavilos' znachitel'noya stepen' logicheskogo razdeleniya konechnoj prog- rammy na moduli s ochen' malen'koj svyaz'yu mezhdu nimi. Iz-za nedostatka vzaimodejstviya mezhdu shkaloj i osnova- niyami sistem schisleniya razumnym bylo obespechit' ponimaemost' sposoba vypolneniya posle izmeneniya shkaly ili osnovaniya, kogda chisla uzhe byli vvedeny. Rannyaya versiya, kotoraya imela glbal'nye ponyatiya shkaly i osnovaniya sistemy schisleniya, ne byla horosho razrabotana. Esli znachenie scale interpretirova- los' v tekushchej vvodnoj ili vyvodnoj sisteme schisleniya, to izmenenie sistemy schisleniya ili shkaly v seredine vychisleniya mog vyzvat' nepravil'nuyu interpretaciyu rezul'tatov. Tekushchaya shema imeet to preimushchestvo, chto znachenie vhodnogo i vyhod- nogo osnovanij sistem schisleniya ispol'zuetsya tol'ko dlya vvody i vyvoda sootvetstvenno, i ignoriruetsya vo vseh drugih dejstviyah. Znachenie shkaly ne ispol'zuetsya dlya lyubyh sushchest- vennyh celej v lyuboj chasti programmy, a ispol'zuetsya tol'ko dlya togo, chtoby predotvratit' uvelichenie kolichestva desyatich- nyh znakov za granicy tekushchej tochnosti. Razumnym resheniem vybora shkaly rezul'tatov arifmetiches- kih dejstvij bylo by to, chto pri yavnom ukazanii pol'zovatelya ni odna znachashchaya cifra ne dolzhna byt' otbroshena. Dejstvi- tel'no, esli pol'zovatel' hochet slozhit' chisla 2.5 i 3.1415, to kazhetsya razumnym dat' emu rezul'tat 5.6415, poskol'ku v ostal'nyh znachashchih cifrah net neobhodimosti. S drugoj storony, pri umnozhenii i vozvedenii v stepen' vyrabatyvaetsya rezul'tat s kolichestvom cifr bol'shim, chem u - 29 - operandov, i kazhetsya razumnym dat' kak mimnimum kolichestvo cifr v operandah, a ne bol'she, esli tol'ko pol'zovatel' ne ukazhet yavno kolichestvo cifr, opredeliv znachenie scale. Kvadratnyj koren' mozhet byt' vychislen tak zhe, kak i umnozhe- nie. Vpolnenie deleniya daet proizvol'noe kolichestvo cifr, i ne tak prosto predpolozhit' pozhelaniya pol'zovatelya otnosi- tel'no kolichestva cifr. V etom sluchae pol'zovatel' dolzhen opredelit' znachenie scale. SHkala ostatka vybrana dlya togo, chtoby mozhno bylo vosstanovit' delimoe iz chastnogo i ostatka. |to legko vypolnit': ni odna cifra ne otbrasyvalas'. - 30 - SODERZHANIE ANNOTACIYA ......................................... 2 1. VVEDENIE .......................................... 2 2. INTERAKTIVNYJ KALXKULYATOR bc ...................... 3 2.1. Prostye dejstviya s celymi chislami ............... 3 2.2. Osnovaniya sistem schisleniya ...................... 4 2.3. Masshtabirovanie ................................. 6 2.4. Funkcii ......................................... 7 2.5. Indeksirovannye peremennye ...................... 8 2.6. Upravlyayushchie operatory ........................... 9 2.7. Nekotorye detali ................................ 11 2.8. Tri vazhnye veshchi ................................. 12 2.9. Detal'noe opisanie .............................. 13 2.9.1. Oboznacheniya ................................... 13 2.9.2. Znaki ......................................... 13 2.9.2.1. Kommentarii ................................. 13 2.9.2.2. Identifikatory .............................. 13 2.9.2.3. Klyuchevye slova .............................. 13 2.9.2.4. Konstanty ................................... 14 2.9.3. Vyrazheniya ..................................... 14 2.9.3.1. Prostye vyrazheniya ........................... 14 2.9.3.1.1. Imenovannye vyrazheniya ..................... 14 2.9.3.1.2. Vyzovy funkcij ............................ 14 2.9.3.1.3. Konstanty ................................. 15 2.9.3.1.4. Kruglye skobki ............................ 15 2.9.3.2. Unarnye operacii ............................ 15 2.9.3.3. Operaciya vozvedeniya v stepen' ............... 16 2.9.3.4. Operacii gruppy umnozheniya ................... 16 2.9.3.5. Operacii gruppy slozheniya .................... 16 2.9.3.6. Operatory prisvaivaniya ...................... 17 2.9.4. Otnosheniya ..................................... 17 2.9.5. Klassy pamyati ................................. 17 2.9.6. Operatory ..................................... 18 2. INTERAKTIVNYJ STEKOVYJ KALXKULYATOR dc ............. 20 2.1. Opisanie sintaksisa ............................. 20 2.2. Detal'noe opisanie .............................. 22 2.2.1. Vnutrennee predstavlenie chisel ................ 22 2.2.2. Raspredelitel' pamyati ......................... 23 2.2.3. Vnutrennyaya arifmetika ......................... 24 2.2.4. Slozhenie i vychitanie .......................... 25 2.2.5. Umnozhenie ..................................... 25 2.2.6. Delenie ....................................... 25 2.2.7. Nahozhdenie ostatka ............................ 26 2.2.8. Vychislenie kvadratnogo kornya .................. 26 2.2.9. Vozvedenie v stepen' .......................... 26 2.2.10. Perevod vvodnyh chisel i vhodnaya sistema schisle- niya ........................................... 26 - 31 - 2.2.11. Vyvodnye komandy .............................. 27 2.2.12. Vyhodnoj format i vyhodnaya sistema schisleniya .. 27 2.2.13. Vnutrennie registry ........................... 27 2.2.14. Stekovye komandy .............................. 27 2.2.15. Opisaniya i vyzovy funkcij ..................... 28 2.2.16. Vnutrennie registry - programmirovanie na dc .. 28 2.2.17. Stekovye registry i massivy ................... 28 2.2.18. Prochie komandy ................................ 28 2.3. Vybor reshenij ................................... 29 - 32 -