\Section{Деление длинных чисел}{6 мая}{Илья Кайсин}

Обозначения: $n$ --- длина делимого в двоичной системе, $m$ --- длина делителя в двоичной системе, $w$ --- длина машинного слова (пропорциональна основанию нашей системы счисления)


\Subsection{Двоичный поиск по частному}

Двоичным поиском перебираем частное. Логарифм частного --- его длина, т. е. примерно $n - m$. Для проверки используем умножение в столбик, получаем асимптотику $\O(m(n - m)^2/w^2)$. На $w$ делим потому что длины чисел в нашей системе счисления в $w$ раз меньше, чем в двоичной.

\Subsection{Двоичный поиск по цифре}

Делим в столбик. Цифру подбираем двоичным поиском, который работает за $\O(w)$. Асимптотика --- $\O(n(n - m)/w)$.

\Subsection{Деление за честный квадрат}

Научимся получать цифру без бинпоиска.

Пусть надо разделить $X = \overline{x_0x_1 \dots x_{n - 1}}$ на $Y = \overline{y_0y_1 \dots y_m}$. Разделим два вещественных числа $x = \overline{x_0,x_1x_2\dots}$ на $y = \overline{y_0,y_1y_2 \dots}$ с нужной точностью и домножим на B в нужной степени (B --- основание системы счисления). 

Важное замечание. В алгоритме $x_0$ не всегда будет цифрой, но будет сохраняться инвариант: $x_0 \leqslant y_0B$.

Пусть $x/y = z = \overline{z_0,z_1z_2\dots}$. Сперва получим $z_0$. Известно, что $z_0 = \lfloor \frac{x}{y} \rfloor$ но как посчитать $\lfloor \frac{x}{y} \rfloor$? Оценим $z_0$ снизу чем-то, что мы можем быстро посчитать: $z_0 \geqslant \lfloor \frac{x_0 + x_1B^{-1}}{y_0 + y_1B^{-1} + B^{-1}} \rfloor = \lfloor \frac{x_0B + x_1}{y_0B + y_1 + 1} \rfloor =: L$ (числитель -- уменьшенный $x$, знаменатель --- увеличенный $y$). Оказывается, $L$ отличается от $z_0$ несильно.

\begin{Thm} 
	$z_0 - L \leqslant 4$.
\end{Thm}

\begin{proof}
	Аналогично нижней границе существует и верхняя: $R := \lfloor \frac{x_0B + x_1 + 1}{y_0B + y_1} \rfloor \geqslant z_0$. 
	$$z_0 - L \leqslant R - L = \lfloor \frac{x_0B + x_1 + 1}{y_0B + y_1} \rfloor - \lfloor \frac{x_0B + x_1}{y_0B + y_1 + 1} \rfloor \leqslant \frac{x_0B + x_1 + 1}{y_0B + y_1} + 1  -  \frac{x_0B + x_1}{y_0B + y_1 + 1} = $$ $$ = \frac{x_0B + x_1 + y_0B + y_1}{(y_0B+y_1)(y_0B+y_1+1)} + 1 \leqslant \frac{y_0B^2 + (B-1) + y_0B + (B - 1) }{y_0^2B^2} + 1 \leqslant 4$$
\end{proof}

Таким образом, мы можем за $\O(1)$ вычислить $L$ и перебрать следующие 4 цифры.
Псевдокод:

\begin{code}
x -= y * L;
while (x >= y) 
	x -= y, ++L;
\end{code}

После вычитания $yz_0$ из $x$ сдвигаем запятую в $a$ вправо на одну позицию, поддерживая инвариант $x_0 \leqslant y_0B$. После этого так же получаем $z_1$, $z_2$ и так далее. 

Для получения одной цифры мы использовали константное число линейных операций (вычитания и умножения на цифру). Асимптотика --- $\O(n(n - m)/w^2)$.

\Subsection{Деление за $\O(n\log^2 n)$}

Для понимания рекомендуется сначала ознакомиться с предыдущим алгоритмом.

Воспользуемся тем же фокусом, что и в предыдущем алгоритме, только получим не одну цифру, а сразу $n/2$. Для этого поделим $x' := \overline{x_0, x_1 \dots x_{k}}$ на $y' := \overline{y_0, y_1 \dots y_{k}}$ ($k := \frac{n}{2} + 1$), а точнее, получим $L := \frac{x'}{y' + B^{-k}}$ --- нижнюю границу для $z$.

$z' := \overline{z_0, z_1 \dots z_{k - 1}}$

$z - z' \leqslant B^{-(k - 1)}$, поэтому $L - B^{-(k - 1)}$ является нижней границей для $z'$.

\begin{Thm}

	$z' - (L - B^{-(k - 1)}) \leqslant 3B^{-(k - 1)}$

\end{Thm}

\begin{proof}

	$$R:= \frac{x' + B^{-k}}{y'} \geqslant z \geqslant z'$$

	$$R - (L - B^{-(k - 1)}) \leqslant \frac{x' + B^{-k}}{y'}  - \frac{x'}{y' + B^{-k}} + B^{-(k - 1)} = \frac{(x' + y' + B^{-k})B^{-k}}{y'(y' + B^{-k})} + B^{-(k - 1)} \leqslant $$ $$ \leqslant (x' + y' + B^{-k})B^{-k} + B^{-(k - 1)} \leqslant 2B \cdot B^{-k} + B^{-(k - 1)} = 3B^{-(k - 1)}$$

\end{proof}

Таким образом, с помощью рекурсивного вызова от чисел вдвое меньшей длины мы получили почти точно $z'$. Чтобы получить $z'$ точно, нужно поступить аналогично предыдущему алгоритму и повычитать $yB^{-(k - 1)}$ из $x$ ещё некоторое (константное) количество раз.

Итак, мы получили $z'$ --- первую часть цифр, осталось получить вторую часть. Пусть $\frac{x}{y} = z' + z'' \cdot B^{-k}$, где $z'' < B$. Тогда x Тогда $z'' = \frac{(x - z'y)B^k}{y}$. Нас интересуют первые $k$ цифр числа $z''$, поэтому поступим так же, как и раньше, разделив первые $k + 1$ цифр $(x - z'y)B^k$ на первые $k + 1$ цифр $y$ рекурсивным вызовом и уточнив затем результат.


Оценим время работы алгоритма. 

$T(n) = \O(n \log n) + 2T(n/2 + 1)$, где $n \log n$ --- время работы умножения z' на y, используем FFT. 

$T(n) = \O(n \log^2 n)$.

Cуществует также алгоритм деления за $\O(n \log n)$.


