Vlákno názorů k článku Fixed point arithmetic od Jakub Hegenbart - Ha, to zavání agitkou Mooreova „extremely-early bindingu“ :-)...
-
Ha, to zavání agitkou Mooreova „extremely-early bindingu“ :-) Přijde mi, na že řešení přesnosti výpočtů a minimální postačující reprezentace se dneska kašle... :-/ Což je škoda, moc jsem do toho zatím nenakoukl, ale je to zajímavá disciplína. Dneska se na hromadu věcí vrhá hrubá síla. Ne, že by to nebylo v mnoha případech ospravedlnitelné, ale přijde mi, že dneska už nikoho nenapadne fixed-point řešení zkusit tam, kde by přišlo vhod. (A nedávno jsem se v téhle domněnce trošku utvrdil, když jsen někoho přistihl, jak chce alpha blending dvou 24b barev řešit (v Delphi) rozkladem hodnoty na složky assembleru a pak míchacím algebraickým vzorcem v doublu... (???)) -
Honza (neregistrovaný)Neřekl bych, že se na analýzu minimální postačující reprezentace kašle. Myslím si, že tenhle dojem máte proto, že dneska programuje plno lidí, kteří už ani nevědí, jak počítač nebo procesor ve skutečnosti funguje.
Osobně se živím vývojem hardware, především pro digitální zpracování obrazových signálů a tam je podrobná analýza numerické reprezentace a jejího vlivu na algoritmus velmi důležitá součást návrhu. On je totiž podstatný rozdíl jestli implementace algoritmu spolkne 200K nebo 20M ekvivalentních hradel. -
Obavam se, ze hodne lidi co pise software na efektivitu na teto urovni kasle. Nemusi jit jen o float/double -- podivejte se kolik lidi pouziva "int" na ulozeni stavu 0/1 (vrcholem pak je nekolik takovych "int" v ramci jedne struktury na misto jednoho a bitovych operaci nad nim) mno a bitova pole najdete dnes uz snad jen v ucebnicich C-ecka.
-
Pavel TišnovskýZlatý podporovatelOno to pro procesor, alespon pokud se bavime o x86, vyjde +- nastejno. Pokud ma totiz zjistit hodnotu nejakeho bitu v bitovem poli, muze pouzit napriklad instrukci TEST, pro slozitejsi operace potom BT, BTS, BTR a BTC. Podobne je to u intu pouziteho jako boolean, akorat to nastavovani do jednicky je slozitejsi (reset do nuly ne, to udela treba XOR nebo SUB).
Neco jineho je to u jednocipu, ktere mnohdy maji prave "bitove" pameti (spis registrove sady). Tam by se za int pouzity misto boolean melo strilet... -
Pavel TišnovskýZlatý podporovatelV pripade pouheho BT je to opravdu o 1-2 takty delsi, i kdyz nechapu proc. Ale v pripade kombinace, tj. spolu s resetem/nastavenim/negaci bitu uz se to vice nez srovna. V kazdem pripade se stejne v realu pouzivaji stare zname AND, OR, XOR, i kdyz u nich se musi ukladat i bitova maska, takze velikost kodu narusta.
-
Miloslav Ponkrác (neregistrovaný)Takhle už dávno rychlost instrukcí počítat nejde. Tak to šlo možná kdysi, ale dnes už to dávno neplatí. Dnešní procesory jsou mnohem složitější a odvozovat rychlost na nějakém taktování je už dávno pasé. Takže v reálu to dopadne tak, že budete rád, když jakákoli kombinace BT byť s resetem, apod.. bude jenom několikanásobně pomalejší, než třeba TEST, nebo AND, OR, XOR. A znovu zdůrazňuji, pokud instrukce BT a spol. budou jen několikanásobně pomalejší, gratulujte si k dobrému výsledku. A i rychlosti různě zapsaných sekvencí s AND, OR, XOR a TEST se mohou lišit rychlostí provádění i několikanásobně pro kód, který dělá to samé.
Dneska optimalizovat assembler moderních procesorů na rychlost je machrovina, kterou zvládá jen málokdo. Mnohdy mnohem delší kód může proběhnout za zlomek času, než třeba třikrát kratší kód s mnohem méně instrukcemi. -
Pavel TišnovskýZlatý podporovatelAsi máte pravdu, já jsem s optimalizací assembleru skončil u prvních Pentií, protože mě nebavilo složitě zjišťovat, která pipeline bude za daných okolností tu instrukci provádět. A to měla Pentia jedničky pouze dvě pipeliny (a to ještě nesymetrické), dneska to bude asi pěknej humus, tak to nechávám na překladači (a stejně moc nevěřím, že to zvládne, snad kromě Inteláckých děl). Otázkou však je, proč by měly být instrukce typu BTx pomalejší než AND, OR, XOR a TEST, vždyť pro ALU je to vždycky věc jednoho cyklu. Jinak počet cyklů by měl udávat nejhorší možný čas, kdy běží pouze jedna pipelina, ne?
-
Miloslav Ponkrác (neregistrovaný)Otázka proč by měla být BT pomalejší, když pro ALU je to jedna instrukce je stejné jako proč je pro mě těžší říct větu svahilsky, než anglicky, vždyť pro hlasové ústrojí je to plus mínus stejná činnost.
Je to složitější, věřte mi. Existuje vícero důvodů proč je BT pomalejší a jediné co Vám mohu zaručit je, že v každém dalším procesoru, který Intel, či AMD vyrobí bude poměr rychlostí provádění BT a spol. versus AND/OR/XOR/TEST/rotace ještě více nepříznivější.
Jinak překladač dnes vygeneruje rychlejší kód, než průměrný assemblerista a to se ani nemusí moc snažit. Musíte ovšem mít dobrý překladač (to znamená vylučuje se gcc, borland, bere se v úvahu ms a především intel). -
Chtěl jste asi říct "dobrý překladač specializovaný na Intel". U Borlandu to chápu, ten má výhodu spíš v rychlosti kompilace než v rychlosti výsledného kódu. ;-) Ale GCC je moloch, který musí brát ohledy na hromadu platforem. (Což mi připomíná, že mě stále čeká instalace VAXu. :-D) Nejsem si jistý, do jaké míry to ovlivňuje kvalitu x86 kódu, ale přinejmenším tomu jeho tvůrci nevěnují všechny prostředky. Microsoft si s tímhle hlavu lámat nemusí. Uvidíme, jak s tím zacloumá budoucnost a nová IR. Já jsem za svobodný překladač docela vděčný, i když třeba není v některých ohledech tak kvalitní, jako jiné. :-)
BTW, to je zvláštní, já měl za to, že TEST trvá stejně dlouho, jako BT, na Athlonu je obojí DirectPath instrukce s latencí 1, a že jen BT mem16/32 je VectorPath (což není dobrý nápad ve výkonnostně kritické části...). A myslím, že těch dobrých assembleristů bude docela dost. Koneckonců, toho optimalizovaného kódu zas tolik zapotřebí nebude. -
Já myslím, že to dneska platí o všech modernějších procesorech, nejenom o Intelech. To, že GCC je moloch, který musí brát ohledy na hromady platforem mě jako programátora přeci nezajímá. Já jsem za free překladač taky vděčný, ale třeba pod Windows je MS překladač taky free :-)
Ono v assembleru není proč psát (bavíme se o x86). -
Miloslav Ponkrác (neregistrovaný)Protože je free jako zdarma, není free jako zdrojáky. Až budu programovat gcc, tak rozhodně nebudu její nedostatky ve stylu, že špatně optimnalizuje vydávat za klad, ale za chybu. Nechápu, proč by mé programátorství se mělo snižovat tím, že používám kvalitní kompilátory tam, kde to jde.
-
Mikuláš Patočka (neregistrovaný)GCC provádí optimalizace na svém interním mezikódu, ale neprovádí skoro žádné optimalizase na vygenerovaném assembleru (leda scheduling). Takže pak například z následujícího kódu
unsigned long long x(unsigned lo, unsigned hi)
{
return ((unsigned long long)hi << 32) | lo;
}
vyleze v gcc 4.1.0 tohle:
pushl %ebx
xorl %edx, %edx
movl 12(%esp), %eax
movl 8(%esp), %ecx
popl %ebx
movl %eax, %edx
movl $0, %eax
orl %ecx, %eax
ret -
Pavel TišnovskýZlatý podporovatelA nebyly na tom nahodou predchozi verze GCC (myslim tim trojkovou radu) s optimalizacemi lepe? Co jsem zkousel, tak z rozumne dlouhe funkce - tj. treba dve zanorene smycky s nejakym rozeskokem - dava gcc docela dobry kod. Zato pri zpracovani obrazu je to dost bida, tady je opravdu nejlepsi Intelacky prekladac, ktery dokaze smycky rozepsat tak, ze dost veci jede paralelne (gcc se zasekava a rozumny unrolling smycek jsem z nej nedostal)
-
developer (neregistrovaný)Paralelne ako paralelne. Sam som bol prekvapeny, ako dokaze napr. amd spracovat paralelne vzajomne kolidujuce instrukcie. Procesory (resp. ich navrhari) to dnes beru skor statisticky. Ak sa casto pouziva kombinacia mov eax, [mem]; add eax, daco; mov [mem], eax; tak to proste zoptimalizuju. Napr. AMD ma na to taky tool, kde simuluje vykonavanie instrukcii v pipelines, toto konkretne spravi za jeden takt:) S kolegom sme boli velmi prekvapeni, ked rucne zoptimalizovany (akoze sparalelizovany) asm bol pomalsi ako neoptimalizovany a so zavislostami. Jedine co sa dnes mozno oplati optiamlizovat su SSE instrukcie, kde mate (zatial) istotu ze je to len jedna pipeline a do nej sa to rve serializovane :)
-
Pavel TišnovskýZlatý podporovatelJá chápu (resp. jsem se s tím už dávno smířil), že instrukční sada x86 má k dokonalosti _dost_ daleko, takže fakt, že BTx je pomalejší než AND/OR... beru (stejně jako nelogický a na sebe navrstvený formát instrukcí). Šlo mě však o to, zda se v principu jedná o nějakou složitější operaci. Myslím si, že se v návrhu číslicových obvodů docela vyznám a opravdu mi nepřipadne, že by BTx měly být nějak složitější instrukce, vždyť je to jednodušší než rotace, které také svého času (286?) trvaly neskutečně a nelogicky dlouho (asi Intel nedokázal udělat pořádný barrell shifter).
Ostatně na jiných architekturách se jedná o docela běžné operace, někde (jednočipy) jsou dokonce podporovány i bitové mapy. -
Mikulas Patocka (neregistrovaný)... a bude hur, na Pentiu 4 je pomalejsi INC register a DEC register (2 mikroinstrukce) nez ADD/SUB register, 1 (1 mikroinstrukce). Duvodem pro toto zpomaleni jsou taky flagy --- INC a DEC nemeni flag C, ADD a SUB ano.
Vlivem toho kompilatory prestaly instrukce INC a DEC generovat a v dalsi verzi procesoru si treba Intel rekne, ze kdyz jsou nepouzivane, tak je jeste vic zpomali.
BTW. ty shifty byly na prvnich verzich Pentia 4 taky velmi pomale (4 tiky) --- nebyly totiz v ALU (ktera bezela na dvojnasobne frekvenci), ale provadela je MMX jednotka. Od Prescotta vyse Intel snizil frekvenci ALU na frekvenci procesoru a pridal do ni shifty. -
Pavel TišnovskýZlatý podporovatelNo, přiznám se, že tyto "optimalizace" moc nechápu. INC, DEC apod. jsou instrukce velmi krátké (svým opkódem), takže kvůli změně na ADD a SUB v moderních kompilátorech se bude strojový kód programů prodlužovat. To přece pěkně rozchodí instrukční chache nehledě na to, že INC a DEC jsou (spolu JZ/JNZ za nimi) ideální instrukce pro predikci skoků.
Takže výsledkem bude sada "vybraných" rychlých instrukcí, které budou mít dlouhé opkódy (ty Intel kvůli zpětné kompatibilitě nebude měnit) a cache bude pěkně vypadávat podobně, jako na RISCích :-))) Benchmarky (ty blbé, co pojedou samotné) budou házet vysoká čísla a při reálném nasazení, kdy se přepínají stovky procesů, to bude pěkně pomaličké...
Shifty byly hlavně pomalé třeba na 286, přesněji řečeno shifty o víc nez jeden bit. Tam se vyplácelo provést několikrát za sebou rol, než jednou rol cx. Z dnešního pohledu (pipelining, více ALU atd.) je to samozřejmě nesmysl, ale tehdá to opravdu fungovalo. -
Miloslav Ponkrác (neregistrovaný)Tyhle optimalizace jsou velice logické. Chcete-li něco udělat rychlé, nemůžete udělat rychlé všechno. Procesor je dneska víc software plus nějaká malá část jsou vlastní výkonné jednotky.
Jinak klídek. INC a DEC pro registry jsou a byly stejně rychlé jako ADD SUB, takže Vaše skoky a cykly jsou ok. INC a DEC pro práci s pamětí byla o jeden takt delší a to ještě jen někdy, než ADD a SUB, dostal jste od diskutující před Vámi neúplné informace.
Dnešní procesory jsou RISCy!!! I když mají CISCovou sadu. -
Mikuláš Patočka (neregistrovaný)INC a DEC s registrem mají na Pentiu 4 dvě mikroinstrukce, ale výsledná hodnota registru je vidět už po první mikroinstrukci. Druhá mikroinstrukce nejspíš opraví flagy.
Pokud uděláte test, který je limitovaný dobou výpočtu ALU (např. pořád se opakující INC EAX), tak naměříte, že je tam jedno, jestli je tam INC nebo ADD, protože druhá mikroinstrukce INC se provede paralelně s první mikroinstrukcí následujícího INC.
Pokud však uděláte test limitovaný propustností mikroinstrukcí (např. INC po sobě s různými registry), tak zjistíte, že je to dvakrát rychlejší, když tam místo INC dáte ADD. -
Pavel TišnovskýZlatý podporovatelPorad to imho zbytecne zpomaleni jeste nechapu :-))) Jak o tom premyslim (uvedumuju si, ze ve skutecnosti to bude o dost komplikovanejsi):
1. Registr FLAGS je vlastne pouze sada jednobitovych klopnych obvodu, ktere vzajemne nemaji mnoho spolecneho - kazdy se nastavuje jinym zpusobem, nektery z ALU, jiny treba z radice preruseni.
2. Takze bity CARRY, ZERO a OVERFLOW jsou imho klopne obvody, ja bych je udelal asi jako klopnaky typu D, samozrejme s clockem.
3. Z toho vyplyva, ze pokud nejaka instrukce (INC/DEC) nechce nejaky z techto bitu nastavovat, staci proste jednim hradlem AND zablokovat clock a do daneho klopneho obvodu se nic nezapise.
Kde je ta komplikace? Vzdyt cela architektura x86 je hroznej bastl, kde jsou tisice zbytecnych obvodu jenom pro zachovani opravdu zbytecnych instrukci typu BOUND, ENTER a LEAVE.
Jinak mam jeste maly dotaz: co to znamena, ze dnesni procesory jsou RISCy? To se dneska rozlisuje podle toho, co procesor dela uvnitr? Myslel jsem, ze se bere do uvahy instrukcni sada, protoze jinak je RISCem prakticky i M68000 a deleni prestava mit smysl. -
Mikulas Patocka (neregistrovaný)Je to uplne jinak. Ve skutecnosti tam zadny registr vyhrazeny na flagy neni. Pentium 4 ma 128 obecnych registru. Tyto registry muzou byt volne nebo alokovane na nektery z registru architektury (E[ABCD]X, ESP, EBP, ESI, EDI, FLAGS) nebo alokovane na docasne registry (napr. pri ADD DWORD [1234], 5).
Hodnota alokovanych registru se nikdy nemeni. Kdyz se provede instrukce, co do nektereho registru zapise, tak se alokuje novy registr a nova hodnota se do nej ulozi. Toto umoznuje out-of-order execution. Napriklad pri kodu:
MUL EBX
JC label
MOV EAX, [1234]
MOV [1238], EAX
ADD EAX,3
se zacne provadet MUL, JC a MOV EAX,[1234] stoji, protoze zavisi na jeho vysledku, a paralelne se zacne provadet MOV [1238], EAX (protoze tato instrukce alokuje EAX v novem registru, tak nijak neposkodi predchozi instrukce). Ten ADD EAX se dokonci drive nez predchozi MOV EAX, [1234], ale nevadi to, protoze kazda z techto mikroinstrukci pouziva jiny registr.
Pokud se po skonceni MUL zjisti, ze priznak C je nastaveny a JC se melo provest, tak se pouze zapomene soucasna tabulka alokace registru a pouzije se tabulka platna v bode te instrukce JC, cimz se zpusobi, ze procesor zapomene, ze instrukce za JC vubec provadel.
Na flagy se tenhle princip pouziva stejne jako na ostatni registry, napriklad ve vyse popsanem pripade jsou tam dve verze flagu, jedna po skonceni MUL a druha po skonceni ADD.
Pokud instrukce INC flag C nemeni, tak vznikne problem, teto instrukci nestaci alokovat novy registr na flagy a zapsat tam vysledek (jako to dela ADD), musi mit jako vstup dva registry (predchozi flagy a hodnotu) a zapsat dva registry (nove flagy a hodnotu). Na PentiuPro se jim jeste se specialnim hardwarem na tohle chtelo piplat (INC tam zere pouze 1 mikroinstrukci), na Pentiu 4 uz ne.
Jinak si muzes precist dokument na http://www.agner.org/assem/
tam jsou do detailu popsane vnitrnosti procesoru, je to asi nejlepsi dokument na toto tema. Neco se taky da vycist z optimalizacniho manualu intelu, ale tam je toho min. -
Pavel TišnovskýZlatý podporovatelDekuju za vysvetleni i za odkaz (to PDFko vypada dost dobre), je videt, ze architektura P3 a P4 se oproti drivejsku dost zmenila, ale asi to nebude na skodu (kdyz se teda budou snazit tvurci prekladacu a zrovinka Ty do toho taky trosku delas ne? :-)
Ted uz tu komplikaci s priznaky chapu; zajimave je, ze takova 65C02 (pouzita v osmibitovem Atarku) mela INCy a DECy reseny tak, ze nastavovala taky vic priznaku, samozrejme vcetne ZERO. -
Mikulas Patocka (neregistrovaný)BTW. ty zbytecne obvody na zachovani BOUND, INTO, ENTER a LEAVE tam nejsou. Kdyz se nejaka takova instrukce nalezne, tak se proste procesor zastavi a zacne se provadet mikrokod. (leda LEAVE je implementovana trochu efektivne, to je totez jako MOV ESP, EBP; POP EBP). Takovehle instrukce pouze zerou RAM s ulozenym mikrokodem, na procesor nemaji vliv. Totez plati pro CALL brany, Task state segment a podobne vymysly navrharu 286.
-
Pavel TišnovskýZlatý podporovatelTo je jasny, ze tyto instrukce uz nikdo "nedratuje", ale maji bohuzel docela kratky opcode, takze zabiraji misto necemu uzitecnejsimu (viz slozite prefixy pouzivane od 286 vys). Proste do ortogonality ma x86 DOST daleko.
-
Mikuláš Patočka (neregistrovaný)Pentium 4 nemá instrukční cache, takže tam nemá cenu snažit se minimalizovat velikost programu. Má místo toho trace cache, která ukládá dekodované mikroinstrukce (12288 mikroinstrukcí, každá má 36 bitů), takže je tam potřeba minimalizovat počet mikroinstrukcí, nikoli délu kódu. Z toho platí:
místo
PUSH EAX
PUSH EBX
(2 byty kódu, 4 mikroinstrukce)
napsat
SUB ESP,8
MOV EAX,[ESP+4]
MOV EBX,[ESP]
(8 bytů kódu, 3 mikroinstrukce)
Podobně pomůže, když se místo INC EAX (1 byte, 2 mikroinstrukce) použije ADD (3 byte, 1 mikroinstrukce).
Sekvence PUSHů je naopak výhodnější na Pentiu M, které má speciální hardware na práci se zásobníkem a PUSH tam sežere pouze 1 mikroinstrukci.
Těch instrukcí, které jsou rychlejší, když se rozepíšou na jednodušší instrukce, je na procesorech už celkem dost --- PUSHA, POPA, LOOP(N)(Z), JECXZ, BOUND, ENTER, LEAVE (pouze Intel, AMD ji má rychlou), INTO, BSR/BSF (na pentiu 1 je trvaly asi 70 tiků a bylo rychlejší ji přepsat pomocí FPU, na ostatních procesorech je rychlá), včecky řetězcové isntrukce vyjma REP MOVSD a REP STOSD (i když nevím, zda by nebyly rychlejší s pomocí SSE, neměřil jsem to). -
Pavel TišnovskýZlatý podporovatelS tim MOVSD je to takove osemetne. Pred nedavnem jsem cetl diskusi na toto tema (potrebovzal jsem co nejrychleji blitovat kontinualni bloky dat) a napriklad na AMDckach se doporucuje MOVSD nepouzivat a misto toho bud instrukce MMX nebo SSE. Na Pentiich to vsak muze byt jinak. Zkousel jsem prenos i pomoci FPU, ale to je jeste o neco pomalejsi nez MOVSD a krome toho se zdrojak hodne zeslozitil (kvuli zasobniku, ktery jsem vyuzil jako frontu).
-
Mikuláš Patočka (neregistrovaný)BT, BTR, BTS a BTC jsou pomalejší než TEST, AND, OR, XOR, protože se moc nepoužívají. Tak Intel nevidí důvod pro ně optimalizovat. BT* instrukce nastavují jinak flagy než TEST, AND, OR, XOR --- takže kdyby měly být zadrátovány rovnou v ALU, musel by do toho ALU vést signál, který říká "pozor, toto je BT* a ne TEST, nastav správně flagy". A Intel si nejspíš spočítal, že se mu nevyplatí plýtvat křemíkem na takový signál, když to v důsledku způsobí zrychlení třeba 0.01%. Nejspíš (ale nevím to jistě, jen předpokládám) jsou tyto instrukce implementovány tak, že se v ALU provede příslušný TEST, AND, OR, XOR, a pak se provede další mikroinstrukce, která opraví flagy.
Je to holt začarovaný kruh --- instrukce jsou pomalé, protože se nepoužívají, a nepoužívají se, protože jsou pomalé. -
Kdyby těch dat bylo víc, nevykompenzuje těch pár taktů navíc latence a přenosová rychlost L1 cache, L2 cache a operační paměti? A propast mezi rychlostí jádra CPU a rychlostí paměti se rozevírá...
To platí i na argument, že alignovaná data jsou lepší. Jsem fakt zvědavý, o kolik rychlejší by bylo šest po slovech perfektně alignovaných bitů než jeden bajt s flagy, když by těch struktur byly milióny...třeba nějaký oflagovaný složitý graf, co já vím. :-) -
Pavel TišnovskýZlatý podporovatelJá jsem si před několika lety také myslel, že fixed-point atd. jsou s nástupem 486DX a prvním Pentií už mrtvá věc a nic nového nepřináší. Ovšem zrovinka u nás řešíme zapeklitý problém s jednou aplikací (dodáno externistkou), která sice z hlediska algoritmu funguje dobre, ale vysledky jsou nekdy az o 20% spatne.
Nakonec jsme prisli na to, ze to je logicke: algoritmus predpoklada realna cisla, pocitac zpracovava podmnozinu cisel racionalnich a to (v pripade doublu) jeste nahustenych v okoli nuly, cim dal od nuly, tim horsi presnost. Reseni - vykaslat se na doubly, udelat poradnou analyzu hodnot zpracovavanych algoritmem, vsechno prevest na fixed-point (nebo na zlomky) a cele to naprogramovat znovu. -
Pavel TišnovskýZlatý podporovatel
Takový typický příklad, kde floating point aritmetika selhává, resp. kde se rozchází s myšlením programátora.
Kolik desetníků musíme položit na stůl, abychom získali jednu korunu? Odpověď nám dá (???) následující program:
#include <stdlib.h> #include <stdio.h> int main(void) { double x=0.0; int desetniku=0; while (x<1.0) { x+=0.1; desetniku++; printf("%d %f\n", desetniku, x); } return 0;Ještě jedna poznámka: pro dvoukorunu (jako výslednou sumu) to funguje, stejně jako tak pro dvacetníky... a teď tuto jasnou chybu v návrhu hledejte v stotisíciřádkovém programu (on totiž v tuto chvíli printf() trošku podvádí).
-
Karel (neregistrovaný)Nevim jak na ktere skole, ale nas na tyhle problemy realnych cisel vzdy upozornovali a za vyrazy typu "a == 0" se vyhazovalo od zkousky.
Navic jak tak koukam, pisete to v Jave. Java pouziva pomerne nepouzitelnou normu realnych cisel, takze to by mel byt dalsi vystrazny signal pred podobnymi konstrukcemi (pokud nekdo nevi, co je na Jave spatne, pak napriklad kladna a zaporna nula.) Poucka rika, ze se nemaji pouzivat realna cisla dokud to neni nezbytne nutne a i pak je vhodne nejprve hledat reseni pomoci celych cisel. Toto je poucka z programovacich technik a zaroven ze zakladu pocitacove grafiky. To same dale plati pro signalni analyzy, fourierovy transformace a kompresni metody. Samostatnou kapitolou jsou pak numericke metody. Po absolvovani stejnojmenneho predmetu jsem ztratil vetsinu iluzi o vhodnosti pocitacu k matematickym uloham.
Nemohu tedy souhlasit s tvrzenim "kde se aritmetika rozchazi s myslenim programatora". Mozna by pomohlo upravit ho na "kde se aritmetika rozchazi s myslenim nedouceneho programatora".
Nektere problemy realnych cisel, na ktere si vzpomenu:
1. porovnani na konkretni hodnotu nebo interval
V realnych cislech se casto objevuji hodnoty jako 0.000001 nebo 0.999998 apod. Porovnani by tedy mela byt intervalova a brat v uvahu zobrazovaci schopnost datoveho typu. Tedy napriklad:
misto "a == 1" pouzit "ABS(a - 1) < 0.0001"
misto "a < 1" pouzit "a < 0.99999"
Jina metoda, zpravidla narocnejsi ale intuitivnejsi, je prevadet podle zobrazovaci schopnosti na cela cisla (s matematickym zaokrouhlenim) a pracovat s nimi. Pokud tedy mantisa dokaze zobrazit napr. 5 cislic, pak rekneme, ze spravne zpracuje nejvyse tisiciny:
misto "a == 1" pouzit "ToInteger(a * 1000) == 1000"
misto "a < 1" pouzit "ToInteger(a * 1000) < 1"
2. omezena mantisa (rozlisovaci schopnost)
Realne cislo je uvadeno formou mantisy a exponentu, naprikla 0.025 bude uvedeno jako 2.5*10^-2. Ulozeno bude tedy napriklad cislo 25000 (mantisa) a exponent (-002). Toto se podle ruznych norem lisi, ale vzdy je tam mantisa s omezeou delkou - tedy cela cisla z intervalu 0 az napr. 99999.
Efekt A: nelze zapsat cislo 1.00001, protoze se proste nevejde do mantisy (moc dlouhe)
Efekt B: prakticky to same, ale je to mene patrne: 1 + 0.00001 != 1.00001 prave proto, ze 1.00001 nelze zapsat. Velice efektni chyba pri iteracnich vypoctech ve vypocetni geometrii.
3. Nektere formaty obsahuji zapornou nulu
4. Nektere formaty nedobre nasobi a jeste vice jich spatne deli - duvodem je, ze tyto formaty neukladaji mantisu jako BCD cislo, ale jako binarni cislo. A zkuste si napsat jako binarni cislo jednu petinu (0.2)
... atd., problemu a tedy duvodu nepouzivat realna cisla je mnohem vice. Pokud je nekdo presto pouzije, pak by si mel rizik a zakladnich metod byt velice dobre vedom. -
Pavel TišnovskýZlatý podporovatelNeni to Java ale Cecko, na tom vsak v tomto pripade zase tak nezalezi, protoze minimalne na x86 se pouzivaji stejne "realne" datove typy vychazejici z normy IEEE (s tim pak pracuje matematicky koprocesor). Dale si vsimnete, ze tam opravdu nepouzivam porovnani, tj. x==1.0, to by byla nekonecna smycka. Prave diky pouziti operatoru < se ten priklad stane zajimavejsi, protoze pro nektere hodnoty funguje a pro nektere nikoli.
V tom ostatnim mate naprostou pravdu, i kdyz ona existence kladne a zaporne nuly se v nekterych pripadech hodi. -
Karel (neregistrovaný)Aha, opravdu je to C. Nevim proc jsem usoudil ze je to Java. Omlouvam se.
Porovnani == jste nepouzil, ale pouzil jste < 1. To je to same. Porovnani na 1 se nema pouzivat, protoze hodnota nemusi byt presne 1, ale nejak kolem (napr. 0.99998 nebo 1.00001). Kazdopadne toto plati i pro porovnani < 1, protoze opet - hodnota muze byt napriklad 0.99998. Jinak receno, podminka < 1 je ekvivalentni podmince NOT(>= 1) a zde rovnitko je a byt nema. Takze v pripade podminky "< 1" je odkaz na chybu "porovnani na konkretni hodnotu" opodstatneny.
A ze to nekdy funguje a nekdy ne je dano tim, zda pocitac tu hodnotu 0.1 (nebo jinou) trefi shora, presne nebo zespoda.
Kazdopadne mam pocit, ze oba dva uskali realnych cisel v pocitacich zname a chapeme. Nezbyva nez si prat, aby tomu tak bylo i u vsech ostatnich, kdo programy pisi. Napriklad u vami zminovane externistky :-) -
Pavel TišnovskýZlatý podporovatelNo právě, schválně jsem použil <1 a to z toho důvodu, že u nás na škole (a v některých knihách, které jdou aspoň trochu do hloubky, ale těch moc není) se varuje před testy ekvivalence dvou floatových čísel, což je samozřejmě správné varování. Zapomínají však dodat, že i další relace nemusí u floatů platit tak, jak u reálných čísel. Pokud vás to ve škole učili, tak gratuluji učiteli, u nás se toto téma jen tak rychle proběhlo, takže se obávám, že chyb v některých numerických částech programů ubývat určitě nebude.
Ještě štěstí, že Visual Basic a spol. (brr) má typ Currency, jinak bych se taky nemusel dočkat žádných úroků :-))) -
Pavel TišnovskýZlatý podporovatelTakhle jde ta rovnost samozrejme zkontrolovat a primo na to existuje instrukce koprocesoru, ale nas problem to v zadnem pripade neresi, protoze napriklad nemusi platit:
0,1+0,1==0,2
V tom je prave nejvetsi problem s FP, protoze neplati nektera zakladni pravidla (resp. vlastnosti), jako je asociativita a komutativita operaci. -
Biktop (neregistrovaný)Mohl byste nám prozradit, co to bylo ve Vašem případě za školu? Určité věci je dle mého názoru nutné považovat za takovou "malou násobilku" nebo "vyjmenovaná slova" programátora. A znalost práce s čísly k nim rozhodně patří. Ještě více by mne zajímal původ oné externistky. Neuvědomit si, že počítač nepočítá v reálných číslech při psaní programu je opravdu chyba hodná neudělení zápočtu v prvním ročníku.
Dále bych se připojil ke komentáři výše, že perfektní znalost této problematiky je nezbytná jednak v numerické matematice, jednak v hardwarařině. Naprostá většina měřících nebo jiných zařízení a modulů zpracovávající různé signály či veličiny převedené na elektrické je realizována pomocí 8-bitových jednočipů, případně 16-bitových DSP, a zde se skutečně jejich tvůrci bez znalosti těchto faktů a umění algoritmy dokonale zoptimalizovat neobejdou. Neboli neřekl bych, že je toto téma nějak opomíjeno, ale je pravdou, že ve světě PC opomíjeno je, a to velmi často. Druhou věcí ovšem je, kolik lidí píšící programy pro PC lze skutečně nazvat programátory a kolik z nich jsou jen programátorští nedoukové. -
Pavel TišnovskýZlatý podporovatelVUT FEI :-)
Externistka: to je jednoduché, jedna velmi chytrá paní, která se programovat naučila kdysi dávno ve Fortranu. V té době samozřejmě nic jako semináře programování neexistovaly, takže se to dá pochopit (a dále si myslím, že tu chybu by udělalo tak 90% absolventů dnešních fakult). Pokud se chcete ptát, proč to psala zrovna externistka; to je složitější. Zaprve danou problematiku znala resp. se ji byla ochotna naučit a za druhé se (samozřejmě) jednalo o peníze, protože mladší by to odmítli za tu cenu udělat.
Jinak ohledně DSP a jednočipů naprostý souhlas, i když v této oblasti jsem už viděl mnoho "borců", co programovali na 8051 nebo HC11 v céčku a vůbec si neuvědomili, že jen FP modul (který IMHO zbytečně použili) zabírá víc paměti, než jejich aplikace. -
Biktop (neregistrovaný)Tak to mne samotného překvapuje. Já mám naopak zkušenost, že lidé z dob Fortranu tyhle věci umějí jako když bičem mrská. Přeci jen přístup k počítačům v dobách jeho nadvlády byl, zvláště pak u nás, velmi omezen, strojový čas byl drahý a proto bylo třeba umět co nejlépe programovat i "na papíře". Navíc se počítačům většinou věnovali na katedrách matematiky, resp. tam byli v této problematice proškolování, což samo o sobě garantovalo celkem vysoký standard znalostí. Srovnáte-li dnešní širokou paletu knih o programování s těmi ze 70., 80. let, zjistíte, že nabídka sice byla nepoměrně menší, zato kvalita a důslednost velice často na nesrovnatelně vyšší úrovni, tedy jak po obsahové stránce, tak po náročnosti na čtenářovy znalosti z matematiky.
-
Pavel TišnovskýZlatý podporovatelOna má ta paní vystudovanou fyziku, ne matematiku, takže to možná vysvětluje to "pochybení". V každém případě je z jejích zdrojáků ten Fortran vidět, i když programuje v jiném jazyce :-) Takže rozdíl mezi programátorem a matematikem/fyzikem v přístupu k programování asi nějaký bude...
-
