<< Zpět

 

  Česky: , English:

LongInt

C++ knihovna dlouhých čísel integer a fixed-point

Původní představa byla vytvořit obecnou C++ knihovnu zdvojnásobující přesnost základních prvků, která by se dala používat sama v sobě a tak rekurzivně zvyšovat rozsah čísel. Ne úplně se to povedlo, přece jen překladač má pro takové použití ještě nějaké odmítavé řeči :-) , ale i tak se knihovna dá použít k realizaci větších čísel, než jaká podporuje překladač. Typickým příkladem využití je procesor ATmega, jehož C knihovna plně nepodporuje 64-bitová integer čísla.

Knihovna obsahuje 2 základní třídy, DblInt a QuadInt, které zdvojnásobí a zečtyřnásobí rozlišení základních použitých prvků. Při použití 8 až 64-bitových prvků lze pomocí třídy DblInt vytvořit čísla typu uint32, sint32, fix32, uint64, sint64, fix64, uint128, sint128 a fix128. Pomocí třídy QuadInt lze vytvořit čísla uin64, sint64, fix64, uint128, sint128, fix128, uint256, sint256 a fix256. Typy uint* jsou celočíselné typy bez znaménka. Typy sint* jsou celá čísla se znaménkem. Typy fix* jdou desetiná čísla s pevnou desetinnou tečkou. Horní polovina čísla je celá část čísla, dolní polovina je desetinná část.

Typy tříd jsou nadefinovány pomocí #define maker. Do zdrojového kódu se includuje soubor třídy a před includem se nadefinují parametry pomocí #define. Kód lze do programu includovat vícekrát, s různým nastavením parametrů, a tak vytvořit různé typy čísel v programu, s využitím společného kódu knihovny. Případně by neměl být problém kód upravit na šablonu template.

Příklad použití lze vidět v ukázkovém souboru test.cpp a test.h, který slouží k testování knihovny. Ukázkový program provádí testování knihoven, generováním náhodných operandů (plný test na PC zahrnuje 1000000000 provedených testů pro každý typ čísla). Program je připraven k překladu jednak pod Microsoft VC++ 2005 a jednak pro procesor ARM na Raspberry Pico. Ukázka výstupu testovacího programu:

Check dbl uint32 ... OK
        123 + 7545 = 7668 (should be 7668)
Check dbl sint32 ... OK
        123 * -7545 = -928035 (should be -928035)
Check dbl fix32 ... OK
        123.45 / 3.1415 = 39.2966 (should be 39.2965)
Check dbl uint64 ... OK
        897656 % 75452 = 67684 (should be 67684)
Check dbl sint64 ... OK
        -1239851456 * 754554789 = -935535853773422784 (should be -935535853773422784)
Check dbl fix64 ... OK
        sin_deg(58.76534523) = 0.855050776 (should be 0.855050780)
Check quad uint64B ... OK
        45872341 xor 664334789 = 623052048 (should be 623052048)
Check quad sint64B ... OK
        (-7545545)^2 = 56935249347025 (should be 56935249347025)
Check quad fix64B ... OK
        457.55 ^ 1.14 = 1078.698207313 (should be 1078.698209953)
Check quad dbl uint128 ... OK
        65544765565 << 12 = 268471359754240 (should be 268471359754240)
Check quad dbl sint128 ... OK
        sqrt_int(65544765565) = 256017 remainder 61276 (should be 256017 remainder 61276)
quad uint256
        28! = 304888344611713860501504000000 (should be 304888344611713860501504000000)
quad fix256
        exp(3.1415926535897932384626433832795028842) = 23.14069263277926900572908636794854738013
                                (should be 23.14069263277926900572908636794854738033)

Celočíselné typy mají k dispozici funkce pro základní aritmetické operace: sčítání, odčítání, násobení, dělení, modulo, inkrementace, dekrementace, integrál, porovnání, negace, bitové operace, posuny a celočíselná odmocnina.

U celočíselných typů je k dispozici rychlé dělení, určené k opakovanému dělení čísla konstantou. Rychlé dělení analyzuje dělitele a stanoví nejrychlejší operaci k provedení dělení. V obvyklých případech namísto dělení použije násobení převrácenou hodnotou dělitele a bitový posun výsledku.

Číselné typy s pevnou desetinnou tečkou mají navíc funkce převrácená hodnota, odmocnina, mocnina, převody úhlové míry, sinus, kosinus, tangens, arcus sinus, arcus kosinus, arcus tangens, logaritmus, exponent.

Knihovna není optimalizovaná na rychlost. Má sloužit k doplnění chybějících rozsahů čísel a jako reference k testování verze knihovny v assembleru. V balíku knihovny je i starší verze knihovny, LongCalc, s urychlením knihovny v assembleru x64 a s rozpracovanou knihovnou dlouhých fixed-point čísel BigNum.

Knihovna není úplně dotažená, ani 100% odladěná. Během vývoje jsem narazil na hlavní nedostatek fixed-point čísel - během výpočtů velmi rychle klesá přesnost. Typicky to lze pozorovat např. u výpočtu exponentu a logaritmu, kdy se chyba rychle dostává do podstatných částí čísla. Správnější řešení by bylo provádět výpočty s vyšší přesností a výsledek převést do cílového formátu. Praktičtější jsou čísla s exponentem. Exponent ochrání číslo před rychlou ztrátou přesnosti mezivýpočtů.

Nejlépe nejsou řešené ani výpočty řad, jako je např. sinus. Výpočty řad by měly být rozdělené na úseky používající různé metody, jinak v některých pásmech operandů probíhá výpočet příliš dlouho a s nižší přesností.

V balíku knihovny naleznete:

Na závěr odbočka - jak detekovat přetečení součtu a rozdílu neznaménkových čísel. V assembleru to je jasné - je k dispozici C a V flag. V C++ carry flag nemáme a tak musíme použít následující postup. Při sčítání čísla sečteme, a je-li výsledek menší než některé ze vstupních čísel, nastalo přetečení:

c = a + b;
bool carry = (c < b) ? 1 : 0;

Při odčítání operandy odečteme. Porovnáme vstupní operandy a pokud byl druhý operand větší než první, nastalo přetečení:

c = a - b;
bool carry = (a < b) ? 1 : 0;

Odkaz ke stažení knihovny: LongInt_src.zip

Miroslav Němeček

<< Zpět