Názory k článku
Fixed point arithmetic

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... (???))

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.

co je zle na int? to je rychlostna optimalizacia. hodnota bude dobre zarovnana v pamati a je velkosti prirodzenej procesoru.
bitove polia sa daju pouzit skor inde.

Ono 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...

V 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.

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.

Asi 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?

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).

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.

Ten pán se ovšem vydával za Alana Coxe. ;-) Od toho bych taková slova prostě nečekal. ;-)

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

A 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)

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 :)

Já 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.

... 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.

No, 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.

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.

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.

Porad 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.

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.

Dekuju 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.

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.

To 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.

Ale nejsou! Jakmile mluvíme o mikrokódu, nemluvíme o RISC. To jsou vše jen obchodní triky a kličky. Procesory typu Pentium rozhodně nelze považovat za RISC. Ortogonálnost instrukční sady procesorů RISC je důsledkem jejich konstrukce.

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).

S 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).

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. :-)

to je snad zrejme, ze ked chcem mat viac flagov v strukture, je to lepsie dat do 1 intu :)

Ne pro každého, zřejmě... ;-)

Ten příspěvek o rychlostní penalizaci je ode mě.

Já 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.

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í).

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.

Neni 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.

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 :-)

No 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ů :-)))

souhlasim, ze pro floaty je a==b celkem kravina, ale slo by to obejit, tak ze by se zkontrolovaly
bitove reprezentace obou floatu a pak by podobna rovnost mela smysl.

Takhle 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.

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é.

VUT 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.

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.

Ona 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...

No, to je pak otázkou, co ta paní vlastně programovala... Já jsem též fyzik :-)

V podstate to byla dost slozita statisticka aplikace.

Dobrý den,

hezký článek. Chtěl bych Vás požádat ještě o vysvětlení algoritmu pro převod dvojkového čísla na desítkové. Myslím, že by se to k tomuto článku hodilo.

Děkuji.

prevod medzi sustavami je otazka maximalne 1. rocnika strednej skoly.

disorder: Vysvetlil jsi to uplne skvele, dekujeme za hodnotny prispevek. Protoze jsi to ovsem probral mozna prilis do hloubky a nekoho zajimaji jen zaklady, zkusim to vysvetlit jeste jednou, jenom jako kucharku. Prevod budu demonstrovat nejprve na desitkove soustave. Jaka je hodnota cisla 123?

1           2       3 = 3*1 + 2*10 + 1*100 = 3*(10^0) + 2*(10^1)+ 1*(10^2) 
stovky   desitky  jednotky

Kdyz si uvedomis, ze takhle se vlastne zapisuje cislo, pro vsechny soustavy uz je to pak stejne. Napr. pro dvojkovou soustavu

0         1       0          1
osmicky ctyrky  dvojky    jednotky
0101 = 1*2^0 + 0*2^1 + 1*2^2 + 0*2^3 = 1*1 + 0*2 + 1*4 + 0*8 = 5

Pro sestnactkovou soustavu

2                      9             A(=10)
dvestepadesatsestky  sestnactky     jednotky

29A = 10*16^0 + 9*16^1 + 2*16^2 = 10*1 + 9*16 + 2*256 = 666

atd pro dalsi soustavy. Doufam ze je to srozumitelne.

rad som pomohol.

ale teraz vazne. kto si cita takyto clanok, mal by take trivialne veci ovladat. urcite to nie je nieco co by v nom malo byt specialne vykladane.

Dobrý den,

myslíte "klasický" převod řetězce dvojkových číslic na desítkovou hodnotu?

Dělá se to následovně: řetězec dvojkových číslic se zapíše do tabulky, kde jsou ke každé pozici bitu vypsány i jejich váhy (desítkově). Potom se sečtou pouze ty váhy, u kterých je příslušný bit nastavený na jedničku, takže například pro řetězec 101010 bysme napsali:

bit  váha  vypočtená váha  váha*bit
1    2^5   32               32
0    2^4   16                0
1    2^3    8                8
0    2^2    4                0
1    2^1    2                2
0    2^0    1                0
Celkem:                  ***42*** 

(btw, velmi důležitá kosmologická konstanta :-)

To stejné platí pro fixed point, pouze se změní váhy. Pro číslo 101.101 to bude:

bit  váha  vypočtená váha  váha*bit
1    2^2    4               4,000
0    2^1    2               0,000
1    2^0    1               1,000
1    2^-1  0,5              0,500
0    2^-2  0,25             0,000
1    2^-3  0,125            0,125
Celkem:                     5,625

Dovolím si jen drobnou poznámku pro upřesnění: Uvedený převod platí pouze pro takzvaný "přirozený binární kód". To jak přiřadím jednotlivé objekty (čísla) jednotlivým kombinacím nul a jedniček záleží jen a jen na mě.
Například si mohu jednotlivým bitů přiřadit segmenty displeje a logická jednička pak znamená, že segment svítí. Číslici v dekadické soustavě je přiřazena taková kombinace, aby se zobrazila na displeji. Je možno jmenovat i Grayův kód, kód 1 z N a další.
Pokud však není uveden typ kódu, uvažuje se vetšinou právě přirozený binární.

Doporučil bych klasickou literaturu:
B.A.Popov, G.S.Tesler
Výpočty funkcí na EVM
(Vyčislenie funkcij na EVM - Kiev, Naukova Dumka - 1984)

Pro toho, kdo se věnuje hard core věcem bez nároků na tuny paměti a potřebuje dosáhnout různou přesnost s různými, ale potřebnými náklady, je to dobrá kniha.

Pak je ještě jedna. Tu musím vyhrabat z archivu a ta je pro fajnšmekry.
Věnuje se výpočtům cifra za cifrou. Žádný koprocesor jen základní operace, posuny a manipulace s bity. Po přelouskání této knížečky máte ten správný pocit. Tedy něco v tom smyslu - už vím jak to funguje.

Dnešní koprocesory jsou na těchto věcech hodně postaveny a odvedou poctivou práci.
Proto je není potřeba zavrhovat.

Čauky

Cifra za cifrou? Na tom není nic zvláštního, to je ekvivalent BIGNUM aritmetiky se "slovem" velikosti jedné číslice... :-) GMP musí být pěkné čtení.

Jak se jmenuje ta druhá kniha? Kde by se daly tyto knihy sehnat? Ja totiž řeším matematické operace pouze s možností sčítání, odčítání, rotacemi (násobení, dělění jen 2).

Ne, klasický převod je triviální. Já myslím zobrazení binarního čísla uloženého v paměti procesoru. Třeba takový PIC16F88 nemá násobení a dělění. Tak že se to řeší sčítáním, odčítáním, rotacemi. Tento článek mě zaujal a protože jsem dlouho hledal algoritmus jak zobrazit uložené číslo v paměti mikrochipu, doufal jsem že bych zde mohl najít odpověď.

Lze to dělat dělením 10^n, kde je n od nejvyššího řádu k nejnižšímu,ale to je zdlouhavé. Určitě existuje nějaký postup, kdy by stačilo násobit a dělit 2, a přičítat a odečítat nějaké malé číslo.

Otázka zní, jak zobrazit binární číslo na displeji desítkově.
Stačil by mi algoritmus na převod BIN -> BCD, protože BCD lze jednoduše zobrazit.

Děkuji za odpověď.

Zkuste se mrknout na http://www.doulos.com/knowhow/vhdl_designers_guide/models/binary_bcd/

Je to sice trošku hardwarově orientováno, ale ten hlavní problém tam mají vyřešený, tj. použití shiftů a bitových operací místo násobení.

algoritmus na prepocet kazdeho bitu je mozny cez tento sikovny programcek:
http://sourceforge.net/projects/k-map

netreba ani poznat minimalizaciu a karnaughove mapy. len si naklikaj pre kazdy bit pravdivostnu tabulku a solve ti vypluje logicke operacie na jeho prepocet.

Je na to jednoduchý postup: postupne beriem bity čísla (od najvyššieho po najnižší) ktoré chcem previesť do BCD a robím s každým toto:
1) vynásobím súčasnú hodnotu medzivýsledku dvomi, medzivýsledok si už udržiavam v BCD -na to by tam mala byť priamo inštrukcia, alebo aspoň inštrukcia, ktorá po vynásobení (rolovaní) upraví výsledok tak, aby bol opat v BCD tvare
2) pripočítam ten bit z prevádzaného čísla (a opať upravím medzivýsledok tak, aby bol v BCD tvare)

A to je všetko... na konci mám BCD tvar čísla

Ahoj, diky za clanek. Sice vetsinu tech veci tak nejak vim (taky jsem programoval v asembleru - kde jsou ty casy), ale uvedomil jsem si, ze uz ty znalosti nepouzivam a nechce se mi nad tim premyslet.
Prave planuju v jednom svem programu pro praci s obrazky rozsireni pro HDR (high dynamic resolution), tzn. vic nez 8 bitu na barvu - myslel jsem si, ze na barvu proste pouziju tri floaty a bude vymalovano, ale asi si pockam na dalsi dily clanku :).

proc floatu proboha?

Protoože HDR? Ale 32b fixed point by taky nemusel být špatný... :-)

Proč ne? Dnešní grafické karty používají pro barvy také floaty.

Ano, ale nejsou to "klasické" typy float aka single podle IEEE. V GPU se pouzivaji i kratsi floaty, napriklad 16bitove, nekdy i 12bitove. Take jejich aritmetika je jednodussi, protoze se nemusi rozlisovat nekonecna a +-0.

Například GPU od NVIDIA nekonečna apod. umí. A mám pocit, že 12bitové floaty se nepoužívají, buď 16, 24 nebo 32. Existuje i 12bitový formát, ale myslím, že ten je fixed point.

12bitove floaty mely cipy od ATI, ted tu informaci vsak nemuzu dohledat. Dokonce existuji i 8bitove floaty, jejich pouziti je vsak minimalni - ukladani prubehu nekterych signalu atd. Na GPU se nepouzivaji.

Jen doplnim, ze jeden z tech znamejsich serveru o open hardware jadrech nejen do FPGA je http://opencollector.org/

Vzdy pomuze vhodny programovaci jazyk. Napriklad pro praci s penezi byl jiz hodne davno navrzen jeden jazyk, kde staci promennou deklarovat s typem
PIC S9(9)V9(2) COMP
a hned nam tam krasny (dekadicky) FXP funguje. A clovek uz na to nemusi vubec myslet. Traduje se, ze v tomto jazyce je napsana stale jeste vetsina software.

Jo jo, COBOListu uz dnes clovek najde malo. Skoda...

"The use of COBOL cripples the mind; its teaching should, therefore, be regarded as a criminal offence"
Edsger Dijkstra
Selected Writings on Computing: A Personal Perspective

Dijkstra - to je ten clovek, co kritizoval syntaxi C za to, ze strednik je ukoncovac prikazu a ne oddelovac prikazu?

A jinak taky: "Fact 30: COBOL is a very bad language, but all the others (for business applications) are so much worse."
Robert L. Glass
Facts and Fallacies of Software Engineering

Tak děti nehádejte se! :-)
Teoretický informatik a programátor se na ideálním programovacím jazyku nikdy nemohou dohodnout. Teoretik by rád matematickou eleganci, programátor by rád praktickou použitelnost => spor :-)

Rikas to jako kdyby sis myslel, ze dva programatori se shodnou mohou. Dva programatori se mohou shodnout na tom ktere jazyky jsou spatne a nekdy i ktere jsou dobre, ale na tom nejlepsim nebo idealnim ... dost nepravdepodobne.

Oni se nekdy neshodnou ani matematici. Neco podobneho jsem zazil na me zkousce :-), kdy jsem na otazku ohledne dukazu nektereho grafoveho algoritmu odpovedel podle jednoho matematika spravne (taky to bylo podle jeho prednasek) a podle druheho to bylo blbe. Potom jsem tak pul hodiny poslouchal jejich diskusi a sem tam prikyvoval - no bylo to nakonec za 2 :-)

Potom by to slo resit vylucovacim zpusobem:

1. vezmeme mnozinu vsech programovacich jazyku P
2. vezmem mnozinu vsech programatoru
3. kazda dvojice programatoru (system kazdy s kazdym bez ohledu na pohlavi :-) vybere jeden "spatny" jazyk
4. ten je nasledne vyjmut z mnoziny P
5. na konci ziskame pouze ty dobre ci idealni jazyky - akorat se obavam, ze vznikne neco takoveho P={} :-)))

Nikoliv. Na konci ziskas jazyky, o kterych ze zminene mnoziny programatoru nikdo neslysel.

Pravda, takze to pravdepodobne nebude ten nejlepsi jazyk :-)

Zajímalo by mě: specifikuje ta norma IEEE přesně (do posledního bitu), jak mají výsledky toho floating-point počítání vypadat?

Kdyby člověk třeba dělal něco jako síťový protokol DOOMa (počítače si posílají pouze akce jednotlivých hráčů a každý počítač provádí výpočet stavu hry sám), zda to vůbec má šanci fungovat mezi počítači různých architektur.

Jak moc dobře je to IEEE podporováno? Třeba Intel má instrukce fsin a fcos, které mají omezený rozsah vstupních hodnot, a zda je přesná náhrada v knihovně, to je otázka.

Zdravím, myslím, že se definice blíží bit exact normě. Je definované i přesně, kdy má být vyhlášena výjimka a jak musí být výsledek zaokrouhlován. Norma je však dost složitá a obsahuje několik vyžadovaných režimů nastavení hlášení výjimek a zarovnávání. Myslím, že v podstatě žádný CPU ji do posledního puntíku neplní. Proto musí být pro zajištění plné kompatability doplněn kompilátor a CPU knihovnou. Protože dodržování všech pravidel zpomaluje, umožňuje většinou kompilátor testy a řešení krajních mezí explicitně vynechat, viz parametr GCC "-ffast-math".

Pro otestování splnění bitexact požadavků je často používán "paranoia" test, třeba viz:

Kahan's Floating Point Test "Paranoia"

Výsledek na Linuxu mi vyšel: The arithmetic diagnosed may be Acceptable despite inconvenient Defects.

Předpokládám, že autor článku má v oblasti širší znalosti a proto se těším na další pokračování, které přinese jeho pohled na problémy a zkušenosti s FP.

Ano, pokud jsou dodrzeny zaokrouhlovaci rezimy (ty jdou v pripade 8087 nastavit), tak je vysledek operaci zarucen i do posledniho bitu. To vsak plati pro zakladni aritmeticke operace, u fsin, flog apod. jde (pravdepodobne) o implementaci algoritmu CORDIC a tam se presnost muze snizovat.

DOOM pouziva FP aritmetiku? Do zdrojaku jsem se nedival, ale pripadne mi, ze jeste na 386 bylo FPU docela pomala zalezitost, nehlede na to, ze to prece fungovalo i na "cisle" 386 bez FPU (teda jestli si to dobre pamatuju). Myslim, ze Carnac to sve slavne paralelni zpracovani CPU+FPU rozvinul az u Quaka.

Cili ta norma zarucuje presnost pouze + - * /, ale ostatni funkce uz ne?

DOOM myslim trochu FP pouzival, ale dost malo, ze to bylo mozno emulovat. Pridani koprocesoru pry DOOMa zrychlilo.

Quaka jsem jednou zkusil pustit se softwarove emulovanym FPU a udelal 0.5 snimku za sekundu (2 snimky, pokud jsem se podival do zeme a nebyly tam zadne vertexy).

Presnost je tam popsana pro operace +, -, *, / a sqrt(). Vysledky se mohou lisit v zavislosti na zvolenem rezimu zaokrouhlovani/osekavani vysledku. IEEE zna ctyri moznosti, ty se napriklad u FPU x87 daji nastavovat v CW.

A nebo taky zrychluje. Už za starých dob bylo možné jet výpočet na procesoru i FPU prakticky paralelně. Svého času to používal MATLAB, který počítal rychleji, než když to běžně napíšete v assembleru. Prostě jel dvě linky, jednu na cpu a druhou na fpu.

To ano (jinak by to taky nebyl koprocesor), ale problemy nastavaji se zpetnym prevodem na integery, ty prave iD soft vyresil az u Quaka. Dalsi problem je v tom, ze v dobach 386 nebyl FPU moc rozsireny, tedy urcite ne na pocitacich prodavanych u nas. To vim docela presne, protoze jsem v te dobe dost delal v AutoCADu, takze jsem na mnoha pocitacich instaloval ruzne emulatory 8087 (ani se neptejte, jak potom AutoCAD pomalu prekresloval pri "regenu", i ma 286 s koupenym 287 za 500,- byla rychlejsi).

Nicmene podle stranky http://www.faqs.org/faqs/games/doom/RGCD-faq/ DOOM FPU nepouziva:

5A. Does DOOM benefit from a FPU for floating point calculations?

No. All calculations in DOOM 1.1 and beyond use integers. Hence,
DOOM does not suffer from the Pentium floating point bug in any way.