Knihovna dlouhých čísel c. Podívejte se, co je „Dlouhá aritmetika“ v jiných slovnících

Ale co když potřebujete reprezentovat číslo, jako je například 29! = 8841761993739701954543616000000? Takové číslo se nevejde do 64bitového, tím méně do 32bitového datového typu. Právě pro práci s tak velkými čísly existuje dlouhá aritmetika.

Dlouhá aritmetika- V počítačová technologie operace (sčítání, násobení, odčítání, dělení, umocňování atd.) na číslech, jejichž bitová hloubka přesahuje délku strojového slova daného počítač. Tyto operace jsou realizovány nikoli hardwarově, ale softwarově, s využitím základního hardwaru pro práci s čísly nižších řádů.

Dlouhá aritmetika může být také považována za jednu ze sekcí programování olympiád, protože při řešení problémů často nestačí kapacita standardních typů k vyjádření konečného výsledku. Při výběru programovacího jazyka pro potřeby olympiády není nepodstatná vestavěná sada nástrojů (hotové knihovny, implementované třídy). Mnoho jazyků (Java, Ruby, Python) má vestavěnou podporu pro dlouhou aritmetiku, což může výrazně zkrátit čas potřebný k napsání programu.

Platforma .NET až do verze 4.0 neměla vestavěnou podporu pro práci s dlouhými čísly. Ve verzi 4 získal .NET nejen dlouhá čísla, ale i komplexní čísla. Tato funkce je dostupná prostřednictvím sestavy Systém.Čísla a typy BigInteger A Komplex definovaný v oboru názvů se stejným názvem jako název sestavení.

Je třeba říci, že struktura BigInteger měl mít, ale v té době ještě nebyl zcela připraven, jeho implementace nesplňovala všechny potřeby (mohou zde být zahrnuty i problémy s výkonem), proto bylo rozhodnuto odložit jeho vydání až na .NET 4.0.

V tomto článku bych se rád podíval na detaily implementace dlouhé aritmetiky od Microsoftu.

Obecné pojmy

123456789 10 = 1*10 8 + 2*10 7 + 3*10 6 + 4*10 5 + 5*10 4 + 6*10 3 + 7*10 2 + 8*10 1 + 9*10 0

V obecný případ, libovolné číslo může být reprezentováno jako:

A = a n-1 β n-1 + a n-2 β n-2 +…+a 1 β + a 0
kde β je základ číselné soustavy, ve které číslo reprezentujeme, a koeficienty a i splňují dvojitou nerovnost 0 ≤ a i< β.

Zobrazení čísla připomíná zobrazení polynomu, jen místo x na příslušný stupeň máme základ β na požadovaný stupeň. Jak známo, je vhodné reprezentovat polynom a 0 + a 1 x + a 2 x 2 + … + a n x n jako pole, jehož prvky představují koeficienty a i a index i určuje odpovídající stupeň x. Stejným způsobem se ukládá dlouhé číslo; zbývá pouze rozhodnout o volbě základu β.

Například stejné číslo 123456789 může být reprezentováno v desetitisícové (β = 10 4) číselné soustavě takto:

123456789 10 = 1*(10 4) 2 + 2345*(10 4) 1 + 6789*(10 4) 0

Zastoupením čísla 123456789 v desetitisícové číselné soustavě získáme dvě výhody najednou: za prvé snížíme množství spotřebované paměti, protože místo pole 9 čísel stačí uložit pole 3 čísel (1 , 2345 a 6789), za druhé, výrazně Zkrátíme čas potřebný k provedení standardních operací s dlouhými čísly, protože zpracováváme 4 číslice čísla najednou. Obecně je počítač stejně rychlý při přidávání jednociferných a 32bitových čísel, takže byste toho měli využít.

Radix β obvykle závisí na maximální velikosti základního datového typu v počítači a vybírá se na základě následujících úvah:

1. základ musí odpovídat jednomu ze základních datových typů;
2. Báze by měla být co největší, aby se zmenšila velikost reprezentace dlouhých čísel a zvýšila rychlost operací s nimi, ale dostatečně malá, aby všechny operace s koeficienty používaly datový typ základ;
3. pro usnadnění výstupu a ladění můžete zvolit β jako mocninu 10, β - mocnina dvě umožňuje provádět rychlé operace na nízké úrovni.

BigInteger od společnosti Microsoft

Soukromé statické pouze pro čtení BigInteger s_bnMinInt = new BigInteger(-1, new uint( (uint) int.MinValue )); private static BigInteger s_bnOneInt = new BigInteger(1); private static BigInteger s_bnZeroInt = new BigInteger(0); private static BigInteger s_bnMinusOneInt = new BigInteger(-1); interní int _sign; interní uint_bits; private const int knMaskHighBit = -2147483648; private const uint kuMaskHighBit = 2147483648U; private const int kcbitUint = 32; private const int kcbitUlong = 64; private const int DecimalScaleFactorMask = 16711680; private const int DecimalSignMask = -2147483648;
Struktura obsahuje pouze dvě pole instance (_sign a _bits), zbývající pole jsou konstanty a pole statického čtení představující hodnoty struktury pro čísla -1, 0 a 1.

Můžeme předpokládat, že proměnná _sign ukládá znaménko čísla a pole _bits obsahuje koeficienty a i . Vzhledem k tomu, že pole _bits je typu uint, můžeme také předpokládat, že základ β je mocninou dvou 2 32 (protože uint je 32bitové číslo bez znaménka).

Pokusme se tedy naše domněnky potvrdit nebo vyvrátit.

Konstruktor, který bere int jako argument, vypadá takto:

Konstruktor přijímající int

public BigInteger(int value) (​if (value == int.MinValue) (​this = BigInteger.s_bnMinInt; ) else ( this._sign = hodnota; this._bits = (uint) null; ) )

Konstruktor, který bere uint jako argument, vypadá takto:

Konstruktér s uint

public BigInteger(hodnota uint) (​if (hodnota<= (uint) int.MaxValue) { this._sign = (int) value; this._bits = (uint) null; } else { this._sign = 1; this._bits = new uint; this._bits = value; } }

Následující konstruktor, který přijímá 64bitové číslo se znaménkem (dlouhé), pomůže odpovědět na otázku o výběru základu číselné soustavy:

Konstruktor, který přijímá dlouhé

public BigInteger(long value) (​if ((long) int.MinValue<= value && value <= (long) int.MaxValue) { if (value == (long) int.MinValue) { this = BigInteger.s_bnMinInt; } else { this._sign = (int) value; this._bits = (uint) null; } } else { ulong num; if (value < 0L) { num = (ulong) -value; this._sign = -1; } else { num = (ulong) value; this._sign = 1; } this._bits = new uint; this._bits = (uint) num; this._bits = (uint) (num >> 32); } }

This._bits = new uint; this._bits = (uint)num; this._bits = (uint) (num >> 32);
V tomto případě je 64bitové číslo num rozděleno na dvě 32bitová čísla: (uint)num a (uint)(num >> 32). První číslo představuje posledních 32 bitů num, zatímco druhé představuje prvních 32 bitů (posun doprava o n bitů je ekvivalentní celočíselnému dělení 2n).

Určíme, jak dlouhé bude číslo.MaxValue = 2 63 -1 = 9223372036854775807 bude uložena ve struktuře BigInteger . Chcete-li to provést, vydělte to 2 32:

Ve skutečnosti (uint)long.MaxValue = 4294967295, (uint)(long.MaxValue >> 32) = 2147483647.

Takže 9223372036854775807 = 2147483647*(2 32) 1 + 4294967295*(2 32) 0 a BigInteger
bude zastoupena dvojice:

_sign = 1
_bits = (4294967295, 2147483647) // zapamatujte si, že číslo je uloženo zpětně

Pro dlouhé číslo -1234567891011121314151617181920 máme:

To znamená, že číslo je rozšířeno na mocniny 2 32 takto:
1234567891011121314151617181920 = 15*(2 32) 3 + 2501550035*(2 32) 2 + 3243814879*(2 32) 1 + 4035623136*(2 32) 0

Prostředek, BigInteger bude zastoupena dvojice:

_sign = -1 // znak čísla
_bits = (4035623136, 3243814879, 2501550035, 15)

Číslo, které se vejde do rozsahu int, řekněme 17, bude uloženo takto:

_sign = 17
_bits = null

Zkoumání konstruktérů struktur BigInteger můžeme uzavřít:

1. pokud se číslo vejde do rozsahu int, pak se uloží do proměnné _sign;
2. pokud se číslo nevejde do rozsahu int, pak je jeho znaménko uloženo v proměnné _sign (-1 pro záporné a 1 pro kladné) a pole _bits obsahuje koeficienty a i rozšíření dlouhého čísla se základem 2 32 .

Obecně platí, že struktura BigInteger je kompletní implementace dlouhé aritmetiky na platformě .NET. Microsoft se ho zároveň snažil co nejvíce přiblížit primitivním číselným typům: instance BigInteger lze použít stejně jako jakýkoli jiný celočíselný typ. BigInteger přetěžuje standardní numerické operátory pro provádění základních matematických operací, jako je sčítání, odčítání, dělení, násobení, odčítání, negace a jednočlenná negace. Můžete také použít standardní číselné operátory k vzájemnému porovnání dvou hodnot BigInteger. Stejně jako jiné celočíselné typy, BigInteger Podporuje bitové operátory And, Or, XOR, vlevo a vpravo.

U jazyků, které nepodporují uživatelem definované operátory, struktura BigInteger také poskytuje ekvivalentní metody provádět matematické operace. To platí pro metody sčítání, dělení, násobení, negace, odečítání a některé další. Microsoft udělal to samé při implementaci struktury Desetinný .

Mnoho členů struktury BigInteger odpovídají přímo členům jiných celočíselných typů. Kromě, BigInteger přidává prvky jako:

• IsEven – určuje, zda je číslo sudé;
• IsPowerOfTwo - určuje, zda je číslo mocninou dvou;
• Znaménko - vrací hodnotu označující znaménko velkého celého čísla;
• Abs - vrátí absolutní hodnotu čísla BigInteger;
• DivRem - vrátí podíl a zbytek operace dělení;
• GreatestCommonDivisor - vrátí největšího společného dělitele dvou čísel;
• Log - vrací logaritmus zadaného čísla v číselné soustavě se zadaným základem;
• Max/Min - vrací největší/nejmenší ze dvou čísel;
• ModPow - provádí modulární dělení čísla umocněného na jiné číslo;
• Pow - zvýší hodnotu BigInteger na danou mocninu.

Pár slov o BigInteger v Mono a Javě

To znamená, že číslo 17 v Mono bude reprezentováno dvojicí:

_sign = 1 // znak čísla
_bits = (17)

Podobná implementace BigInteger zastoupené v Javě:

Veřejná třída BigInteger rozšiřuje Number implementuje Comparable ( int signum; int mag; private int bitCount = -1; private int bitLength = -1; private int nejnižšíSetBit = -2; private int firstNonzeroByteNum = -2; private int firstNonzeroIntNum = -2; private final static long LONG_MASK = 0xffffffffL; )
Protože Java nemá nepodepsané typy, pole mag je typu int. V souladu s tím bude reprezentace dlouhého čísla v Javě a .NET odlišné. V .NET bude reprezentace o něco efektivnější, protože typ uint pokrývá větší rozsah:

Konstruktor, který přijímá dlouhé

private BigInteger(long val) ( if (val< 0) { signum = -1; val = -val; } else { signum = 1; } int highWord = (int)(val >>> 32); if (highWord == 0) ( mag = new int; mag = (int)val; ) else ( mag = new int; mag = highWord; mag = (int)val; ) )

Výkon BigInteger

Délka int = 1000000; BigInteger num = BigInteger.Parse("12345678910111213141516171819"); for (int i = 2; i< length; i++) { if (IsPrime(i)) num++; } Console.WriteLine(num);
Ačkoli se zdá, že tento příklad mění hodnotu existujícího objektu, není tomu tak. Objekty BigInteger neměnný, což znamená, že interně společný jazykový modul runtime skutečně vytvoří nový objekt BigInteger a přiřadí mu hodnotu o jednu větší než předchozí.

V v tomto příkladu, můžete provést následující: provádět mezioperační operace pomocí běžných číselných typů a poté použít BigInteger :

Délka int = 1000000; BigInteger num = BigInteger.Parse("12345678910111213141516171819"); int temp = 0; for (int i = 2; i< length; i++) { if (IsPrime(i)) temp++; } num += temp; Console.WriteLine(num);
Ostatní číselné typy .NET Framework jsou také neměnné. Nicméně, protože typ BigInteger nemá žádnou horní ani dolní hranici, jeho hodnoty mohou narůst do velmi vysokých hodnot a mít měřitelný dopad na výkon.

Místo závěru

Dlouhá aritmetika

Dlouhá aritmetika je množina software(datové struktury a algoritmy), které umožňují pracovat s čísly mnohem větších velikostí, než umožňují standardní datové typy.

Typy celočíselné dlouhé aritmetiky

Obecně lze říci, že i pouze v úlohách olympiády je sada nástrojů poměrně velká, takže udělejme klasifikaci různé typy dlouhá aritmetika.

Klasická dlouhá aritmetika

Základní myšlenkou je, že číslo je uloženo jako pole jeho číslic.

Čísla lze použít z jedné či druhé číselné soustavy, obvykle se používá desítková číselná soustava a její mocniny (deset tisíc, miliarda), nebo se používá binární číselná soustava.

Operace s čísly v tomto typu dlouhé aritmetiky se provádějí pomocí „školních“ algoritmů pro sčítání, odčítání, násobení a dlouhé dělení. Jsou však pro ně také použitelné rychlé algoritmy násobení: Fast Fourier Transform a Karatsuba Algorithm.

Zde popisujeme práci pouze s nezápornými dlouhými čísly. Pro podporu záporných čísel je nutné zavést a podporovat další příznak pro „negativitu“ čísla nebo pracovat v doplňkových kódech.

Datová struktura

Dlouhá čísla budeme ukládat jako vektor čísel, kde každý prvek je jedna číslice čísla.

Pro zvýšení efektivity budeme pracovat v systému na bázi základní miliardy, tzn. Každý prvek vektoru neobsahuje jednu, ale všechny číslice najednou:

Číslice budou ve vektoru uloženy v takovém pořadí, aby na prvním místě byly nejméně významné číslice (tj. jedničky, desítky, stovky atd.).

Všechny operace budou navíc implementovány tak, že po provedení kterékoli z nich nebudou žádné úvodní nuly (tj. nuly navíc na začátku čísla) (samozřejmě za předpokladu, že před každou z nich nebudou žádné úvodní nuly). úkon). Je třeba poznamenat, že v prezentované implementaci jsou pro číslo nula správně podporovány dvě reprezentace: prázdný vektor číslic a vektor číslic obsahující jediný prvek - nulu.

Závěr

Nejjednodušší je vytisknout dlouhé číslo.

Nejprve jednoduše vytiskneme úplně poslední prvek vektoru (nebo , je-li vektor prázdný) a poté vytiskneme všechny zbývající prvky vektoru a doplníme je nulami před znaky:

(zde je malý jemný bod: nezapomeňte si zapsat typové obsazení, protože jinak bude číslo bez znaménka, a pokud , pak při odečítání dojde k přetečení)

Čtení

Načteme řetězec do a poté jej převedeme na vektor:

Pokud místo toho použijete pole "s", kód bude ještě kompaktnější:

Pokud vstupní číslo již může obsahovat úvodní nuly, lze je po přečtení odstranit tímto způsobem:

Přidání

Přidá číslo k číslu a uloží výsledek do:

Odčítání

Odečte číslo () od čísla a uloží výsledek do:

Zde po provedení odečítání odstraníme úvodní nuly, abychom podpořili predikát, že žádné úvodní nuly nejsou.

Násobení dlouhým krátkým

Vynásobí long krátkým() a výsledek uloží do:

Zde po provedení dělení odstraníme úvodní nuly, abychom podpořili predikát, že žádné úvodní nuly nejsou.

(Poznámka: metoda další optimalizace. Pokud je rychlost operace extrémně důležitá, můžete zkusit nahradit dvě dělení jedním: počítejte pouze celočíselnou část dělení (v kódu je to proměnná) a poté z ní vypočítejte zbytek dělení (pomocí jednoho násobení úkon). Tato technika vám zpravidla umožňuje zrychlit kód, i když ne příliš výrazně.)

Násobení dvou dlouhých čísel

Vynásobí a uloží výsledek do:

Lnum c(a.size() + b.size()); for (velikost_t i= 0 ; i< a.size () ; ++ i) for (int j= 0 , carry= 0 ; j< (int ) b.size () || carry; ++ j) { long long cur = c[ i+ j] + a[ i] * 1ll * (j < (int ) b.size () ? b[ j] : 0 ) + carry; c[ i+ j] = int (cur % base) ; carry = int (cur / base) ; } while (c.size () >1 && c.back () == 0 ) c.pop_back () ;

Dělení dlouhé na krátké

Dělí dlouhé krátkým (), ukládá kvocient v , zbytek v:

Dlouhá aritmetika v faktorizované formě

Smyslem je zde ukládat nikoli samotné číslo, ale jeho rozklad na rozklad, tzn. stupně každého prvočísla v něm obsaženého.

Tato metoda je také velmi jednoduchá na implementaci a je velmi snadné provádět operace násobení a dělení, ale není možné provádět sčítání nebo odčítání. Na druhou stranu tato metoda oproti „klasickému“ přístupu výrazně šetří paměť a umožňuje násobení a dělení mnohem (asymptoticky) rychleji.

Tato metoda se často používá, když je nutné dělit komplexním modulem: pak stačí uložit číslo ve formě mocnin prvočíselných dělitelů tohoto modulu a další číslo - zbytek stejného modulu.

Dlouhá aritmetika pomocí systému jednoduchých modulů (čínský teorém nebo Garnerovo schéma)

Myšlenka je taková, že se vybere určitý systém modulů (obvykle malých, které se vejdou do standardních datových typů) a počet se uloží jako vektor zbytků z jeho rozdělení každým z těchto modulů.

Jak uvádí čínská věta o zbytku, stačí to k jedinečnému uložení libovolného čísla v rozsahu od 0 do součinu těchto modulů mínus jedna. Zároveň existuje Garnerův algoritmus, který umožňuje tuto obnovu z modulární formy do obvyklé, „klasické“ podoby čísla.

Tato metoda tedy umožňuje úsporu paměti ve srovnání s "klasickou" dlouhou aritmetikou (i když v některých případech ne tak radikální jako metoda faktorizace). V modulární formě je navíc možné velmi rychle provádět sčítání, odčítání a násobení - to vše v asymptoticky krátkém čase, úměrném počtu modulů systému.

To vše je však za cenu velmi pracného překladu čísla z tohoto modulárního tvaru do běžného tvaru, který kromě značné časové náročnosti vyžaduje i implementaci „klasické“ dlouhé aritmetiky s násobením.

Kromě toho vyrábět divizečísla v takové reprezentaci pomocí systému jednoduchých modulů není možné.

Typy zlomkové dlouhé aritmetiky

Operace se zlomkovými čísly se v úlohách olympiády vyskytují mnohem méně často a práce s obrovskými zlomkovými čísly je mnohem obtížnější, takže v olympiádách se nachází pouze specifická podmnožina dlouhé zlomkové aritmetiky.

Dlouhá aritmetika v neredukovatelných zlomcích

Číslo je reprezentováno jako neredukovatelný zlomek , kde a jsou celá čísla. Pak lze všechny operace se zlomkovými čísly snadno zredukovat na operace s čitateli a jmenovateli těchto zlomků.

Obvykle je v tomto případě nutné pro uložení čitatele a jmenovatele použít také dlouhou aritmetiku, ale její nejjednodušší formou je „klasická“ dlouhá aritmetika, i když někdy stačí vestavěný 64bitový číselný typ.

Z pozice s plovoucí desetinnou čárkou se stane samostatný typ

Někdy problém vyžaduje provedení výpočtů s velmi velkými nebo velmi malými čísly, ale zároveň zabránit jejich přetečení. Je známo, že vestavěný typ bajtu umožňuje hodnoty exponentů v rozsahu , což někdy nemusí být dostatečné.

Technika je ve skutečnosti velmi jednoduchá - zavádí se další celočíselná proměnná, která je zodpovědná za exponent, a po provedení každé operace zlomkové číslo"normalizuje", tzn. se vrátí do segmentu zvýšením nebo snížením exponentu.

Při násobení nebo dělení dvou takových čísel musíte odpovídajícím způsobem přičíst nebo odečíst jejich exponenty. Při sčítání nebo odčítání by se před provedením této operace měla čísla zmenšit na jeden exponent, u kterého se jedno z nich vynásobí mocninou rozdílu exponentu.

Konečně je jasné, že není nutné volit za základ exponenciály. Na základě struktury vestavěných typů s plovoucí desetinnou čárkou se jeví jako nejvýhodnější nastavit základ rovný .

Při řešení určitého počtu problémů nastávají situace, kdy výsledky nebo mezivýpočty nelze uložit v žádném z platných typů programovacího jazyka. Poté se musíte obrátit na část programování nazvanou dlouhá aritmetika.

Pro řešení různé typy problémy dlouhé aritmetiky platí stejný princip. Každá číslice čísla je uložena v samostatném prvku pole. Pro usnadnění přidávání nové číslice jsou čísla uložena v obráceném pořadí a délka čísla může být uložena v samostatné proměnné nebo v nulovém prvku pole.

Problém se sčítáním

Algoritmus řešení

Problém se řeší stejným způsobem jako při přidávání do sloupce. Sčítání provádíme pro každou číslici zvlášť. Pokud je součet větší než 9, vezměte zbytek při dělení čísla 10 a nezapomeňte přidat počet desítek k další nejvyšší číslici

Programový kód

jestliže c>0 pak begin len:=délka+1; a:=c; konec;

for i:=len downto 1 do (výsledek vypíše do souboru) Write(f2,a[i]); close(f2); konec.

Algoritmus řešení

Na rozdíl od sčítacího problému si nemůžeme vybrat, po jehož délce se budeme pohybovat, takže nejprve musíme zkontrolovat konečný výsledek pro jeho znaménko. To vás zbaví dalších potíží. Přímé nalezení rozdílu se neliší od nalezení rozdílu „odčítáním sloupců“.

Programový kód