Длинная арифметика

Материал из Algocode wiki
Перейти к: навигация, поиск

Того что тут написано вроде больше нигде нет на русском. Сама статья может быть достаточно сложной.

Нам понадобится Быстрое преобразование Фурье чтобы иметь умножение за $O(n \log n)$.

Быстрое деление двух чисел

У нас будут 2 функции, рекурсивно вызывающие друг друга. $n$ всегда будет являться точной степенью двух, $|a|$ будет обозначать длину числа a.

  1. div21 — делит число $a$ длиной не более $2n$ на число $b$ длиной не более $n$, при условии, что ответ по длине не превосходит $n$.
  2. div32 — делит число $a$ длиной не более $3n$ на число $b$ длиной не более $2n$, при условии, что ответ по длине не превосходит $n$.

Обе функции должны возвращать результат деления и остаток.

div21

Как работает div21: пусть $m=\frac{n}{2}$. Тогда $a$ имеет длину не более $4m$, на $b$ имеет длину не более $2m$, а ответ по длине не превосходит $2m$. Возьмём первые $|a| - m \le 3m$ цифр числа $a$ и разделим на число $b$ при помощи div32. Ответ по длине не превзойдёт $m$, так как иначе $a/b$ было бы больше по длине чем $2m$. Далее возьмём остаток после этого деления, домножим его на $10^m$, и припишем к нему последние $m$ цифр числа $a$. После этого разделим это число на $b$. Так как $|b| \le 2m$, то длина остатка не превосходит $2m$, значит длина остатка, домноженного на $10^m$ на превосходит $m$, тогда для деления мы можем использовать функцию div32. Далее умножим результат первого деления на $m$ и прибавил результат второго деления. Так мы получим ответ.

div32

Как работает div32: пусть $|b| \le n$. Тогда так как длина ответа не превосходит $n$, $|a| \le 2n$, тогда будем использовать $div21$. Иначе возьмём $b_1$, образованное первыми $n$ цифрами из $b$. Возьмём $a_1$, образованное первыми $|a| - (|b| - n)$ цифрами из $a$. (Т.е. обрежем $a$ и $b$ на одинаковое число цифр в конце так, чтобы длина $b$ стала равна $n$) Обозначим за $k = |b| - n$. (т.е. сколько цифр в конце мы отрезали от $a$ и от $b$). Обозначим за $r_a = a - a_1 \cdot 10^k$, $r_b = b - b_1 \cdot 10^k$. (т.е. обозначим за $r_a$ и $r_b$ то, что мы отрезали от $a$ и от $b$). Тогда $a / b = (a_1 \cdot 10^k + r_a) / (b_1 \cdot 10^k + r_b)$.


Утверждение:
${a_1} / {b_1} \ge {a}/{b}$

Доказательство:
Это верно так как $a_1 / b_1 = (a_1 \cdot 10^k) / (b_1 \cdot 10^k)$. Так как $k < n$, и $b_1 \le 10^n$, то для любого $x < 10^k$ $(a_1 \cdot 10^k + x) / (b_1 \cdot 10^k) = (a_1 \cdot 10^k) / (b_1 \cdot 10^k)$. Ну и тогда понятно, что $(a_1 \cdot 10^k + x) / (b_1 \cdot 10^k) \ge (a_1 \cdot 10^k + x) / b$ так как $b \ge b_1 \cdot 10^k$. Тогда если $x=r_a$, то мы всё доказали.

Сразу за этим утверждением следует следующее утверждение.


Утверждение:
${a_1} / ({b_1} + 1) \le {a}/{b}$

Доказательство:
Замечаем, что $b < (b_1 + 1) \cdot 10^k$. Тогда $\frac{a}{b} \ge \frac{a}{(b_1 + 1) \cdot 10^k}$. Дальше как и в прошлом утверждении так как у знаменателя $((b_1 + 1) \cdot 10^k)$ в конце $k$ нулей, то если от числителя отбросить последние $k$ цифр, результат не поменяется. Тогда получим, что $\frac{a}{(b_1 + 1) \cdot 10^k} = \frac{a_1}{b_1 + 1}$. Тогда ${a_1} / ({b_1} + 1) \le {a}/{b}$.

Тогда $a_1 / b_1 \ge a / b \ge a_1 / (b_1 + 1)$. Теперь возьмём $q = a_1 / b_1$ и будем пытаться получить из него $a / b$. Несложно заметить, что на самом деле $q \ge a / b \ge q - 10$. Для этого надо показать, что:


Утверждение:
$q - 10 \le a_1 / (b_1 + 1)$

Доказательство:
Домножим на $(b_1 + 1)$. $(q - 10) \cdot (b_1 + 1) = (a_1 / b_1 - 10) \cdot (b_1 + 1) = a_1 - 10 \cdot b_1 + q - 10$. Т.к. $q = a_1 / b_1$ по длине не превышает $n$, а $b$ по длине ровно равно $n$, то $10b > q$. Тогда в предыдущем выражении мы можем убрать $-10\cdot b_1 + q$ и от этого оно только возрастёт. Но тогда у нас останется $a_1 - 10$. Нетрудно понять, что это меньше $a_1$, а значит при домножении обеих частей искомого неравенства мы получили корректное неравенство. Тогда $q - 10 < a_1 / (b_1 + 1)$.

Тогда $a_1 / b_1 \ge a / b \ge a_1 / b_1 - 10$. Тогда для div32 получается следующий алгоритм. Строим числа $a_1$ и $b_1$. С помощью div21 разделим $a_1$ на $b_1$. (Если $a_1 > b_1 \cdot 10^n$, будем считать что результат равен $10^n - 1$). Далее вычтем из $a$ результат деления, домноженный на $b$ и посчитаем остаток от текущего деления. Пока остаток меньше нуля, будем прибавлять к нему $b$ и вычитать из частного 1. Таких действий мы сделаем не более $n$.

При совсем маленьких числах надо делить уже используя int-овое деление.

Можно увеличить базу с 10 до $10^9$, но делать это надо аккуратно.

Асимптотику доказать несложно. $div21(n)$ делает $O(n)$ действий и вызывает div32 два раза. $div32(n)$ делает $O(n \log n)$ действий (т.к. там есть операция умножения) и возможно вызывает $div21(n)$. Таким образом $div21(n)$ делает $O(n \log n)$ действий и два раза вызывает div21. Таким образом время работы $O(n \log^2 n)$.

Более подробное описание и доказательство этого алгоритма можно найти по ссылке

Быстрый корень произвольной степени

Метод Ньютона

Для начала рассмотрим алгоритм поиска корня $k$ степени за $O(n\log^3n)$ с огромной константой. Будем использовать Ньютоновский метод поиска нуля функции $f(x)$. Он работает итерациями~--- есть начальное число $x_0$. Далее $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$. Каждая следующая итерация приближает $x_n$ к нулю функции.

Тогда если мы возьмём функцию $f(x)=a-x^k$, то максимальный целый $x$, при котором функция положительна и есть корень $k$ степени из $a$. Тогда $f'(x) = -k\cdot x^{k - 1}$. Тогда $$x_{n + 1} = x_n + \frac{a}{k \cdot x_n^{k - 1}} - \frac{x_n}{k}$$ Тогда если за $x_0$ взять $10^{n/k}$, то кол-во итераций будет $O(\log n)$ с большой константой, а в каждой производится операция деления, т.е. асимптотика — $O(nlog^3n)$.

Более быстрый алгоритм

То был общеизвестный алгоритм поиска корня который везде используется. Он не самый быстрый. А теперь будет описан другой алгоритм, который работает за $O(nlog^2n+klog^3k)$ c малой константой. Будем искать корень $k$ степени из $x$ рекурсивно. Но сначала чуть чуть математики. Если вы не хотите разбираться в этом говне, а хотите сразу алгоритм, то он написан ниже.

Пусть $\sqrt[k]{x} = a10^m+b$, где $b < 10^m$. Тогда

$$x=a^k10^{km}+ka^{k-1}b10^{(k-1)m}+\frac{k(k-1)}{2}a^{k-2}b^2 10^{(k-2)m}+...+b^k$$

Тогда если $a > b$ и $10^m > k$ то

$$\frac{k(k-1)}{2}a^{k-2}b^{2}10^{(k-2)m} > \frac{k(k-1)(k-2)}{1\cdot2\cdot3}a^{k-3}b^{3}10^{(k-3)m} > ... > b^k$$

Тогда

$$k\left(\frac{k(k-1)}{2}a^{k-2}b^{2}10^{(k-2)m} \right)> \frac{k(k-1)}{2}a^{k-2}b^{2}10^{(k-2)m} + \frac{k(k-1)(k-2)}{1\cdot2\cdot3}a^{k-3}b^{3}10^{(k-3)m} + ... + b^k$$

Тогда если $b<10^m <a$ и $10^m>k^2$ то

$$a^{k-1}\cdot10^{(k-1)m}> k\left(\frac{k(k-1)}{2}a^{k-2}b^{2}10^{(k-2)m} \right)> \frac{k(k-1)}{2}a^{k-2}b^{2}10^{(k-2)m} + \frac{k(k-1)(k-2)}{1\cdot2\cdot3}a^{k-3}b^{3}10^{(k-3)m} + ... + b^k$$

А из этого следует уже не такой ужасный алгоритм.

Пусть $n$ - длина числа $x$, из которого мы ищем корень. Пусть $m=\frac{n-1}{2k}$. Тогда если $10^m\leq k^2$, то ищем корень методом Ньютона. Иначе возьмём число $x$ без последних $km$ цифр. Пусть $a$ - корень из этого числа. Тогда замечаем, что $\sqrt[k]{x}$ имеет вид $a10^m+b$, где $b < 10^m$. При этом $b<10^m <a$ и $10^m>k^2$. Тогда верно последнее большое неравенство, описанное выше. Тогда $b=(x-a^k10^{km})/(a^{k-1}10^{(k-1)m})$ или на единицу меньше. Тогда совершив такое деление и проверив, надо ли вычесть 1 из $b$ мы найдём $\sqrt[k]{x}$. Замечаем, что самое большое по асимптотике действие, которое мы сделаем — деление, а далее вызовемся от числа, в 2 раза меньшего нас по длине. Тогда так как в конце нам ещё придётся искать корень методом Ньютона из числа, по длине примерно равному $k$, то всего асимптотика — $O(nlog^2n+klog^3k)$.



Автор конспекта: Филипп Грибов

По всем вопросам пишите в telegram @grphil