
\Section{Длинная арифметика}{13 мая}{Андрей Тонких}

    \begin{Lm}{}
        многочлены $\EQ$ целые неотрицательные $\EQ$ целые со знаком $\EQ$ вещественные
    \end{Lm}

    Длинные числа можно хранить как массив фиксированной (\texttt{a[N]}) или динамической (\texttt{vector<int> a}) длины.

\Subsection{Простые операции}

    За $\O(n)$:

    \begin{itemize}
        \item длинное \texttt{[$+|-|<$]} длинное \\
        \item длинное \texttt{[$\cdot|\div$]} короткое ($0 \le x < BASE$) (одна цифра в системе счисления $BASE$) \\
    \end{itemize}

    Псевдокод умножения длинного на короткое (цифру): % проверено
    \begin{code}
operator*(a, x) -> result:
    `// сначала без переносов`
    for i in [0; N):
        a[i] *= x

    `// теперь делаем переносы`
    for i in [0; N - 1):
        if a[i] >= BASE:
            a[i + 1] += a[i] / BASE
            a[i] %= BASE

    return a
    \end{code}

    Псевдокод деления длинного на короткое: % проверено
    \begin{code}
div(a, x) -> (result, rest):
    var carry = 0
    for i in [0; N).reversed():
        a[i] += carry * BASE
        carry = a[i] % x
        a[i] /= x

    return (a, carry)
    \end{code}


\Subsection{Умножение длинных чисел}

    \begin{enumerate}
        \item за $\O(nm)$, эффективно при небольшой длине ($length \le C$, где $C \approx 8$) \\
        \item за $\O(n^{\log_2 3}) = \O(n^{1.5849...})$, используя трюк Карацубы \\
        \item за $\O(n \log n)$, используя быстрое преобразование Фурье \\
    \end{enumerate}

    Псевдокод умножения многочленов за $\O(nm)$:
    \begin{code}
operator*(a, b) -> result:
    var an = a.length
    var bn = b.length

    var c = new BigInt(length = an + bn)

    for i in [0; an):
        for j in [0, bn):
            c[i + j] += a[i] * b[j]

    `// не нужно, если используются массивы фиксированной длины`
    while c.length > 1 && c.back == 0:
        c.pop_back
    \end{code}

    Псевдокод умножения длинного на длинное за $\O(nm)$, ускоренный для 64-битной архитектуры.
    \begin{code}
operator*(a, b) -> result:
    const BASE = 1e9
    const K = 7
    const M = K * BASE^2

    var an = a.length
    var bn = b.length

    var c = new BigInt(length = an + bn)

    for i in [0; an):
        for j in [0, bn):
            c[i + j] += a[i] * b[j]
            if c[i + j] >= M:
                c[i + j] -= M
                c[i + j + 2] += K

    for i in [0; an + bn - 1):
        c[i + 1] += c[i] / BASE
        c[i] %= BASE

    `// не нужно, если используются массивы фиксированной длины`
    while c.length > 1 && c.back == 0:
        c.pop_back
    \end{code}

\Subsection{Деление длинных чисел за $\O(nm)$}

    Псевдокод деления многочленов:
    \begin{code}
div(a, b) -> (result, rest):

    var an = a.length
    var bn = b.length

    for i in [bn - 1; an - 1].reversed():
        x = a[i] / b[bn - i]
        for j in [0; bn):
            a[i - j] -= x * b[bn - j - 1]
        c[i - bn - 1] = x

    return (c, a)
    \end{code}

\Subsection{Двоичная арифметика}

    % $BASE$ = степень двойки $\SO$ все операции с числом $2$ делаем быстро.

    Возведение в степень $= \log k$ умножений, где $k$ - степень, в которую возводим (не длина)

    Умножение $= \log k$ сложений, где $k$ - число, на которое умножаем.

    $\log k = \Theta(k.length)$

    Псевдокод деления за $\O(n^2)$: % проверено
    \begin{code}
div(a, b) -> (result, rest):
    if a < b:
        return (0, a)

    (c, r) = div(a, 2b)
    c *= 2

    if r >= b:
        r -= b
        c += 1

    return (c, r)
    \end{code}

    Пример: \\
    $(103 / 16) \to (6, 7)$  \\
    $(103 / 32) \to (3, 7)$ \\
    $(103 / 64) \to (1, 39)$ \\
    $(103 / 128) \to (0, 103)$ \\

    Псевдокод $\gcd$ за $\O(nm)$:
    \begin{code}
gcd(a, b) -> result:
    if a == 0:
        return b
    if b == 0
        return a

    if a % 2 == 0 && b % 2 == 0: `// проверяем за O(1)`
        return gcd(a / 2, b / 2) * 2
    
    while a % 2 == 0:
        a /= 2
    while b % 2 == 0:
        b /= 2

    if a < b:
        swap(a, b)
    return gcd(a - b, b)
    \end{code}    

    \begin{Thm}
        Все 3 функции за $\O(\frac{(\log_2 n)^2}{\omega})$, где $n$ - число (не длина).
    \end{Thm}

    \begin{proof}
        Копирование происходит за $\O(\frac{\log_2 n}{\omega})$
    \end{proof}
