Programátorská hádanka 2 - najdete chybu?

22.8.2009 08:56 | Přečteno: 1323× | poslední úprava: 22.8.2009 21:09

Možná tuto hádanku už znáte, ale každopádně je to hezká ukázka toho, jak může být matematika v programování někdy matoucí. Narazil jsem na ni kdesi před několika lety.

Následující funkce má fungovat jako knihovní funkce na spočítání průměru ze dvou čísel. Použití je jednoduché - jako parametry očekává dvě čísla a vrací číslo, které je jejich průměrem. Pokud je výsledek neceločíselný, vrátí funkce nejbližší hodnotu směrem k nule.

int SpocitejPrumer(int cislo1, int cislo2) {
  int vysledek;
  
  vysledek = (cislo1 + cislo2) / 2;
  
  return vysledek;
}

Uvedená funkce nevrací výsledek podle zadání. Poznáte, kde je chyba?

Aktualizace: Jako první na chybu přišel Petr Tomášek, na řešení pak uživatel L. Důvodem je to, že ačkoli matematicky platí, že průměr samozřejmě je (číslo+číslo...)/počet_čísel, v programu může dojít k přetečení rozsahu proměnné a po vydělení už nedostaneme správný výsledek. Přetypování na větší typ není obecné řešení (takový typ nemusí existovat nebo chceme udělat funkci jako šablonu, což by bylo v tomto případě nejvhodnější).

Tato chyba se údajně vyskytovala ve starých verzích Javy. Definici chování při neceločíselném výsledku jsem si ale vymyslel jen já pro zmatení nicméně podle reakcí byl příklad i tak celkem lehký. Všem úspěšně řešícím gratuluji

       

Anketa

Komentáře

[Dušan Hokův]

zeby nemel byt vysledek int ?

[Petr Tomášek]

To je zbytečné, průměr dvou intů se totiž do intu vždy vleze ;)

[Dent]

Ale už se tam nevleze to, co je za desetinnou čárkou.

[Aleš Janda]

Co se má dít s desetinným zbytkem mám v příkladu popsáno

[Dent]

Moje chyba, nepřečetl jsem si pořádně zadání.

[Jardík]

Průměr dvou intů se tam vleze, ale nemusí se tam vlézt int+int.

[Petr Tomášek]

hehe, už rozumím, já četl „výsledek“ jako „návratová hodnota funkce“.  A ona to měla být proměnná vysledek :-o

[Petr Tomášek]

Funkce nebude fungovat (hehe), pokud součtem obou intů dojde k přetečení intu... Řešení je triviální: proměnnou vysledek deklarovat jako long a pak jej přetypovat zpět na int.

[L]

i1/2 + i2/2 + (i1%2 + i2%2)/2

[Aleš Janda]

Ano, toto je správné řešení

[kralyk z abclinuxu]

Co mi výde pro i1 = 3 a i2 = 5? Imho 5, což se mi nezdá...
Nebo sem něco nepobral?

[kralyk z abclinuxu]

Aha, oni to nejsou floaty. Proč to nejsou floaty? A to ani když změnim typ proměný vysledek na float

[Marek Bernát]

Prečo by to mali byť floaty? A prečo by to malo súvisieť s premennou vysledek? Kompilátor (obvykle) funguje tak, že vo výraze "var = expr" najprv vyhodnotí typ expr a až potom sa stará o nejaké pretypovania. Samozrejme, mohol by postupovať aj naopak (najprv analyzuje var a potom to berie do úvahy pri analýze expr), ale toto AFAIK žiadny kompilátor nerobí a mne osobne takýto postup dokonca pripadá dosť čudný.

[kralyk z abclinuxu]

Jj, vím jak to je s tou prioritou zpracování, problém byl, že jsem si z nějakého důvody myslel, že produktem promena/2 je vždy float. Už je to jasné...

[Marek Bernát]

Aha. Tak toto si takmer žiadny jazyk nestráži, C-like jazyk AFAIK žiadny, v Pythone to tiež nefunguje, ale napríklad v Lispe áno (/ 1 2) = 1/2 (Lisp má podporu racionálnych čísel) a na celočíselné delenie treba používať zvlášť funkciu div. Vlastne ma napadá, že Pascal mal tiež div, takže / v ňom produkoval REAL alebo chybu? Hm, už je to kopa rokov. Niekto by to mohol otestovať

[kralyk z abclinuxu]

jj, myslim že jsem si to splet právě s Pascalem. Imho / v object pascalu produkoval double nebo dokonce extended, ale ruku do ohně za to nedám...

[Ondrej 'SanTiago' Zajicek]

> Řešení je triviální: proměnnou vysledek deklarovat jako long a pak jej přetypovat zpět na int.

Coz nepomuze, protoze casto (napr. na 32bit Linuxu) ma long stejny rozsah jako int.

[Deleted [8409]]

Dokonce i na 64-bit windows:(

[podlesh]

Řešení je triviální: proměnnou vysledek deklarovat jako long a pak jej přetypovat zpět na int

To je možná triviální, ale není to řešení. Přetypovat na long se musí sčítaná čísla (stačí jedno, druhé se pak přetypuje implicitně).

int vysledek = (int) ( ( (long)cislo1 + (long)cislo2 ) / 2 )

[Marek Bernát]

Lenže long je na 32 bitových architektúrach obvykle úplne rovnako veľký ako int, takže toto tiež nie je riešenie (nehovoriac o tom, že aj keby to fungovalo, napríklad pomocou long long, alebo ešte lepšie explicitného int64_t, tak to stále nie je moc dobré riešenie). A zjavne o tom ani ľudia poriadne netušia, čo som zistel pri bugu, na ktorý som včera narazil.

[Jardík]

Jenže long long je jen v iso c99, C++ vychází ze staršího (snad neplácám kraviny) a c++0x (nebo jak se to teď jmenuje) se asi jen tak nedočkáme.

[Jardík]

Asi jsem si spletl diskusi, tady se asi o C++ nikde neříká ani slovo

[Marek Bernát]

To nevadí. Ako si to s tým C++ myslel? Neviem aký je štandard a pokiaľ viem, tak tieto veci sa ani nijak extra presne nešpecifikujú, ale ja som mal zatiaľ v C++ vždy a všade na 32bitovej architektúre (windows/linux, rôzne kompilátory) long = 32bit, long long = 64bit.

[kralyk z abclinuxu]

Má pravdu chlapec - C++ bylo odvozené od staršího standardu C, ale mám dojem, že některé featury z C99 zařadili aj do C++ v roce 2003, nejsem si ale jistej, jestli nekecám.
Stejnak to máte kopilátor od kopilátoru a platforma od platformy jináč, tak co...

[Marek Bernát]

Ono to s tými kompilátormi nie je IMHO až tak zlé. Väčšinou podporujú štandard kompletne a len pridávajú veci naviac. Tak či tak je naivná kompilácia relatívne jednoduchá (C++ je v tomto výnimka) a najviac roboty je v optimalizácii, nie v dodržiavaní špecifikácie. Málokedy niečo zo štandardu chýba, alebo je implementované inak. Hoci si spomínam, že v nejakej starej verzii MSVC zopár vecí skutočne nefungovalo. Možno deklarácia premenných vo for cykle? Je to dávno. A hlavne je to fuk

[Jardík]

S tím C++ jsem to myslel tak, že ve "starém" C nebyl typ "long long" (btw ten je 64bit i v 64bit linuxu/windows), takže ho "oficiálně" nemá C++ (tzn. GCC ho má ). long long byl přidán právě v iso c99 a z toho C++ "nedědí". long long v C++ má být až po schválení toho C++0x.

[Marek Bernát]

Aha, tak už som zistil, prečo mi to fungovalo aj pod windowsom. Lebo tam som používal DevCpp a ten používa gcc cez mingw. Záhada vyriešená Ale už to bolo dávno, takže ospravedlň moju pamäť. A v MSVC som long long tuším nikdy nepoužil (zasa je to ale dávno), tam to teda nefunguje?

[Jardík]

V MSVC je __int64 a unsigned __int64, popř. pokud includneš windows.h či tak něco, tak máš INT64 a UINT64

[Marek Bernát]

Na to som sa ale nepýtal. Pýtal som sa na to, či tam nefunguje long long. A teraz neviem, či mám tvoju odpoveď brať ako implicitné ÁNO, alebo si len stratil niť

[kralyk z abclinuxu]

Příloha:

• tmp.png (0 bytů)

No tak abyste se nehádali... (viz příloha)
Můj stroj je 64bit, systém je ale win xp 32bit. MSVC 2008.

[Deleted [8409]]

I ve VS 2005 je long long:)

[Marek Bernát]

Nehádame sa, ja sa celkom regulárne pýtam, lebo o tom nič neviem (resp., zabudol som, čo je vo výsledku to isté) Dík.

[kralyk z abclinuxu]

Však jo, to byla nadsázka... btw. všimněte si, jak je ten PNG účinej - zkompresoval to na 0 bytů

[Jardík]

To bych mohl na ábíčko nahrát nějaký gigový obrázek, jestli tam maj chybu

[Marek Bernát]

Môj primitívny parser rozoznáva takéto veci len za pomoci smajlíkov

Nom, tak PNG je bezstrátové, takže to odráža informačnú hodnotu tohoto vlákna

 

[Dr. Eddy]

ehm, mě ten kód funguje docela dobře. a co se týče přetýkání intu a nahrazování ho jiným typem, to přeci neni matematická nesrovnalost, nýbrž to je problém kódu...

[Dent]

To mě také, ale s programováním začínám. S jakými čísly to nevrací očekávaný výsledek?

[mirec]

Záleží na dĺžke intu na danej platforme, odporúčam pozrieť maximálne hodnoty a dať čísla medzi polovičnou a maximálnou hodnotou int-u.

[Dr. Eddy]

Taky s programováním začínám.

Tady vůbec nejde o matematiku, jak naznačuje autor blogpostu, ale jen o rozsah integeru. unsigned int pojme 0 až 65535, tzn. když zadáte funkci obě čísla dost veliká na to, aby jejich součet byl větší než 65535, tak funkce přestává fungovat správně. To se týká jen datových typů v C, mohlo by to být napsané v jiném jazyce a rozsah by se mohl posunout nebo prostě jen změnit typ třeba na long double. Stejně pak ale narazíte na hranice...

[Dent]

To s tím přetečením mne napadlo hned, ale pak by tedy autor zápisku mohl změnit ten úvod. O matiku se imho moc nejedná, spíš o špatný návrh metody.

[Aleš Janda]

Tou matikou jsem myslel to, že průměr je běžně definován jako součet čísel vydělený jejich počtem. Ačkoli to v běžném životě platí, v programování to lze jen málokdy tak použít.

[Dent]

btw - rozhodně jsem pro další programátorské hádanky, aspoň vím, na co si dávat pozor. Doufám, že budete v jejich zadávání pokračovat?

[Aleš Janda]

Jsem rád, že se hádanky líbí Občas na něco narazím, tak až se mi to bude zdát zajímavé, tak to sem zas hodím

[...............23]

Až na pár detailov, int väčšinou býva 32bitový, navyše je štandardne signed, takže ten rozsah je -2³¹ až 2³¹.

Tá akože chyba je ale v tom, ako tu už niekto hovoril, že priemer dvoch intov je vždy v rozsahu intu, takže by to malo fungovať pre všetky int vstupy, stačí zmeniť spôsob počítania toho medzivýsledku alebo použiť tam 64bitový typ (na väčšine compov to bude long long).

[...............23]

Oprava, tá horná hranica má byť 2³¹-1

[Marek Bernát]

Spôsob počítania medzivýsledku myslíš niečo ako a/2 + b/2 a potom ešte ošetrovať ošetrovať sčítanie nepárnych čísel (kde sa stratia dve polovice)? To je dosť hnusné riešenie. Ale každopádne lepšie ako použivať 64 bitový typ (ktorý ani nemusí existovať), keď stačí 33 bitový Tak či onak to poukazuje na to, že v jazykoch ako C človek strávi 90% času riešením blbostí a tak 10% skutočným programovaním

[...............23]

Ten pomer by som prehodil na 10% blbostí, ale stále dosť veľké číslo. V praxi však jednak s takými veľkýmí číslami buď nebude treba počítať vôbec, alebo bude treba počítať ešte aj s väčšími číslami nad rozsah bežných typov, a to už sa použije nejaká knižnica, napríklad gmp, kde tieto problémy odpadajú...

[Marek Bernát]

To je pravda.

[Kvakor]

Druha možnost je saturace - když se při sečtení dvou čísel překročí rozsah (tj. dojde k přetečení), vrátí se misto chybného výsledku maximum. Tj. třeba u osmi bitů by běžné sečtení 0xAA a 0xBB vrátilo 0x65, kdežto se saturací se vrátí 0xFF. Což je sice stále chybný výsledek, ale je to menší chyba než přetečení (více viz http://en.wikipedia.org/wiki/Saturation_arithmetic na wikipedii). Saturovaná aritmetika se sice hlavně používa v DSP (hlavně v audiu, kde většinou přetečení==clipping==zlo), ale dnes je běžný i na obecných procesorech (x86 ho má v MMX).

[Kvakor]

Grrr, nějak jsem zeslonil odkaz, tak znova - Saturation arithmetic.

[Marek Bernát]

IMHO má saturácia význam len keď sa jedná už o skutočnú výstupnú veličinu (napríklad v tom audiu ale tiež farba pixelu a podobne). Ak sa jedná len o medzivýsledok, tak je to úplne rovnako na nič ako pretečenie, lebo v priebehu ďalších výpočtov sa tá chyba môže nepredvídateľne rozrásť.

[default]

hlavně v audiu, kde většinou přetečení==clipping==zlo

V tomto případě to řeší tzv. limiter.

[Tomáš]

Tak či onak to poukazuje na to, že v jazykoch ako C človek strávi 90% času riešením blbostí a tak 10% skutočným programovaním  

Ale když to má běžet na topinkovači, tak většinou není na výběr. (Sorry, ale nenašel jsem odkaz na příslušný díl seriálu Red Dwarf.)

[kralyk z abclinuxu]

Stačí přidat + 0.5 ne?
(a ochranu proti přetečení, dobře)

[Kvakor]

Nebo spíš jedničku a pak teprve podělit (potom to celé bude čistě celočíselné). A pokud se programuje pro platformu, která má pomalé dělení, posunout o jeden bit doprava.

[Heron]

Dělení konstantou rozložitelnou na mocniny dvojky kompilátor snad vždy optimalizuje jako posun, ne?

[Jardík]

No jak kterej, gcc bych nevěřil ani v tomhle

[Jardík]

A jak víte, že zrovna doprava? Co když je to doleva?

[M. Lox]

+1. Vymrdat s bajtsexem!

[Ondrej 'SanTiago' Zajicek]

Protoze to rika standard C99 (sekce 6.5.7). Tohle s endianitou nema nic spolecneho.

[Jardík]

Tak když to říká standard, tak to máte asi pravdu. Sem si zase jednou naletěl

[Ladicek]

Tato chyba se údajně vyskytovala ve starých verzích Javy.

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

[Jardík]

Největším problémem javy však je indexace inty, jehož rozsah je např. 64bit platformách nedostatečný.

[Marek Bernát]

Čo sem furt ťaháš tú 64 bitovú šmejďárnu? Kým to nemá aspoň 128 bitov, tak je to nepoužiteľné.

[Ladicek]

A jak to souvisí s tématem zápisku?

[Jardík]

Tak, že v tom kódu na binary search, kam odkazuješ, se indexuje intem.

[Ladicek]

Tak na to bych nepřišel. A kdyby se tam indexovalo longem (a bylo to povolené), tak ta chyba nenastane? Nebo sis jenom chtěl kopnout do Javy (což nevyšlo, má mnohem větší problémy, detailněji probráno v několika minulých flamech)?

[Jardík]

Samozřejmě jsem si potřeboval kopnout. Indexace longem (jako v .NET) je taky špatná. Správný způsob indexace je takovým typek, který má stejnou velikost jako ukazatel, aby šla indexovat celá paměť a né jen její část. Takhle v javě třeba nemůžete do paměti např. namapovat iso DVDéčka > 2GB, i když má aplikace dostatek adresového prostoru (úmyslně nepíšu paměti).

[kralyk z abclinuxu]

Je velkej problém tohle opravit?

[Jardík]

Tak povídejte, jak v javě namapuju do paměti 3GB soubor?

[Marek Bernát]

Možno je to hlúpa otázka, ale povieš mi, prečo ho potrebuješ v pamäti celý naraz?

[Jardík]

Ano, hloupá otázka, hloupá odpověď: proč ne?

[Marek Bernát]

Pretože nenávidím programy, ktoré si alokujú viac pamäte, než potrebujú. Obvykle úplne stačí buffering (lebo na spracovanie dát obvykle stačí pracovať s presne jedným znakom, maximálne pár ďalšími, ak sa jedná o zložitejšie parsovanie). Dobrým (teda skôr zlým) príkladom je vim, v ktorom keď otvoríš film, tak sa môžeš rovno so systémom rozlúčiť, lebo sa ten súbor snaží celý natiahnuť do pamäte. Keby bol bufferovaný, tak sa to dá používať.

Takže ešte raz: prečo to chceš (napriek spomínaným obrovským nevýhodám)?

[Heron]

Při mapování se soubor nečte celý do paměti (rozhodně ne do alokované paměti programů). mmap v podstatě zpřístupní soubor na disku jako běžné pole, programátor pak pracuje přímo s tím polem, nemusí ručně sahat na ten soubor a řešit postupné načítání. To vše za něj řeší OS, včetně věcí jako readahead. Je to rychlé a paměť to šetří.

[Marek Bernát]

A čo mmap je jediný spôsob využívania pamäte? Nehovoriac o tom, že ešte pred chvíľou sme sa bavili o Jave. Tak či onak, ten vim proste na veľkých súboroch nefunguje.

[Jardík]

A čo mmap je jediný spôsob využívania pamäte

Ne. Ale pro namapování souboru do paměti vám na POSIX systémech nic jiného nezbývá. Ve Windows máte třeba CreateFileMapping().

vim proste na veľkých súboroch nefunguje

Jenže to bude proto, že vim neudělá mmap(), ale buffer = malloc(velikost_souboru), read(soubor, buffer, velikost_souboru).

[Marek Bernát]

Samozrejme, z nejakého dôvodu som intepretoval mapovanie ako ľubovoľné naťahovanie do pamäte. Ešte raz sa ospravedlňujem.

[Jardík]

Jenže to by to pan Bernát musel nejdřív vědět, aby neplácal takový kraviny

[Marek Bernát]

Wtf? Hovoril som o tom, že programy si alokujú viac než potrebujú, nejde o žiadny mmap. Pokojne si ten vim skús a sleduj jeho spotrebu pamäte. Zjavne opakovane volá malloc, aby si tam celý ten súbor narval naraz

[Jardík]

Pretože nenávidím programy, ktoré si alokujú viac pamäte, než potrebujú.

Pokud si přečtete pořádně i na co reagujete, tak zjistíte, že na "proč bych neměl chtít namapovat do paměti 3GB soubor"

[Marek Bernát]

Aha, sorry, ty si sa na začiatku pýtal práve na mapovanie a ja som to pochopil ako načítanie súboru do pamäte. Tak to sa ospravedlňujem

[Jardík]

Jup, než jsem to dopsal. To neva, alespoň byl důvod se hádat

[Marek Bernát]

No, to už teraz bohužiaľ nie je

Ale aj tak by ma zaujímalo, prečo to ten vim rieši tak dementne. Možno kvôli kompatibilite so systémami, ktoré mapovanie neposkytujú (ak také vôbec sú)? Ak by išlo len o to, tak nie je problém si napísať vlastný buffering. Asi to skôr nikoho netrápi, lebo 100MB súbory sa väčšinou needitujú

[kralyk z abclinuxu]

Tak povídejte, jak v javě namapuju do paměti 3GB soubor?

Zřejmě nijak. Moje otázka nebyla nějak ironická, jen jsem se zajímal o to, jak velkej problém je tu indexaci vylepšit, abych mohl buď zdvyhat obočí nad laxností vývojářů SUNu (v případě, že to problém není), nebo s pochopením přikyvovat hlavou (v případě, že to je velký problém)

[Jardík]

Já řešení už nabídl (tak trochu) - zavedeme nový datový typ s velikostí jako "nativní ukazatel" a ten budeme používat na indexaci polí. Umí java pole s jiným prvním prvkem než 0 (jako např. pascal)? Pokud ne, tak ten typ by měl být neznaménkový.

[kralyk z abclinuxu]

Takový datový typ ale bude muset mít proměnnou velikost podle platformy, na které daný sw spustíš. Tzn. jeho velikost bude známa až při spuštění sw. Nevím jak moc snadno se tohle dá v Javě zařídit, ale třeba jo...

Mimochodem mám dojem, že pascal umí pole taky jen od 0.

[Ladicek]

Pascal umí pole odkud chci dokud chci. A pevně dané rozsahy/velikosti primitivních datových typů, když už teda v Javě primitivní typy máme, jsou mnohem lepší než ten céčkový zmatek. Navíc v případě pevně daných velikostí datových typů nemá smysl se zabývat něčím jako "nativní ukazatel", prostě indexuju tím největším, co mám (a co dává smysl).

[kralyk z abclinuxu]

A pevně dané rozsahy/velikosti primitivních datových typů, když už teda v Javě primitivní typy máme, jsou mnohem lepší než ten céčkový zmatek.

To je sice hezké, jenže Javu vyvíjí jedna firma a ta samá firma vyvíjí také jeden runtime VM, tedy JVM.
Céčko - tam je situace o něco složitější. Máme k dispozici hafo kompilátorů za kterými stojí různí tvůrci, máme tu taky hafo operačních systémů a platforem, z nichž každý je o něco jiný. Vzhledem k tomu, že každý program v C/C++ běží přímo na železe daného stroje bez nějaké mezivrstvy, jako je JVM, není divu.

[Jardík]

Nemůžete indexovat tím největším, protože to se přetypováním hezky "zkrátí" a bude to stejný jako indexovat intem.

[Ladicek]

To jsem myslel z pohledu architekta platformy. V Javě to samozřejmě nejde, to je jasné, nikde tu netvrdím (i když bys jistě rád ), že zrovna v Javě se zrovna pole dají indexovat longem.

[Ladicek]

FileChannel, ByteBuffer a spol.

[Ladicek]

Správný způsob indexace je takovým typek, který má stejnou velikost jako ukazatel

To umožňuje který jazyk?

Mimochodem mapování souborů do paměti v Javě funguje. I pro ty tvoje oblíbené desetigigové soubory. Indexuje se longem. Nevíš a mluvíš – jako obvykle.

[Jardík]

Četl jste ten odkazovaný blog?

1:         public static int binarySearch(int[] a, int key) {
2:         int low = 0;
3:         int high = a.length - 1;
4:
5:         while (low <= high) {
6:             int mid = (low + high) / 2;
7:             int midVal = a[mid];
8:
9:             if (midVal < key)
10:                 low = mid + 1
11:             else if (midVal > key)
12:                 high = mid - 1;
13:             else
14:                 return mid; // key found
15:         }
16:         return -(low + 1);  // key not found.
17:     }

Jestli nejse slepej, indexujou intem.

[Jardík]

pole.length, netbeans napovídá "int", veškeré funkce pro práci s polem přebírají int ...

[Jardík]

http://java.sun.com/docs/books/jls/second_edition/html/arrays.doc.html

[podlesh]

Špatně, tam není o mmap ani slovo.

[Jardík]

O mmap() tam slovo těžko bude, když to není funkce javy ale systémové volání. Ale je tam důkaz, že java indexuje intama, což se mi snažil Ladicek vymluvit a udělat ze mě debila.

Já akorát teď můžu přiznat svou chybu, že s FileChannel a ByteBuffer je možné namapovat soubor o velikosti >2GB, protože tam se opravdu pracuje s longem, ale je tam další omezení a to velikost longu, která bude zase na 128bit platformě nedostatečná k adresaci. Ale mapování souboru byl jen příklad a neřeší to problém, že indexování polí je řešené intem.

[Jardík]

kdyby se to nechtělo hledatv textu:

Arrays must be indexed by int values; short, byte, or char values may also be used as index values because they are subjected to unary numeric promotion (§5.6.1) and become int values. An attempt to access an array component with a long index value results in a compile-time error.

[Ladicek]

Četl jsi můj příspěvek? Zkusím odstranit nadbytečné: mapování souborů do paměti v Javě funguje. Indexuje se longem. Co to má společného s poli?

Jo, na size_t jsem si nevzpomněl, díky.

[Jardík]

Jó, tak to soráč

[Jardík]

To umožňuje který jazyk?

Minimálně C/C++ - size_t, v stl je to *::size_type pro indexování v polích, ptrdiff_t k přičítání k ukazateli.