Céčko a triviálna matematika

31.3.2008 23:28 | Přečteno: 1853×

Céčkom som sa nikdy nezaoberal a tým pádom viem o ňom naozaj len málo. No vážne som netušil, že nezvláda ani jednoduché porovnanie dvoch čísel!

Kamarát sa mi stažoval, že sa mu nedajú porovnať dve desatinné čísla v Céčku. Neveril som kým som si nenapísal vlastný kód:

priklad.c:

#include <stdio.h>

int main() {

	double Fg, Fy, g;
	int m;

	g=9.81;
	m=10;
	Fg=g*m;

	Fy=98.1;

	printf("Fg = %f\nFy = %f\n", Fg, Fy);

	if (Fg==Fy) {
		printf("OK\n");
	}
	else {
		printf("FUCK\n");
	}

	return 0;

}

Preložil som si ho pomocou gcc priklad.c a spustil - "./a.out". Samozrejme som bol prekvapený už len z toho, že sa mi to skompilovalo, keďže moje skúsenosti s Céčkom skončili pri Hello World.. :) Ale nanešťastie mi môj program zanadával, čo by sa nemalo stať, keďže tie dve premenné sa rovnajú!

Preto by som sa vás chcel spýtať, kde je chyba..? Ja ju teda naozaj nevidím.. :(

       

Komentáře

[Jardík]

Nerovnají, protože se pravděpodobně provede (double)(((int)g)*m). Jestli chceš správný výsledek, musíš do napsat Fg=g*(double)m; nebo by muselo být m typu double.

[Milan Lajtoš]

Zmenil som teda m na double a stále sa to nerovná.

[Josef Kufner]

int krát double vrací double. Vždy se provede přetypování na ten "větší" datový typ.

[Josef Kufner]

Nemůžeš testovat rovnost dvou čísel s plovoucí desetinou čárkou. A to v žádném jazyce. Musíš udělat absolutní hodnotu jejich rozdílu a porovnat, zda je menší než požadovaná přesnost porovnání. Problém je totiž v tom, že samotná reprezentace takovýchto čísel je nepřesná.

if (fabs(Fg - Fy) < 0.01) {

[Milan Lajtoš]

Áno, takto to už funguje ako má. Ďakujem. :)

[filo]

Nemůžeš testovat rovnost dvou čísel s plovoucí desetinou čárkou. A to v žádném jazyce.

Přesně tak. Někdy není dobré věřit tomu, co člověk vidí, ať už v debuggeru, editoru nebo na výstupu. Stejný problém se mnou kdysi "zacvičil" v Delphi a Interbase/Firebirdu. Čísla vypadala, že mají 2 des. místa, ale v reálu tam byl ještě drobek v x-tém řádu.

[Miloslav Ponkrác]

Protože Vám chybí triviální základy ohledně teorie. Protože reálná čísla ve formátu floating point jsou jen přibližná a dochází k zaokrouhlovacím chybám při převodu mezi desítkovým (které máte ve zdrojáky) a dvojkovým vyjádřením reálného čísla v plovoucí čárce (jak je vnitřně uloženo).

Tohle ale patřilo mezi věci, které se v mé době člověk co začínal programovat učil jako první. Ale dnes se propaguje fakt sedni a dělej a pak jsou lidi překvapení naprosto běžnými věcmi.

[Milan Lajtoš]

Aspoň sa môžem vyhovoriť, že nás to v škole neučili. :) Ale naozaj nechápem ako som mohol prísť k takejto zásadnej veci až teraz. Hold, asi si vystacim s celociselnymi typmi.. ;)

[Kvakor]

Opravdu se to dnes neuci? To, ze se dnes uz neuci assembler, se mi sice nelibi, ale chapu to. To, ze se nevysvetluje, jak hardware vlastne pracuje, se mi take nelibi, ale i to dokazu pochopit. Ale to, ze se neuci, jak vypadaji cisla v pohyblive radove carce, povazuju za zlocin, protoze prave chyby, zpusobene neznalosti zakladnich datovych typu, mohou byt velmi zavazne (obzvlast treba v takovem bankovnictvi ). A plati to i pro jazyky, ktere jsou jen slabe typove, nebo typy nepouzivaji vubec.

Minimalne by mel kazdy, kdo programuje, vedet, ze u cisel v plovouci radove carce existuje jen omezena presnost, pri scitani moc rozdilnych cisel mohou podtect, nelze je porovnavat klasickym zpusobem, ale pouze pomoci absolutni hodnoty rozdilu a nastavene presnosti, a ze pro operace nad temito cisly neplati za urcitych okolnosti asociativia a komutativnost, tj. ze nemusi platit napr. (a/b)*c=(a*c)/b.

[Miloslav Ponkrác]

Protože dnes se to považuje za zbytečné

Jinak operace s reálnými čísly na počítači komutativní jsou, ale nejsou asociativní.

[Kvakor]

Jinak operace s reálnými čísly na počítači komutativní jsou, ale nejsou asociativní.

Za urcitych okonlosti nejsou ani komutativni - pokud se nepocita v plne presnoti, dochazi k chybam v dusledku konverze pri nacitani a ukladani dat z/do koprocesoru. Presneji je to popsano treba na Wikipedii, u popisu rozdilu klasickeho FPU a SSE2. Pak zalezi, jakym zpusobem je vzorec zpracovan a poradi promenych muze ovlivnit presnost vysledku.

Prakticky je ale pravdepodobnost neceho takoveho v bezne praxi velmi mala, ale je dobre to vedet.

[Michal Kubeček]

Hlavně je dobré psát aplikace tak, aby jejich funkčnost na takových věcech nezávisela. Tedy aby se zaokrouhlovací chyby projevovaly pokud možno až v těch řádech, které nás nakonec stejně nezajímají.

[Miloslav Ponkrác]

Za urcitych okonlosti nejsou ani komutativni - pokud se nepocita v plne presnoti, dochazi k chybam v dusledku konverze pri nacitani a ukladani dat z/do koprocesoru.

Pak ale komutativnost základních operací není narušena. Protože mluvíme o základních operacích, tedy třeba o

a + b

ne o operaci

converze(a) + converze(b)

Pokud skládáte více operací, pak už platí ta věta o asociativnosti, ale přímé jednoduché operace jsou komutativní.

A pokud si data ukládáte ve více formátech a i na jednoduchou matematickou operaci uděláte konverze - tak pak je to nešikovnost programátora, děláte-li to častěji to za prvé a za druhé už to s konverzí není jedna jednoduchá matematická operace.

[Miloslav Ponkrác]

Jinak bych dodal, že SSE2 je kriplík. Pokoušel jsem se ho kdysi použít a počítá tak blbě a nestandardně, že zlaté FPU. Rychle jsem přišel na to, že ošetřit pro SSE2 všechny potřebné případy tak, aby to přes operace s xmm registry proběhlo v pořádku ve všech případech hodnot mi sežere víc výkonu, než to prostě narvat do FPU, která počítá korektně.

SSE2 je použitelné pro floaty jen tehdy, pokud máte určitá omezení na množinu hodnot, která tím prochází a zaručíte, že výpočet z určitého rozsahu nevybočí.

Argumentovat SSE2 jednotkou na reálná čísla mi přijde stejné jako vyrobit aritmetickou jednotku, která spočítá, že 1+2=8, a vše ostatní spočítá dobře a pak tím argumentovat, že výpočty na integer číslech nejsou komunitativní, protože přeci 1+2=8 a 2+1=3. Pokud máte kriplíka počítací jednotku, tak je chyba v té jednotce, ne v číslech.

[Martin Böhm]

Blbost. Učí se to každý, kdo se vůbec učí.

[Jardík]

Blbost. Potvrzuji, že jsme se tohle také neučili.

[Martin Böhm]

Já Tě varoval, že důkaz chybí :o)

[Messa]

Rovnajú? Spíš nerovnajú, ne? Nebo v čem je vlastně problém? Každopádně vsadím krk na to, že program, operační systém, standardní knihovna a možná i hardware se chová naprosto korektně a problém je mezi židlí a klávesnicí

Nicméně toto je celkem známý problém. Počítače počítají ve dvojkové soustavě a ne v desítkové. Když ti dám spočítat, kolik je deset děleno třema, nikdy mi v desítkové soustavě nenapíšeš přesný výsledek. Stejně tak těžké je pro počítač popsat jednu desetinu. Někde se prostě musí zaokrouhlit, tím vznikne chyba, a když tu chybu zdesetinásobíš, bude to už docela velká chyba, která způsobí nerovnost těch čísel. Řešením je tolerovat drobné chyby, použít zlomky, použít matematickou knihovnu s neomezenou přesností nebo tak něco

[Messa]

Ad můj první odstavec: už jsem to pochopil, kedže znamená nejspíš protože. Zatracená slovenština Never mind.

[Semo]

Preto by som sa vás chcel spýtať, kde je chyba..? Ja ju teda naozaj nevidím.. :(

To vidis spravne! Ziadna tam nie je, je to uplne spravne.

[Vašek Lorenc]

A schválně.. jak dlouho bych musel dělit, aby se výsledek operace 4/3 rovnal po vynásobení 3 zase zpátky třem? Při tom, jak se desetinná čísla reprezentují v počítači, může být takové 0.1 poněkud nešťastné číslo..

[Messa]

Aby 4 děleno 3 krát 3 bylo opět tři? Na čem jedeš, na Pentiu?

[Vašek Lorenc]

Skoro ;) Dnešek byl delší, než bych si normálně přál. Inu, ale otázka platí, ne? ;) Dobře, omlouvám se.. výsledek měl být roven 4.

[Tom.š Ze.le.in]

Z Poznáte matfyzáka:

V Moskovskom gosudarstvennom universitětě postrojili trojíčnuju sčotnuju mašínu Saturn.

Některé nástroje jsou na některé úlohy vhodnější než jiné. (typo 3=4 nechme stranou)

[Miloslav Ponkrác]

Právě z těchto důvodů existují i reálné číslo s pevnou desetinnou čárkou, která počítají přesně - ale Céčko je přímo nepodporuje. Ono to není totiž ani moc potřeba, protože prostě reálná čísla mají své vlastnosti, kde to nevadí. Ono spoustu příkladů stejně nevypočítáte přesně: Kolik je přesně pí? Kolik je přesně e?

A jako další pokud navrhuji spočítat kolik je nula děleno nulou - to totiž v reálných číslech jde. A kolik je třeba jedna děleno nulou - vyjde nekonečno a printf Vám to vypíše. Pak můžete zarýt do ohlašovaného a neohlašovaného NaN, pohrát si s reálnými čísly v normalizovaném a denormalizovaném tvaru. To všechno Vaše Céčko umí

A pak třeba si zapnout FPU výjimky a hrát si s nimi a chytat je, nastavit si přesnost v FPU jednotce, způsob zaokrouhlování.

A nebo porovnávat reálná čísla jako integery - to jde, protože formát reálných čísel podle IEEE 754 normy to umožňuje - a dá to správný výsledek.

Zkrátka reálná čísla jsou pro většinu lidí pole neprobádané, kde je tolik skrytých věcí pro většinu populace až to hezké není.

[h3poun]

Opravdu čísla s pevnou desetinnou čárkou počítají přesně? Není hlavní rozdíl vůči pohyblivé čárce, že vlastně mají pouze mantisu, takže z hlediska přesnosti jsou spíše v nevýhodě a jejich smysl spočívá spíše někde jinde (např. úspora paměti)? Ale třeba se mýlím...

[h3poun]

Tedy abych se ještě opravil, pevná čárka má při stejné paměťové náročnosti vyšší přesnost, ale pořád konečnou a to je podle mne jádro pudla. Pohyblivá čárka má zase větší rozsah [nejmenší vyjádřitelné číslo..největší]. Jde o to, co je pro nás v dané situaci výhodnější.

[Miloslav Ponkrác]

Pro operace plus, mínus, krát počítají čísla s pevnou řádovou čárkou přesně bez zaokrouhlovacích problémů - a to je to co autor počítá. A pokud dáte vypočítat jeho příklad, ale namísto double by tam byl typ s pevnou řádovou čárkou, tak se mu jeho příklad bude rovnat - nebude se divit.

Je jasné, že zase ne všechna existující matematická reálná čísla lze vůbec v počítači reprezentovat - ale tady je zase úplně jedno, jestli jde o pevnou, nebo plovoucí řádovou čárku, nebo třeba logaritmickou, či jinou reprezentaci v počítači, to platí pro všechno. Neexistuje možnost mít na počítači taková čísla, aby vyjádřila celý matematický pojem reálného čísla. Nejde to.

Pohyblivá řádová čárka nemusí mít nutně větší rozsah, než pevná. Pokud třeba zvolíte typ, který bude reprezentovat deset tisíc číslic v pevné řádové čárce, pak číslo typu double jste překonal i v rozsahu. Pevná řádová čárka nemusí mít vyšší přesnost, než pohyblivá. Ono je to tak - pevná řádová čárka fixuje a dělá konstantní počet míst za desetinnou čárkou - a to je její doména. Pohyblivá řádová čárka zase fixuje počet platných číslic, které jsou pro daný typ konstatní. A podle toho co potřebujete se rozhodnete. Ale většinou jsou užitečnější ty pohyblivé.

Existující i jiné reprezentace - třeba jako zlomek (dvě integer čísla), nebo logaritmické (ukládáte logaritmus čísla - velmi výhodné a super rychlé pro algoritmy s obrovskou spoustou násobení a dělení - zrychlení výpočtu je pak enormní).

Vůbec numerická matematika je zajímavá, ale složitá věda.

[h3poun]

Při stejné paměťové náročnosti by mělo mít číslo s pevnou desetinnou čárkou menší rozsah než číslo s pohyblivou, to bylo, co jsem psal. Autorův problém spočívá v tom, že v kódu používá čísla zadaná v desítkové soustavě, která při klasické reprezentaci ve dvojkové soustavě nemají ukončený rozvoj, v čemž by mu zřejmě nepomohla ani pevná desetinná čárka. Ale nechci se hádat, protože si, myslím, rozumíme.

[Miloslav Ponkrác]

Rozumíme si a naprosto souhlasím.

[Kvakor]

Je jasné, že zase ne všechna existující matematická reálná čísla lze vůbec v počítači reprezentovat - ale tady je zase úplně jedno, jestli jde o pevnou, nebo plovoucí řádovou čárku, nebo třeba logaritmickou, či jinou reprezentaci v počítači, to platí pro všechno. Neexistuje možnost mít na počítači taková čísla, aby vyjádřila celý matematický pojem reálného čísla. Nejde to.

Presneji receno, mnozina reprezentovatelnych cisel v pocitaci ma vzdy mohutnost (kardinalitu) pouze mnoziny celych cisel (napr. kazde cislo muzete pretypovat ci prevest na nejaky celociselny typ), ktera je nekonecna (v pocitaci jen teoreticky), ale spocetna (kazdemu prvku muzete priradit pritozene cislo, treba diagonalizaci). Ale mnozina realnych cisel ma vyssi mohutnost, protoze je nejen nekonecna, ale i nespocetna, tj. mezi kazda dve cela nebo racionalni cisla muzete umistit nekonecne mnoho cisel iracionalnich.

Zjednodusene receno: mnozina cisel reprezentovatelnych na pocitaci je sice (teoreticky) nekonecna, ale je nekonecnekrat mensi nez mnozina realnych cisel. Ale moc nad tim nedumejte, nebo se z toho zblaznite jako chudak Cantor.

Prakticky se pomoci plovouci radove carky daji presne reprezentovat jen cela cisla do velikosti mantisy a jejich nasobky vynasobene 2 na rosah exponentu. Cokoliv jineho uz muze byt nepresne. U necelych cisel jsou presna jen ta, ktera jdou prevest na racionalni cislo, jehoz delitel je mocnina dvou. Cokoliv jineho dava nekonecny binarni rozvoj a je tudiz nepresne.

Pokud budete pouzivat bignums, kde jsou cisla reprezenovana racionalnimy cisly (delenec/delitel), tak muzete presne reprezentovat tak velka racionalni cisla, na ktera vam staci pamet. Ale jakekoliv iracionalni cislo (Pi, e, odmocniny atd.) je mozne reprezentovat jen a pouze jako aproximaci s konecou presnosti.

[Miloslav Ponkrác]

Prostě reálná čísla jsou na počítači jen zakuklené integery

Jinak souhlas.

[Michal Kubeček]

Nejen reálná čísla… :-)

[michich]

Ale mnozina realnych cisel ma vyssi mohutnost, protoze je nejen nekonecna, ale i nespocetna, tj. mezi kazda dve cela nebo racionalni cisla muzete umistit nekonecne mnoho cisel iracionalnich.

Mezi libovolnými dvěma racionálními čísly najdete taky nekonečně mnoho racionálních čísel. To ale neznamená, že by množina racionálních čísel byla nespočetná. (Ne)spočetnost je definována podle (ne)existence bijekce na množinu přirozených čísel.

[Michal Kubeček]

Aspoň mezi množináři. Slušné obory považují konečné množiny také za spočetné… :-)

[Ondrej 'SanTiago' Zajicek]

resneji receno, mnozina reprezentovatelnych cisel v pocitaci ma vzdy mohutnost (kardinalitu) pouze mnoziny celych cisel (napr. kazde cislo muzete pretypovat ci prevest na nejaky celociselny typ), ktera je nekonecna (v pocitaci jen teoreticky), ale spocetna (kazdemu prvku muzete priradit pritozene cislo, treba diagonalizaci). Ale mnozina realnych cisel ma vyssi mohutnost, protoze je nejen nekonecna, ale i nespocetna

Coz je sice pravda, ale je to v tomto kontextu irelevantni. Lowenheim-skolemova veta nam totiz zarucuje, ze existuje spocetna podmnozina realnych cisel, ktera obsahuje vsechna 'zajimava' realna cisla. A tedy staci reprezentovat tuto spocetnou podmnozinu. Nicmene algoritmy pracujici nad takovou podmnozinou stejne nejspis nedobehnou v rozumnem case ...

[Michal Kubeček]

Mám tomu rozumět tak, že celá analýza je nezajímavá?! :-)

[Ondrej 'SanTiago' Zajicek]

Nikoliv. Celou analyzu je mozne formulovat v ramci teorie mnozin a pokud je teorie mnozin bezesporna, tak na zaklade LS vety ma spocetny model. Tedy i analyzu jde delat v ramci te spocetne podmnoziny realnych cisel. Jde to definovat i pripocare, bez okliky pres teorii mnozin, akorat je treba lehce preformulovat analyznicke axiomy a vety.

[Michal Kubeček]

No, moc se mi to nezdá, ale momentálně je můj spánkový deficit příliš velký na to, abych v té úvaze hledal chybu nebo abych si představoval, jak namodelovat nespočetné množiny ve spočetném modelu.

[Käyttäjä 11133]

A jako další pokud navrhuji spočítat kolik je nula děleno nulou - to totiž v reálných číslech jde.

Zdroj by nebyl?

[Miloslav Ponkrác]

Norma IEEE 754, a normy jazyků C/C++

[Käyttäjä 11133]

Jesus! Já myslím reálná čísla jako reálná čísla a ne jako Binary Floating-Point aritmetiku.

[Miloslav Ponkrác]

Tak to jsem špatně pochopil! Ale pokud máte limity, tak jde leccos i v matematice Tedy někdy.

Ale jinak jak vidíte, počítače zvládají bravurně věci, se kterými má matematika problémy

[Käyttäjä 11133]

Spíš já špatně pochopil tvůj komentář. Ale to už je fuk. Hlavně, že jsme si to vyjasnili :)

[Kyosuke]

"keďže tie dve premenné sa rovnajú!"

Opravdu? Doporučil bych změnit ten printf na tenhle:

printf("Fg = %f\nFy = %f\n, Fg - Fy = %0.30f\n", Fg, Fy, Fg - Fy);

Pak doporučuji zamyslet se nad tím, jak v dvojkové soustavě (potažmo v plovoucí řádové čárce) vypadá třeba číslo 0.01 (9.81 je 981 * 0.01).

Povinná četba pro Tebe.

[Milan Lajtoš]

Ak mám pravdu povedať, tak ma naozaj nikdy nezaujímalo, že ako sú uložené, no myslím, že po tejto skúsenosti mám na to naozaj dobrý dôvod. Samozrejme si to teda prečítam. :)

[zoul]

A není na to nějaký warning?

[Miloslav Ponkrác]

Jenže ono porovnávání na reálných číslech na rovnost není vždy špatně. Třeba tohel projde vždy správně:

double a = 0.0;
double b = 2.0 - 2.0;

if (a == b)
  printf("Jsi nula!");

Není tam sebemenší důvod, proč by tam bylo cokoli špatně, žádná zaokrouhlovací ani jiná chyba aproximace se v tomto případě vůbec neobjeví. Zde je porovnávání reálných čísel naprosto v pořádku.

Nebo další:

bool is_nan(double x)
{
  return (x != x);
}

Také je porovnávání naprosto v pořádku, není problém.

Prostě pak se tyhle věci musí řešit tak, že se do zdrojáku napíše:

#ifdef __GNUC__
  vypni_debilni_nedomysleny_gcc_warning
#elif _MSVC_VER
  vypni_debilni_nedomyslene_ms_warningy
#endif

Nejlépe do globálního headeru připojeného všemi moduly.

[Miloslav Ponkrác]

A vyšší level: Pro jaké reálné číslo platí toto:

double x = ?;

if (x != x)
  printf("Nerovnaji se");

[Kyosuke]

Není to chyták? To je přeci totéž, co isnan(x) a "not a number" již z definice není zrovna "číslo".

[Miloslav Ponkrác]

No ale uložíte ho do typu na reálné číslo A Céčko s ním jako s reálným číslem pracuje. Ona totiž definice "počítačově uložené floating point číslo" a "matematická definice čísla" není totéž. A nan splňuje první definici, a nesplňuje druhou.

[Miloslav Ponkrác]

Ale Vy jste znalý člověk, tak pro Vás, pane Kyosuke mám ještě jeden vyšší level (a ostatní také mohou odpovídat ):

Pro které číslo (zdůrazňuji jde mi o počítačovou definici čísla) platí, že v proměnné a i b budou (trochu) jiná čísla?

double vrat_cislo(double x)
{
  return x;
}

double a = ?;
double b = vrat_cislo(x);

[Miloslav Ponkrác]

Pardon, ve zdrojáku jsem se přeťukl, ale na principu to nic nemění:

double vrat_cislo(double x)
{
  return x;
}

double a = ?;
double b = vrat_cislo(a);

[xxx]

double a = c++;

[xxx]

Hups jsem se spatne podival

[anicka]

Kde je chyba? Prece v architekture Tve masiny

Ovsem nerikala bych tomu chyba, ale vlastnost.