naturals-arithm.tex

\section{Вычислительный аспект}

В первом параграфе мы определили арифметические операции над натуральными числами, но однако не сказали ни слова о том, как реально вычислять результат от их применения. Можно, конечно, использовать аксиомы напрямую. Так, для сложения $m+n$ в соответствии с аксиомами Пеано нам потребуется $n$ раз прибавить 1 к числу $m$. Скажем, вот так может начинаться процесс сложения $123+456$:
$$123+456 = 124 + 455 = 125 + 454 = 126 + 453 = \ldots$$
Очевидно, что этот способ никуда не годится. В этом параграфе мы рассмотрим каким образом можно проводить арифметические вычисления более-менее эффективно, но прежде введём новую для нас удобную нотацию.

Пусть $\{x_i\}$~--- некоторая последовательность и мы хотим сложить все элементы этой последовательности подряд начиная $x_a$ и заканчивая $x_b$. Кратко мы будем записывать эту сумму с помощью символа $\sum$:
$$\sum_{i=a}^b x_i = x_a + x_{a+1} + \ldots + x_b$$
Аналогичную краткую запись мы введём и для произведения:
$$\prod_{i=a}^b x_i = x_a \cdot x_{a+1} \cdot \ldots \cdot x_b$$
Для пронумерованного семейства множеств $\{S_i\}$ аналогично введём краткое обозначение для объединения и пересечения:
$$\bigcup_{i=a}^b A_i = A_a \cup A_{a+1}\cup\ldots\cup A_b$$
$$\bigcap_{i=a}^b A_i = A_a \cap A_{a+1}\cap\ldots\cap A_b$$
В полной аналогии можно обозначать конъюнкцию, дизъюнкцию и исключающее или  для логических высказываний да и вообще многие другие операции, но мы не будем на этом лишний раз останавливаться~--- эти обозначения и так очевидны и понятны.

Также введём следующее сокращение для многократного применения функции:
$$f^n(x) = \underbrace{(f\circ f\circ\ldots\circ f)}_n (x)$$

Пусть мы теперь хотим просуммировать не все элементы $x_i$ в каком-то диапазоне, а в точности те значения $x_i$, где $i$ принадлежит некоторому наперёд заданному множеству $S$. Это можно кратко записать так:
$$\sum_{i\in S} x_i$$
Аналогично можно записывать и прочие операции.

Пользуясь введённой нотацией любое натуральное число $n$, для представления которого требуется $k$ разрядов, можно записать в системе счисления с основанием $b$ таким образом:
$$n = \sum_{i=0}^{k-1} r_i b^i = r_{k - 1} b^{k-1} + \ldots + r_1 b + r_0$$
Или даже, если посчитать, что при $i\ge k$ все $r_i = 0$, можно избавиться в этой сумме от величины $k$:
$$n = \sum_{i=0}^\infty r_i b^i = \sum_{i\in\mathbb{N}} r_i b^i$$
Символом $\infty$ мы абстрактно обозначили <<бесконечность>>, что означает, что мы будем суммировать по всем значениям $i$ вообще. В общем случае возможность сложения бесконечного количества чисел вызывает сразу ряд вопросов, однако в нашей ситуации мы знаем, что лишь конечное число слагаемых $r_ib^i$ будет отлично от нуля, так что реально здесь суммируется по сути конечное число значений и проблемы с этим не возникает.

Пусть мы хотим сложить числа $a$ и $b$. Их разряды в системе счисления с основанием $d$ мы обозначим как $a_i$ и $b_i$ соответственно. Тогда, если вспомнить, что сложение может осуществляться в любом порядке и мы можем как угодно переставлять в суммах скобки (см.~\S3.1), мы элементарно получаем следующее соотношение:
$$\left(\sum_{i=0}^\infty a_i d^i\right) + \left(\sum_{i=0}^\infty b_i d^i\right) = \sum_{i=0}^\infty (a_i + b_i) d^i$$
Буквально здесь говорится, что мы можем складывать числа поразрядно. То есть для нашего примера с 123 и 456 мы можем отдельно сложить 1+4, 2+5 и 3+6. Результатом будет 579 (если вам непонятны эти рассуждения, распишите эти числа как сумму в десятичной системе счисления и проведите вычисления аккуратно).

Если мы теперь попытаемся сложить 579 и 123, то у нас выйдет проблема: $3+9=12$, что больше, чем основание системы счисления. Это значит, что 12 надо представить как $1\cdot10 + 2$, и теперь единица переходит в старший разряд. В итоге вместо $7+2$ мы должны во второй разряд записать $7+2+1=10$, что опять не умещается в систему счисления. Снова единица перейдет уже в третий разряд: $5+1+1$. Результат: 702.

Мы не будем останавливаться на этом подробно, так как все эти вещи совершенно тривиальны. В школах используется именно этот способ сложения, только для удобства записи числа записываются в столбик, разряд под разрядом, и в школе редко объясняют почему такой способ сложения вообще работает. Мы это только что доказали.

Вычитание практически аналогично сложению и мы не будем его рассматривать отдельно.

Так же легко определить и формулу для умножения (мы могли бы получить много разных вариантов, но именно этот вариант простой перестановки скобок~--- стандартный школьный):
$$\left(\sum_{i=0}^\infty a_i d^i \right)\left( \sum_{j=0}^\infty b_j d^j \right) = \sum_{i=0}^\infty \left(\sum_{j=0}^\infty a_i b_j d^j \right)d^i$$
Это выражение в точности дублирует умножение в столбик~--- каждый разряд числа $a$ по отдельности умножается на число $b$ целиком (опять же поразрядно). Не будем вдаваться в скучные подробности умножения в столбик, а обратим внимание на следующий важный аспект:

\begin{exercise}
Пусть даны два $n$-разрядных числа $a$ и $b$. Для их умножения приведенным способом потребуется $n^2$ операций умножения отдельных разрядов.
\end{exercise}

Если взять числа 23 и 45 и сложить их, то нам потребуется сложить разряды $2+4$ и $3+5$. Для умножения же этих чисел, потребуется вычислить произведения $2\cdot 4$, $2\cdot 5$, $3\cdot 4$ и $3\cdot 5$. Если взять не двузначные числа, а трехзначные, то при сложении нам потребуется сложить три разряда, а при умножении перемножить девять разрядов. Для сложения 100-разрядных чисел потребуется 100 операций сложения разрядов, а для умножения их же~--- 10000 операций умножения.

Как видно, сложность умножения (если выражать сложность в количестве операций)  значительно выше, нежели сложность сложения, причем чем больше числа по разрядности, тем значительнее возрастает сложность умножения, в отличие от сложения. Компьютер, конечно, вычислит это всё равно за доли секунды, какими бы длинным ни были перемножаемые числа, однако часто этого оказывается недостаточно. Умножение~--- это одна из самых базовых операций и зачастую она выполняется компьютером сотни или даже тысячи раз в секунду, например, при обработке графики или сложных физических расчетах. В таких условиях, разработчикам компьютерных систем становится принципиальным, чтобы умножение чисел компьютер мог успевать совершать не несколько раз за секунду, а несколько миллионов раз за секунду (а лучше~---больше). Понятно, что приведенный нами алгоритм, даже если и сможет работать так быстро в силу совершенства оборудования, будет сильно падать в эффективности при увеличении перемножаемых чисел.

Один из общих подходов к созданию быстрых алгоритмов называется <<Разделяй и властвуй>>. Идея состоит в том, чтобы некоторую крупную по размерам задачу разбить на ряд маленьких подзадач, обработать каждую из этих подзадач в отдельности, а затем объединить результат. Это довольно общие слова и как именно надо действовать зависит от конкретной задачи. Мы рассмотрим этот подход на примере умножения чисел.

Пусть числа $a$ и $b$ имеют $2d$ десятичных разрядов (возможно, меньше, тогда дополним их нулями). Запишем их в виде $a = a_H10^d + a_L$ и $b = b_H10^d + b_L$, где $a_H, a_L, b_H, b_L$ имеют по $d$ разрядов. Тогда их произведение может быть расписано простым раскрытием скобок:
\begin{align*}
ab &= (a_H10^d + a_L)(b_H10^d + b_L) \\
         &= a_Hb_H10^{2d} + a_Hb_L10^d + a_Lb_H10^d + a_Lb_L\\
         &= a_Hb_H10^{2d} + (a_Hb_L + a_Lb_H)10^d + a_Lb_L
\end{align*}
Здесь мы свели одно умножение $2d$-разрядных чисел к умножению четырех чисел, но уже $d$-разрядных и суммированию результатов. К сожалению, это нам пока ничего не даёт. Например, для двузначных чисел мы что раньше выполняли четыре умножения однозначных чисел, что теперь. Однако, этот метод возможно ускорить, применив так называемый трюк Карацубы (для многих неожиданно, что Карацуба был советским математиком родом из Чечни, закончившим грозненскую школу, и звали его Анатолий), который стал исторически первым эффективным алгоритмом типа <<Разделяй и властвуй>> и первым алгоритмом умножения, работающим быстрее чем за время $n^2$. Трюк заключается в вычислении произведения
$$c = (a_H + a_L)(b_H + b_L) = a_Hb_H + a_Hb_L + a_Lb_H + a_Lb_L$$
Если вычислить предварительно произведения $a_Hb_H$ и $a_Lb_L$, то получаем
$$a_Hb_L + a_Lb_H = c - a_Hb_H - a_Lb_L$$
В итоге теперь нам требуется вычислить не четыре произведения, а лишь три: $c$, $a_Hb_H$ и $a_Lb_L$, каждое из которых оперирует числами разрядности $d$, а затем вычислить требуемое значение $a_Hb_L + a_Lb_H$, используя $c$ и операцию вичитания, что намного быстрее. Каждое из этих произведений опять же может быть вычислено по алгоритму Карацубы, для чего придется опять перемножить три числа, на этот раз разрядности $d \over 2$. Процесс следует продолжать, пока мы не дойдём до одноразрядных чисел.

Подробный анализ быстродействия алгоритма Карацубы требует довольно отвлеченных от нашего нынешнего рассказа тем математики (их мы тоже рассмотрим, но позже), поэтому мы пока ограничимся лишь бездоказательным утверждением о том, что алгоритм Карацубы за счет сокращения четырех умножений до трёх, действительно даёт вычислительное преимущество при умножении чисел, в сравнении с умножением в столбик. Для умножения с использованием ручки и бумажки он не удобен, однако на компьютере он может быть запрограммирован элементарно в несколько строчек кода. Часто именно таким образом реализуется компьютерное умножение, хотя сейчас есть и более совершенные методы, один из которых мы будем рассматривать в этом курсе позже.

Возведение в степень легко осуществить по определению Пеано:
$$a^b = \prod_{i=1}^b a$$
но можно и быстрее, что опять же важно для компьютерных вычислений.

Пусть для начала нам надо возвести число $a$ в степень $2b$. По свойствам степени $a^{2b} = (a^b)^2$ и мы можем вначале возвести $a$ в степень $b$, а затем результат возвести в квадрат~--- одно это уже намного проще, чем производить умножение $2b - 1$ раз в соответствии с аксиомами Пеано.

Если же нам надо возвести число $a$ в степень $2b +1$, то мы можем поступить похожим образом: $a^{2b+1} = (a^b)^2a$. Мы вначале вычисляем $a^b$, затем возводим результат в квадрат, и в итоге умножаем результат опять на $a$. Подробный анализ быстродействия этого способа опять же выходит за рамки этого параграфа, но довольно очевидно, что преимущество, получаемое нами в данном случае, будет огромно.
\begin{exercise}
Покажите, что для возведения числа $x$ в степень 64 достаточно произвести всего 6 операций умножения в соответствии с приведенным подходом, против 63 умножений в соответствии с аксиомами Пеано.
\end{exercise}

Осталось рассмотреть лишь одну операцию~--- деление с остатком. Совсем простой подход я уже озвучивал в прошлом параграфе: чтобы поделить $a$ на $b$ с остатком, надо вычитать $b$ из $a$ до тех пор, пока результат не окажется меньше $b$. Например, поделим 123 с остатком на 40. После первого вычитания получаем 83 ($123 = 40 + 83$). После второго вычитания~--- 43 ($123 = 2\cdot 40 + 43$). После третьего~--- 3 ($123 = 3\cdot 40 + 3$). Итого и частное и остаток оказались равны трём.

Этот способ очень прост, но и очень неэффективен: как, например, таким способом поделить с остатком 12347 на 5?

Простая идея для ускорения вычислений заключается в том, чтобы вычитать делитель не по одному за итерацию, а сразу по нескольку. В случае с 12347 и 5 вместо того, чтобы вычитать многократно число 5, мы можем вычесть сразу некоторое число $5n$, где $n$ надо подобрать таким образом, чтобы $5n$ было не больше 12345. Удобнее всего здесь брать степени десяти (или основания той системы счисления, в которой мы работаем), помноженные на какое-то небольшое число. Для нашего примера удобно взять $n=2000$. Отсюда после первого вычитания получаем: $12347 = 5\cdot 2000 + 2347$. Для второго вычитания возьмём $n=400$:
$$12347 = 5\cdot 2000 + 5\cdot 400 + 347 = 5\cdot 2400 + 347$$
Теперь возьмём $n=60$: $12347 = 5\cdot 2460 + 47$. Взяв в последний раз $n=9$, получаем $12347 = 5\cdot 2469 + 2$. Это и есть желаемый ответ.

Приведенные рассуждения~--- это в точности школьное деление в столбик, но только расписанное подробно. Примерно таким образом работает и деление чисел в компьютере. На практике при компьютерной реализации этого алгоритма возникает целый ряд дополнительных вопросов, например каким именно образом наиболее быстро можно выбрать значение $n$, плюс к этому можно рассмотреть целый ряд усовершенствований, основанных на использовании двоичной системы счисления.

В заключение этого раздела мы спустимся в вычислительных системах еще на уровень ниже и кратко рассмотрим, каким образом реализуется арифметика на уровне компьютерного железа. Мы ограничимся рассмотрением только сложения, остальные операции читатель сможет сам домыслить по аналогии.

Очень абстрактно мы будем представлять себе один бит как контакт на компьютерной плате, по которому может либо идти напряжение (значение 1), либо не идти (значение 0). Мы будем также рассматривать логические блоки, которые имеют несколько входных контактов, и несколько выходных и которые реализуют некоторые логические операции. Одним из простейших логических блоков является блок, реализующий логическую операцию <<штрих Шеффера>>. В \S~1.2 мы упоминали, что абсолютно любую логическую операцию можно выразить с помощью него. Как пример, мы можем рассмотреть операцию <<И>>. Её выражение на языке логики с помощью штриха Шеффера такое: $a\land b = (a|b)|(a|b)$ (проверьте). Абстрактное представление этого выражения в том виде, как оно будет реализовано на логической схеме, представлено на рисунке~3.1.
\begin{figure}[h]
\centering
\begin{tikzpicture}
	\def\lblock{node [minimum height=1cm,minimum width=1.5cm,draw] }
	\def\spoint{node [circle, draw, fill, inner sep = 0, minimum size = 0.05cm] }
	\draw (-2cm, .5cm) \spoint (x) {};
	\draw (-2cm, -.5cm) \spoint (y) {};
	\node [above] at (x.north) {a};
	\node [below] at (y.south) {b};
	\draw (0, .7cm) \lblock (s1) {|};
	\draw (0, -.7cm) \lblock (s2) {|};
	\draw (3cm, 0) \lblock (s3) {|};
	\draw (4.5cm, 0) \spoint (xy) {};
	\node [above] at (xy.north) {$a\land b$};
	\draw [->] (s1.east) -- ($(s3.south west)!.75!(s3.north west)$);
	\draw [->] (s2.east) -- ($(s3.south west)!.25!(s3.north west)$);
	\draw [->] (x.east) -- ($(s1.south west)!.75!(s1.north west)$);
	\draw [->] (x.east) -- ($(s2.south west)!.75!(s2.north west)$);
	\draw [->] (y.east) -- ($(s1.south west)!.25!(s1.north west)$);
	\draw [->] (y.east) -- ($(s2.south west)!.25!(s2.north west)$);
	\draw [->] (s3.east) -- (xy.west);
\end{tikzpicture}
\caption{Схема операции <<Логическое И>>}
\end{figure}

Теперь перейдём к построению схемы сложения чисел. За $n$ обозначим количество разрядов в складываемых числах. Результатом будет $(n+1)$-битное число из-за возможности переполнения последнего разряда. Складываемые числа будем обозначать как $x$ и $y$, а их разряды как $x_i$ и $y_i$. Результат сложения и его разряды будем обозначать $z$ и $z_i$ соответственно. Введем также переменные $c_i$, которые будут равны 1, если в разряде $i$ произошло переполнение. Для того, чтобы выразить значения $z_i$ и $c_i$, нам доступны лишь логические (двоичные) операции и только они. На деле нам обычно доступно лишь какое-то подмножество логических операций, но во многих случаях мы можем из них выразить все остальные операции, как это описано в~\S~1.2.

Очевидно, что $z_0 = x_0 \oplus y_0$ и $c_1 = x_0\land y_0$. В общем же случае нам требуется, чтобы $z_i$ равнялось 1 когда либо одно из чисел $x_i, y_i, c_{i-1}$ равно 1, либо все они одновременно, а $c_i$ равно 1, когда по крайней мере два из них равно 1. Используя таблицу истинности, легко увидеть, что этим критериям соответствуют логические формулы
$$z_i = x_i\oplus y_i \oplus c_{i-1}$$
$$c_i = (\neg x_i\land y_i \land c_{i-1}) \lor (x_i \land (y_i \lor c_{i-1}))$$

Диаграмма для этих формул показана на рисунке~2.

\begin{figure}[h]
\centering
\begin{tikzpicture}
	\def\lblock{node [minimum height=1cm,minimum width=1.5cm,draw] }
	\def\spoint{node [circle, draw, fill, inner sep = 0, minimum size = 0.05cm] }
	\draw (-2cm, 1cm) \spoint (x) {};
	\draw (-2cm, 0) \spoint (y) {};
	\draw (-2cm, -1cm) \spoint (c) {};
	\draw (-2cm, -2.95) \spoint (c1) {};
	\node [left] at (x) {$x_i$};
	\node [left] at (y) {$y_i$};
	\node [left] at (c) {$c_{i-1}$};
	\draw (-.5cm, -1.7cm) \lblock (p1) {$\oplus$};
	\draw (2.2cm, -2.7cm) \lblock (p2) {$\oplus$};
	\draw (-.5cm, 2cm) \lblock (n) {$\neg$};
	\draw (1.5cm, 1.8cm) \lblock (and1) {$\land$};
	\draw (3.5cm, 1.6cm) \lblock (and2) {$\land$};
	\draw (3.5cm, 0) \lblock (and3) {$\land$};
	\draw (1.5cm, -.8cm) \lblock (or1) {$\lor$};
	\draw (5.5cm, .8cm) \lblock (or2) {$\lor$};
	\draw (7cm, -1cm) \spoint (z) {};
	\draw (7cm, 1cm) \spoint (cn) {};
	\node [right] at (z) {$z_i$};
	\node [right] at (cn) {$c_i$};
	\draw [->] (x.east) -- ($(p1.south west)!.75!(p1.north west)$);
	\draw [->] (y.east) -- ($(p1.south west)!.25!(p1.north west)$);
	\draw [->] (p1.east) -- ($(p2.south west)!.75!(p2.north west)$);
	\draw [->] (c.east) -- (c1) -- ($(p2.south west)!.25!(p2.north west)$);
	\draw [->] (p2.east) -- (z.west);
	\draw [->] (x.east) -- (n.west);
	\draw [->] (n.east) -- ($(and1.south west)!.75!(and1.north west)$);
	\draw [->] (y.east) -- ($(and1.south west)!.25!(and1.north west)$);
	\draw [->] (and1.east) -- ($(and2.south west)!.75!(and2.north west)$);
	\draw [->] (c.east) -- ($(and2.south west)!.25!(and2.north west)$);
	\draw [->] (y.east) --  ($(or1.south west)!.75!(or1.north west)$);
	\draw [->] (c.east) --  ($(or1.south west)!.25!(or1.north west)$);
	\draw [->] (x.east) --  ($(and3.south west)!.75!(and3.north west)$);
	\draw [->] (or1.east) --  ($(and3.south west)!.25!(and3.north west)$);
	\draw [->] (and2.east) --  ($(or2.south west)!.75!(or2.north west)$);
	\draw [->] (and3.east) --  ($(or2.south west)!.25!(or2.north west)$);
	\draw [->] (or2.east) -- (cn.west);
\end{tikzpicture}
\caption{Схема сложения одного разряда}
\end{figure}

Подобная схема должна быть реализована на каждый бит данных для сложения чисел.

\begin{exercise}
Сколько всего логических элементов и соединений потребуется для реализации операции сложения для двубайтовых чисел? Можете ли вы предложить способ, которым можно сократить это число?
\end{exercise}

Приведенная диаграмма является очень сильным упрощением того, что в действительности происходит, и отражает лишь общую идею, на которой всё базируется. В физическом устройстве было бы важно реальное геометрическое расположение элементов и связей между ними, их размеры, материалы, напряжение, стоимость, общее количество элементов и много прочих сложных инженерных деталей, которые математикам уже мало интересны.