Pokud bychom chtěli zjistit, kolik paměti nám zabírá které číslo, bude se nám hodit funkce mpz_sizeinbase, které předáme jako druhý parametr základ 2 (chceme velikost v binární soustavě). Výsledek pro základ 2 je vždy přesný.
mpz_set_str(num, "1000000", 10);
printf("bits = %zu\n", mpz_sizeinbase(num, 2)); /* vypíše bits = 20 */
Dále se podíváme na umocňování. Výsledky umocňování mají tendenci růst do závratných výšin. Proto se dá mpz_t umocnit jen na unsigned long. Například 1021 spočteme takhle:
mpz_t num; mpz_init_set_ui(num, 10UL); mpz_pow_ui(num, num, 21UL); /* num = 10^21 */ mpz_clear(num);
V příkladu také vidíme, že inicializaci a přiřazení hodnoty lze spojit do jediné funkce mpz_init_set_ui.
Pokud se zabýváte teorií čísel, mohl by pro vás být zajímavý výpočet operace modulo. Ten můžeme realizovat samostatnou funkcí mpz_mod, kde jsou dělenec i dělitel typu mpz_t.
mpz_set_ui(n, 11UL);
mpz_set_ui(d, 5UL);
mpz_mod(r, n, d); /* r = n mod d */
gmp_printf("r = %Zi\n", r); /* vypíše r = 1, protože n = 2 * 5 + 1 */
Když se teď opět vrátíme k umocňování, můžeme rovnou využít funkci mpz_powm, která spočte mocninu v daném modulu.
mpz_set_ui(b, 10UL);
mpz_set_ui(e, 21UL);
mpz_set_ui(m, 3UL);
mpz_powm(r, b, e, m); /* spočítá 10^21 mod 3 */
gmp_printf("r = %Zi\n", r); /* vypíše zbytek po dělení 10^21 / 3, což je 1 */
Tentokrát vidíme, že mpz_t lze umocnit na mpz_t, ale pohybujeme se v nějakém omezeném modulu.
Dále se podíváme na výpočet největšího společného dělitele dvou čísel. K tomu slouží funkce mpz_gcd, jejíž použití je velmi jednoduché:
mpz_set_ui(a, 37107UL); /* 37107 = 3 * 3 * 7 * 19 * 31 */
mpz_set_ui(b, 1254UL); /* 1254 = 2 * 3 * 11 * 19 */;
mpz_gcd(r, a, b);
gmp_printf("r = %Zi\n", r); /* vypíše 57 = 3 * 19 */
A co třeba výpočet faktoriálu? Ten můžeme realizovat funkcí mpz_fac_ui:
mpz_fac_ui(r, 25UL);
gmp_printf("r = %Zi\n", r); /* vypíše 15 511 210 043 330 985 984 000 000 (bez mezer) */
Teď se podíváme na generování pseudonáhodných čísel. Klíčem je proměnná typu gmp_randstate_t. Tu je třeba nejprve inicializovat pomocí funkce gmp_randinit_default, která použije jako generátor Mersenne Twister. Následně nastavíme náhodné semínko pomocí volání gmp_randseed_ui. Jednotlivá náhodná čísla v rozmezí 0 až n − 1 se pak generují voláním mpz_urandomm, přičemž n předáme jako poslední parametr.
gmp_randstate_t state;
gmp_randinit_default(state);
gmp_randseed_ui(state, 42UL);
mpz_set_ui(n, 100UL); /* rozsah [0; 100-1] */
for (int i = 0; i < 10; ++i) {
mpz_urandomm(r, state, n);
gmp_printf("%Zi\n", r);
}
Nyní se podíváme na manipulaci s bity. S čísly můžeme pracovat jako ve dvojkovém doplňku (ačkoli ve skutečnosti takto nejsou v paměti uložena). Můžeme použít bitové operace AND, OR a XOR. Například pro operaci AND máme k dispozici funkci mpz_and. Použití vypadá následovně.
mpz_set_ui(a, 85UL); /* 1010101 */
mpz_set_ui(b, 31UL); /* 11111 */;
mpz_and(r, a, b);
gmp_printf("r = %Zi\n", r); /* vypíše r = 21, což je 10101 */
Podobně existují i funkce mpz_ior a mpz_xor. Stejně tak máme k dispozici třeba operaci popcount (počet bitů, které jsou nastaveny na 1) pomocí funkce mpz_popcount.
mp_bitcnt_t pcnt;
mpz_set_ui(a, 85UL); /* 1010101 */
pcnt = mpz_popcount(a);
printf("%zu\n", (size_t)pcnt); /* vypíše 4 */
Na závěr malý příklad. K tomu budeme potřebovat funkci mpz_mul_2exp, která spočítá bitový posun doleva neboli první operand krát dvě na druhý operand, tedy op1 × 2op2. Příklad hledá kandidáty na Mersennova prvočísla pomocí Fermatova testu prvočíselnosti se základem 3:
/* přes všechny liché exponenty */
for (unsigned long k = 1; ; k += 2) {
mpz_set_ui(Mp, 1UL); /* začneme s číslem 1 */
mpz_mul_2exp(Mp, Mp, k); /* spočteme 2^k */
mpz_sub_ui(Mp, Mp, 1UL); /* spočteme 2^k - 1 */
mpz_sub_ui(Mp_1, Mp, 1UL); /* dále spočteme 2^k - 2 */
mpz_set_ui(b, 3UL); /* základ bude 3 */
mpz_powm(x, b, Mp_1, Mp); /* vypočítat Fermatův test */
/* je-li výsledek kongruentní s 1 */
if (mpz_cmp_ui(x, 1UL) == 0) {
/* máme kandidáta na prvočíslo */
printf("PRP: %lu\n", k);
}
}
