Гарнерийн алгоритм¶

Хятадын үлдэгдлийн теорем-ийн үр дагавар бол бид том тоог бага бүхэл тооны массив ашиглан илэрхийлж болох явдал юм. Жишээ нь $p$ нь эхний $1000$ анхны тооны үржвэр байг. $p$ нь ойролцоогоор $3000$ оронтой.

$p$-ээс бага дурын тоо $a$-г $a_1, \ldots, a_k$ массив хэлбэрээр илэрхийлж болно, энд $a_i \equiv a \pmod{p_i}$. Гэвч үүнийг хийхийн тулд бид илэрхийллээс нь $a$ тоог хэрхэн буцаан гаргахыг мэдэх хэрэгтэй нь ойлгомжтой. Нэг аргыг Хятадын үлдэгдлийн теоремын өгүүлэлд авч үзсэн.

Энэ өгүүлэлд бид энэ зорилгоор мөн ашиглаж болох өөр нэг арга болох Гарнерийн алгоритмыг авч үзнэ.

Холимог суурьт илэрхийлэл¶

Бид $a$ тоог холимог суурьт илэрхийллээр илэрхийлж болно:

$$a = x_1 + x_2 p_1 + x_3 p_1 p_2 + \ldots + x_k p_1 \cdots p_{k-1} \text{ энд }x_i \in [0, p_i)$$

Холимог суурьт илэрхийлэл нь байрлалын тооллын систем бөгөөд хоёртын эсвэл аравтын тооллын систем мэтийн ердийн тооллын системүүдийн ерөнхийлөл юм. Жишээ нь аравтын тооллын систем нь суурь (радикс) нь 10 байх байрлалын тооллын систем юм. Тоо бүрийг $0$-ээс $9$ хоорондох $d_1 d_2 d_3 \dots d_n$ цифрүүдийн мөрөөр илэрхийлнэ. Жишээ нь $415$ мөр нь $4 \cdot 10^2 + 1 \cdot 10^1 + 5 \cdot 10^0$ тоог илэрхийлнэ. Ерөнхийдөө $d_1 d_2 d_3 \dots d_n$ цифрүүдийн мөр нь суурь $b$ бүхий байрлалын тооллын системд $d_1 b^{n-1} + d_2 b^{n-2} + \cdots + d_n b^0$ тоог илэрхийлнэ.

Холимог суурьт системд бидэнд нэг суурь байхаа больдог. Суурь нь байрлал бүрт өөр өөр байна.

Гарнерийн алгоритм¶

Гарнерийн алгоритм нь $x_1, \ldots, x_k$ цифрүүдийг тооцоолдог. Цифрүүд харьцангуй бага болохыг анхаараарай. $x_i$ цифр нь $0$-ээс $p_i - 1$ хоорондох бүхэл тоо юм.

$r_{ij}$ нь $p_j$ модулиар авсан $p_i$-ийн урвууг илэрхийлэг

$$r_{ij} = (p_i)^{-1} \pmod{p_j}$$

үүнийг Модулийн урвуу-д тайлбарласан алгоритмаар олж болно.

Холимог суурьт илэрхийллээс $a$-г эхний congruence тэгшитгэлд орлуулснаар бид дараахыг авна

$$a_1 \equiv x_1 \pmod{p_1}.$$

Хоёр дахь тэгшитгэлд орлуулснаар

$$a_2 \equiv x_1 + x_2 p_1 \pmod{p_2},$$

гарах ба үүнийг $x_1$-г хасаж, $p_1$-д хуваах замаар дахин бичвэл

$$\begin{array}{rclr} a_2 - x_1 &\equiv& x_2 p_1 &\pmod{p_2} \\ (a_2 - x_1) r_{12} &\equiv& x_2 &\pmod{p_2} \\ x_2 &\equiv& (a_2 - x_1) r_{12} &\pmod{p_2} \end{array}$$

Үүнтэй адилаар бид дараахыг авна

$$x_3 \equiv ((a_3 - x_1) r_{13} - x_2) r_{23} \pmod{p_3}.$$

Одоо бид гарч ирж буй хэв маягийг тодорхой харж болох бөгөөд үүнийг дараах кодоор илэрхийлж болно:

for (int i = 0; i < k; ++i) {
    x[i] = a[i];
    for (int j = 0; j < i; ++j) {
        x[i] = r[j][i] * (x[i] - x[j]);

        x[i] = x[i] % p[i];
        if (x[i] < 0)
            x[i] += p[i];
    }
}

Ингэснээр бид $x_i$ цифрүүдийг $O(k^2)$ хугацаанд хэрхэн тооцоолохыг сурлаа. Одоо $a$ тоог өмнө дурдсан томьёогоор тооцоолж болно

$$a = x_1 + x_2 \cdot p_1 + x_3 \cdot p_1 \cdot p_2 + \ldots + x_k \cdot p_1 \cdots p_{k-1}$$

Практикт бид $a$ хариуг Дурын нарийвчлалтай арифметик ашиглан тооцоолох шаардлагатай болох нь бараг гарцаагүй боловч $x_i$ цифрүүдийг (тэдгээр нь бага тул) ихэвчлэн стандарт төрлүүдээр тооцоолж болох тул Гарнерийн алгоритм маш үр ашигтай гэдгийг тэмдэглэх нь зүйтэй.

Implementation of Garner's Algorithm¶

It is convenient to implement this algorithm using Java, because it has built-in support for large numbers through the BigInteger class.

Here we show an implementation that can store big numbers in the form of a set of congruence equations. It supports addition, subtraction and multiplication. And with Garner's algorithm we can convert the set of equations into the unique integer. In this code, we take 100 prime numbers greater than $10^9$, which allows representing numbers as large as $10^{900}$.

final int SZ = 100;
int pr[] = new int[SZ];
int r[][] = new int[SZ][SZ];

void init() {
    for (int x = 1000 * 1000 * 1000, i = 0; i < SZ; ++x)
        if (BigInteger.valueOf(x).isProbablePrime(100))
            pr[i++] = x;

    for (int i = 0; i < SZ; ++i)
        for (int j = i + 1; j < SZ; ++j)
            r[i][j] =
                BigInteger.valueOf(pr[i]).modInverse(BigInteger.valueOf(pr[j])).intValue();
}

class Number {
    int a[] = new int[SZ];

    public Number() {
    }

    public Number(int n) {
        for (int i = 0; i < SZ; ++i)
            a[i] = n % pr[i];
    }

    public Number(BigInteger n) {
        for (int i = 0; i < SZ; ++i)
            a[i] = n.mod(BigInteger.valueOf(pr[i])).intValue();
    }

    public Number add(Number n) {
        Number result = new Number();
        for (int i = 0; i < SZ; ++i)
            result.a[i] = (a[i] + n.a[i]) % pr[i];
        return result;
    }

    public Number subtract(Number n) {
        Number result = new Number();
        for (int i = 0; i < SZ; ++i)
            result.a[i] = (a[i] - n.a[i] + pr[i]) % pr[i];
        return result;
    }

    public Number multiply(Number n) {
        Number result = new Number();
        for (int i = 0; i < SZ; ++i)
            result.a[i] = (int)((a[i] * 1l * n.a[i]) % pr[i]);
        return result;
    }

    public BigInteger bigIntegerValue(boolean can_be_negative) {
        BigInteger result = BigInteger.ZERO, mult = BigInteger.ONE;
        int x[] = new int[SZ];
        for (int i = 0; i < SZ; ++i) {
            x[i] = a[i];
            for (int j = 0; j < i; ++j) {
                long cur = (x[i] - x[j]) * 1l * r[j][i];
                x[i] = (int)((cur % pr[i] + pr[i]) % pr[i]);
            }
            result = result.add(mult.multiply(BigInteger.valueOf(x[i])));
            mult = mult.multiply(BigInteger.valueOf(pr[i]));
        }

        if (can_be_negative)
            if (result.compareTo(mult.shiftRight(1)) >= 0)
                result = result.subtract(mult);

        return result;
    }
}