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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Применение[править | править вики-текст]

Длинная арифметика применяется в следующих областях:

Необходимые аппаратные средства для работы с длинной арифметикой[править | править вики-текст]

Строго говоря, для реализации арифметики произвольной точности от процессора требуется лишь косвенная адресация; в арифметике фиксированной точности можно обойтись даже без неё. Тем не менее, определённые функции процессора ускоряют длинную арифметику, одновременно упрощая её программирование.

Реализация в языках программирования[править | править вики-текст]

Языки программирования имеют встроенные типы данных, размер которых, в основном, не превышает 64 бита (около 1019). Десятичная длинная арифметика была реализована в советских языках программирования АЛМИР-65 на ЭВМ МИР-1 и АНАЛИТИК на ЭВМ МИР-2.
Для работы с большими числами, в современных языках программирования существует довольно много готовых оптимизированных библиотек для длинной арифметики.

Большинство функциональных языков позволяют переключаться с обычной арифметики на длинную без необходимости изменения кода арифметических расчётов. Например, Erlang и Scheme всегда представляют точные числа длинными. В Standard ML реализации всех разновидностей целых чисел определяются на основании сигнатуры INTEGER, позволяя выбирать необходимую размерность,— в том числе присутствует модуль IntInf, реализующий целые числа произвольной точности; в реализации PolyML этот модуль используется по умолчанию.

Встроенные библиотеки работы с большими числами есть в Ruby, Python и Java.

Алгоритмы[править | править вики-текст]

Алгоритмы умножения[править | править вики-текст]

Для описания алгоритмов обычно используется следующее представление целых чисел. Выбирается основание ~~\beta > 1 . Тогда целое число длины n можно представить в виде:
~~A=a_{n-1} \cdot \beta^{n-1} + ... + a_1 \cdot \beta + a_0,
где  0 \le a_i \le \beta - 1 [1]

Базовый[править | править вики-текст]

Представляет собой алгоритм по школьному методу «в столбик». Занимает время O(n \cdot m), где n, m — размеры перемножаемых чисел.
Алгоритм может быть представлен в виде: [1] [2]

Algorithm 1 BasecaseMultiply
Input: A=\sum\nolimits_{i=0}^{m-1} a_i \beta^i, B=\sum\nolimits_{j=0}^{n-1} b_j \beta^j
Output: C=AB:=\sum\nolimits_{k=0}^{m+n-1} c_k \beta^k
1: C \gets A\cdot b_0
2: for j from 1 to n-1 do
3: ~~~~C \gets C + \beta^j(A \cdot b_j)
4: return~~C.

Умножение Карацубы[править | править вики-текст]

Метод умножения Карацубы относится к парадигме «разделяй и властвуй». Сложность вычисления алгоритма:

M(n)=O(n^{\log_23}),\quad\log_23=1{,}5849\ldots.

Данный алгоритм представляет собой простую реализацию[3] идеи разделения входных данных, которая стала базисной для нижеперечисленных алгоритмов. Идея заключается в разделении одной операции умножения над n-значными числами на три операции умножения над числами длины n/2 плюс O(n)[1].
Для перемножения двух чисел, превышающих длину машинного слова, алгоритм Карацубы вызывается рекурсивно до тех пор, пока эти числа не станут достаточно маленькими, чтобы их можно было перемножить непосредственно. Пример такого алгоритма:

Algorithm 2 KaratsubaMultiply
Input: A=\sum\nolimits_{i=0}^{n-1} a_i \beta^i, B=\sum\nolimits_{j=0}^{n-1} b_j \beta^j
Output: C=AB:=\sum\nolimits_{k=0}^{2n-1} c_k \beta^k
k \gets [n/2]
(A_0, B_0):=(A, B)mod \beta^k, (A_1, B_1):=(A, B)div \beta^k
s_A \gets sign(A_0-A_1), s_B \gets sign(B_0-B_1)
C_0 \gets KaratsubaMultiply(A_0,B_0)
C_1 \gets KaratsubaMultiply(A_1,B_1)
C_2 \gets KaratsubaMultiply(|A_0-A_1|,|B_0-B_1|)
return~C:=C_0+(C_0+C_1-s_As_BC_2) \beta^k + C_1 \beta^{2k}

Посчитаем ~x = 12345 \cdot 6789~:
12345 = 12 \cdot 1000 + 345
6789 = 6 \cdot 1000 + 789
Нужно вычислить три промежуточных коэффициента:
C_0 = 345 \cdot 789 = 272205
C_1 = 12 \cdot 6 = 72
C_2 = C_1 + C_0 - (345 - 12) \cdot (789 - 6) = 72 + 272205 -333 \cdot 783 = 11538
Результат:
x = C_1 \cdot 1000^2 + C_2 \cdot 1000 + C_0
x = 72 \cdot 1000^2 + 11538 \cdot 1000 + 272205 = 83810205

Алгоритм Тоом-а[править | править вики-текст]

Этот алгоритм является обобщением алгоритма Карацубы и работает быстрее. Для двух данных целых чисел A и B алгоритм Toom-a делит их на k меньших частей, длина каждой из которых равна длине машинного слова, и производит операции над этими частями. Сложность вычисления алгоритма: O(n^{ln(2k-1)/ln(k)}).

Toom 3-Way[править | править вики-текст]

Идея впервые была предложена А. Л. Тоомом в 1963 году[4], и заключается в разделении входных данных (множителей) на 3 равные части(для простоты все части считаем равными). Toom-3 сокращает число элементарных операций умножения с 9 до 5. Сложность алгоритма O(n^{1.465}).
Рассмотрим данный алгоритм на следующем примере. Пусть дано два числа Y и X. Пусть определены операции над числами, размер которых равен 1/3 от размеров исходных чисел (см. рисунок). Предположим также, что числа занимают равную память и делятся ровно на 3 части, в противном случае дополним оба числа нулями до необходимых размеров.

Разбиение входных чисел.jpg


Затем происходит отображение (параметризация) этих частей на полиномы 2 степени.
X(t) = x_2 \cdot t^2 + x_1 \cdot t + x_0,
Y(t) = y_2 \cdot t^2 + y_1 \cdot t + y_0,
Введем b, по определению такую, что значение многочленов X(b),~Y(b) соответственно равно входным числам x и y. Для битового представления чисел это число равно возведению 2 в степень, равную длине каждой из частей в битах. Также введем полином:
W(t)=X(t) \cdot Y(t), (1)
W(t) = w_4 \cdot t^4 + w_3 \cdot t^3 + w_2 \cdot t^2 + w_1 \cdot t + w_0,
После того как будут определены элементы w_i — коэффициенты многочлена~W(t)~, они будут использованы в целях получения w=W(b), так как ~x \cdot y=X(b) \cdot Y(b)=W(b)~. Размер коэффициентов ~w_i~ в 2 раза больше (по памяти), чем разбиение ~x_i~ или ~y_i~. Конечное число, равное произведению ~x \cdot y~ можно найти, складывая ~w_i~ со сдвигом, как показано на рисунке ниже.

Разбиение выходных чисел.jpg

Коэффициенты ~w_i~ могут быть вычислены следующим образом: w_4=x_2 \cdot y_2, w_3=x_2 \cdot y_1+x_1 \cdot y_2,~~ w_2=x_2 \cdot y_0+x_1 \cdot y_1+x_0 \cdot y_2 и так далее, но это потребует все 9 перемножений: x_i \cdot y_j для i, j=0,1,2, и будет эквивалентно простому перемножению.
Вместо этого был использован иной подход. ~X(t),Y(t)~ вычисляются в (1) в 5 точках при разных t.
В таблице, представленной ниже, приведены значения полиномов в равенстве (1)

t=0 x_0 \cdot y_0 W(0)~~~=~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~w_0
t=1 (x_2+x_1+x_0) \cdot (y_2+y_1+y_0) W(1)~~~=~~~~w_4 + ~w_3 +  ~~w_2 +  ~w_1 + w_0
t=-1 (x_2-x_1+x_0) \cdot (y_2-y_1+y_0) W(-1)~=~~~~w_4 - ~w_3 + ~~w_2 - ~w_1 + w_0
t=2 (4x_2+2x_1+x_0) \cdot (4y_2+2y_1+y_0) W(2)~~~=~16w_4 + 8w_3 + 4w_2 + 2w_1 + w_0
t= \infty x_2 \cdot y_2 W(\infty)~~=~~~~w_4

Параметр t=\infty условный. Он означает банальное равенство коэффициентов при t^4, тем самым мы получим значение w_4 сразу. Данная система линейна относительно 5 неизвестных. При её разрешении мы получаем неизвестные w_i. Далее получаем значение многочлена, как было описано выше.

Toom 4-Way[править | править вики-текст]

Сложность алгоритма O(n^{1.404}). Представляет собой 7 элементарных операций умножения. Toom-4 разделяет входные данные на 4 части.
По такому же принципу как и в Toom-3 строим два полинома:


X(t) = x3 \cdot t^3 + x2 \cdot t^2 + x1 \cdot t + x0,
Y(t) = y3 \cdot t^3 + y2 \cdot t^2 + y1 \cdot t + y0,

X(t) и Y(t) вычисляются в 7 разных точках, также вычисляется значение W(t) в этих точках.

t=0 x_0 \cdot y_0, откуда сразу получаем w_0
t=1/2 (x_3+2x_2+4x_1+8x_0) \cdot (y_3+2y_2+4y_1+8y_0)
t=-1/2 (-x_3+2x_2-4x_1+8x_0) \cdot (-y_3+2y_2-4y_1+8y_0)
t=1 (x_3+x_2+x_1+x_0) \cdot (y_3+y_2+y_1+y_0)
t=-1 (-x_3+x_2-x_1+x_0) \cdot (-y_3+y_2-y_1+y_0)
t=2 (8x_3+4x_2+2x_1+x_0) \cdot (8y_3+4y_2+2y_1+y_0)
t=\infty x_3 \cdot y_3, откуда сразу получаем w_6

Количество операций сложения и умножения для Toom-4 намного больше, чем для Toom-3. Но некоторые выражения встречаются по нескольку раз. Например, x_2+x_0 вычисляется для t=1 и для t=-1 [5].

Алгоритм Тоом-а для произвольного разбиения[править | править вики-текст]

Алгоритм Тоома для разделения входных чисел на n операндов эквивалентен описанному выше. В общем случае разделение двух одинаково длинных операндов на r частей приводит к вычислению значений в 2r-1 точках. В качестве точек для решения системы, обычно берут 0, \infty, +1, -1 , \pm 2^i, \pm 2^{-i}.

Перемножение методом Фурье[править | править вики-текст]

Данный алгоритм перемножения используется для больших и очень больших чисел.[6]
Этот алгоритм перемножает два числа за время  O(n \cdot \log n) , где  n  — количество значащих цифр в перемножаемых числах (предполагая их равными). Создание приписывается Кули (Coolet) и Таки (Tukey) — 1965 г. Также есть предположения, что данный алгоритм был известен и раньше, но не имел большой важности до того как изобрели первые компьютеры. Вероятными кандидатами изобретения данного алгоритма также называют Рунг (Runge) и Кёниг (Konig) — 1924 г., а также Гаусса — 1805 г.
Пусть имеется число, представим его в виде многочлена, как мы делали ранее. Назовем этот многочлен A(x). Также введем дискретное Фурье преобразование многочлена как вектор, с координатами   	\left (b_1, b_2, b_3, b_4, \dots b_{n-1}\right ). Где b[i] определены как w^n[i] — комплексный корень n-ой степени из 1, не равный 1. Дело в том, что комплексный корень из 1 определен с точностью до фазового множителя, количество этих корней — n. Фурье преобразование применено для того, чтобы свертку коэффициентов многочленов A и B: (A(x) \cdot B(x)) — заменить на произведение их Фурье образов.
F(A(x)  \cdot  B(x)) = F (A)  \cdot  F (B)
 A(x)  \cdot  B(x) = F^{-1} (F (A)  \cdot  F (B)),
где под умножением F (A)  \cdot  F (B) подразумевается скалярное произведение векторов.
Предположим, что n есть степень двойки.
Нахождение F(A) производится рекурсивным методом (разделяй и властвуй). Идея заключается в разбиении исходного многочлена A (x) = a_0x_0 + a_1x_1 + ... + a_{n-1}x_{n-1} на два многочлена,
A0 (x) = a_0x_0 + a_2x_1 + a_4x_2 + \dots + a_{n-2}x_{\frac{n-2}{2}}
A1 (x) = a_1x_0 + a_3x_1 + a_5x_2 + \dots + a_{n-1}x_{\frac{n-2}{2}}
Тогда A(x) = A0 (x^2) + x  \cdot  A1 (x^2).
Заметим, что среди всех чисел \left (w^n_i\right )^2 (0 \leq i < n), только \frac{n}{2} различных. Поэтому, ДПФ A0 и A1 будут \frac{n}{2}-элементными. А так как ДПФ A0 и A1 состоит из \frac{n}{2} элементов, то комплексным корнем из 1 там будет корень степени \frac{n}{2}.
Значит, A(w^n_k) = A0(w^n_{2k}) + w^n_k  \cdot  A1(w^n_{2k}) = A0(w^\frac{n}{2}_k) + w^n_k  \cdot  A1(w^\frac{n}{2}_k), где 0 \leq k < n / 2 и
A(w^n_{k+\frac{n}{2}}) = A0(w^n_{2 \cdot {k+\frac{n}{2}}}) + w^n_{k+\frac{n}{2}}  \cdot  A1(w^n_{2 \cdot {k+\frac{n}{2}}}) = A0(w^{n/2}_{k+\frac{n}{2}}) + w^n_{k+\frac{n}{2}}  \cdot  A1(w^\frac{n}{2}_{k+\frac{n}{2}}) = A0(w^\frac{n}{2}_k) - w^n_k  \cdot  A1(w^\frac{n}{2}_k).
Мы использовали свойства комплексных чисел: различных корней степени n всего  n. w^n_{k+\frac{n}{2}}  = w^n_k  \cdot  e^{i \cdot \frac{2\pi}{n}  \cdot  \frac{n}{2}} = w^n_k  \cdot  e^{i \cdot \pi} = - w^n_k.

Получаем рекурсивный алгоритм:
ДПФ одного элемента равно этому элементу
для нахождения ДПФ A разбиваем коэффициенты A на чётные и нечётные, получаем два многочлена A0 и A1, находим ДПФ для них, находим ДПФ A:
b_k = b^0_k + w^n_k  \cdot  b^1_k
b_{k + \frac{n}{2}} = b^0_k - w^n_k  \cdot  b^1_k
для 0 \leq k < n / 2.
Существует доказательство следующего утверждения: Обратное ДПФ находится аналогично прямому ДПФ, за исключением того, что в качестве точек берутся точки, симметричные относительно вещественной оси, вместо тех, что использовались в прямом ДПФ преобразовании. Также необходимо все коэффициенты многочлена поделить на n

Алгоритмы извлечения корня[править | править вики-текст]

Квадратный корень[править | править вики-текст]

Одним из алгоритмов вычисления квадратного корня является «Karatsuba Square Root»[7]

Алгоритмы преобразования системы счисления[править | править вики-текст]

Алгоритмы деления[править | править вики-текст]

Целочисленное деление[править | править вики-текст]

Деление чисел с плавающей точкой[править | править вики-текст]

Другие алгоритмы[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 Richard P. Brent and Paul Zimmermann, Modern Computer Arithmetic
  2. Donald E. Knuth «The Art of Computer Programming», Секция 4.3.1
  3. Donald E. Knuth «The Art of Computer Programming», Секция 4.3.3, часть А
  4. Доклады академии наук СССР 150 (1963), 496—498
  5. Toom 4-Way Multiplication — GNU MP 5.1.3
  6. Donald E. Knuth «The Art of Computer Programming», Секция 4.3.3, часть С
  7. Paul Zimmermann, «Karatsuba Square Root», INRIA Research Report 3805, November 1999, http://hal.inria.fr/inria-00072854/PDF/RR-3805.pdf

Литература[править | править вики-текст]

  • Donald E. Knuth, «The Art of Computer Programming», volume 2, «Seminumerical Algorithms», 3rd edition, Addison-Wesley, 1998
  • Dan Zuras, «On Squaring and Multiplying Large Integers», ARITH-11: IEEE Symposium on Computer Arithmetic, 1993, pp. 260 to 271.
  • ДАН СССР 150 (1963), 496—498
  • Richard P. Brent and Paul Zimmermann, Modern Computer Arithmetic