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

Для термина «большие числа» см. также другие значения.

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

Применение

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

• составление кода для процессоров (микроконтроллеров) низкой разрядности. Например, микроконтроллеры серии AVR имеют АЦП с разрядностью 10 бит и регистры с разрядностью 8 бит. Этого недостаточно для обработки информации с АЦП; без длинной арифметики не обойтись;
• криптография. Большинство систем подписывания и шифрования данных используют целочисленную арифметику по модулю m, где m — очень большое натуральное число, не обязательно простое. Например, при реализации метода шифрования RSA, криптосистемы Рабина или схемы Эль-Гамаля требуется обеспечить точность результатов умножения и возведения в степень порядка 10^309;
• математическое (см. список ПО) и финансовое ПО. Результат вычисления на бумаге должен совпадать с результатом работы компьютера с точностью до последнего разряда. В частности, калькулятор Windows (начиная с Windows 95) проводит четыре арифметических действия с намного большей точностью, чем позволяет процессор x86. Для научных и инженерных расчётов длинная арифметика применяется редко, так как ошибки во входных данных обычно намного больше, чем ошибки округления;
• стандартная тема в спортивном программировании.

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

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

• Флаг переноса. Операции «сложить/вычесть с переносом», «циклический сдвиг через бит переноса».
• Косвенная адресация с автоинкрементом и автодекрементом (индексный регистр после операции увеличивается или уменьшается).
• Умножение w · w = 2w (умножение слова на слово, результат — двойное слово), деление 2w / w = w (с возможным переполнением).

Реализация в языках программирования

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

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

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

Алгоритмы

Алгоритмы умножения

Для описания алгоритмов обычно используется следующее представление целых чисел. Выбирается основание ${\displaystyle \beta >1}$. Тогда целое число длины ${\displaystyle n}$ можно представить в виде[1]:

${\displaystyle A=a_{n-1}\cdot \beta ^{n-1}+...+a_{1}\cdot \beta +a_{0},}$

где ${\displaystyle 0\leq a_{i}\leq \beta -1.}$

Базовый

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

Алгоритм может быть представлен в виде[1][2]:

Algorithm 1 BasecaseMultiply
Input: ${\displaystyle A=\sum \nolimits _{i=0}^{m-1}a_{i}\beta ^{i},B=\sum \nolimits _{j=0}^{n-1}b_{j}\beta ^{j}}$
Output: ${\displaystyle C=AB:=\sum \nolimits _{k=0}^{m+n-1}c_{k}\beta ^{k}}$
${\displaystyle 1:C\gets A\cdot b_{0}}$
${\displaystyle 2:}$ for ${\displaystyle j}$ from ${\displaystyle 1}$ to ${\displaystyle n-1}$ do
${\displaystyle 3:~~~~C\gets C+\beta ^{j}(A\cdot b_{j})}$
${\displaystyle 4:return~~C.}$

Умножение Карацубы

Основная статья: Умножение Карацубы

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

${\displaystyle M(n)=O(n^{\log _{2}3}),\quad \log _{2}3=1{,}5849\ldots }$.

Данный алгоритм представляет собой простую реализацию[3] идеи разделения входных данных, которая стала базисной для нижеперечисленных алгоритмов. Идея заключается в разделении одной операции умножения над ${\displaystyle n}$-значными числами на три операции умножения над числами длины ${\displaystyle n/2}$ плюс ${\displaystyle O(n)}$[1].

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

Algorithm 2 KaratsubaMultiply
Input: ${\displaystyle A=\sum \nolimits _{i=0}^{n-1}a_{i}\beta ^{i},B=\sum \nolimits _{j=0}^{n-1}b_{j}\beta ^{j}}$
Output: ${\displaystyle C=AB:=\sum \nolimits _{k=0}^{2n-1}c_{k}\beta ^{k}}$
${\displaystyle k\gets [n/2]}$
${\displaystyle (A_{0},B_{0}):=(A,B)mod\beta ^{k},(A_{1},B_{1}):=(A,B)div\beta ^{k}}$
${\displaystyle s_{A}\gets sign(A_{0}-A_{1}),s_{B}\gets sign(B_{0}-B_{1})}$
${\displaystyle C_{0}\gets }$ KaratsubaMultiply${\displaystyle (A_{0},B_{0})}$
${\displaystyle C_{1}\gets }$ KaratsubaMultiply${\displaystyle (A_{1},B_{1})}$
${\displaystyle C_{2}\gets }$ KaratsubaMultiply${\displaystyle (|A_{0}-A_{1}|,|B_{0}-B_{1}|)}$
${\displaystyle return~C:=C_{0}+(C_{0}+C_{1}-s_{A}s_{B}C_{2})\beta ^{k}+C_{1}\beta ^{2k}}$

Посчитаем ${\displaystyle x=12345\cdot 6789}$:

${\displaystyle 12345=12\cdot 1000+345}$

${\displaystyle 6789=6\cdot 1000+789}$

Нужно вычислить три промежуточных коэффициента:

${\displaystyle C_{0}=345\cdot 789=272205}$

${\displaystyle C_{1}=12\cdot 6=72}$

${\displaystyle C_{2}=C_{1}+C_{0}-(345-12)\cdot (789-6)=72+272205-333\cdot 783=11538}$

Результат:

${\displaystyle x=C_{1}\cdot 1000^{2}+C_{2}\cdot 1000+C_{0}}$

${\displaystyle x=72\cdot 1000^{2}+11538\cdot 1000+272205=83810205}$

Алгоритм Тоома

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

Алгоритм Тоома-3

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

Рассмотрим данный алгоритм на следующем примере. Пусть дано два числа ${\displaystyle Y}$ и ${\displaystyle X}$. Пусть определены операции над числами, размер которых равен 1/3 от размеров исходных чисел (см. рисунок). Предположим также, что числа занимают равную память и делятся ровно на 3 части, в противном случае дополним оба числа нулями до необходимых размеров.

Затем происходит отображение (параметризация) этих частей на полиномы 2 степени.

${\displaystyle X(t)=x_{2}\cdot t^{2}+x_{1}\cdot t+x_{0},}$

${\displaystyle Y(t)=y_{2}\cdot t^{2}+y_{1}\cdot t+y_{0},}$

Введем ${\displaystyle b}$, по определению такую, что значения многочленов ${\displaystyle X(b),~Y(b)}$ соответственно равны входным числам ${\displaystyle x}$ и ${\displaystyle y}$. Для битового представления чисел это число равно двойке в степени, равной длине каждой из частей в битах.

Также введем полином:

${\displaystyle W(t)=X(t)\cdot Y(t),}$ (1)

${\displaystyle W(t)=w_{4}\cdot t^{4}+w_{3}\cdot t^{3}+w_{2}\cdot t^{2}+w_{1}\cdot t+w_{0},}$

После того как будут определены элементы ${\displaystyle w_{i}}$ — коэффициенты многочлена${\displaystyle W(t)}$, они будут использованы в целях получения ${\displaystyle w=W(b)}$, так как ${\displaystyle x\cdot y=X(b)\cdot Y(b)=W(b)}$. Размер коэффициентов ${\displaystyle w_{i}}$ в 2 раза больше (по памяти), чем разбиение ${\displaystyle x_{i}}$ или ${\displaystyle y_{i}}$. Конечное число, равное произведению ${\displaystyle x\cdot y}$ можно найти, складывая ${\displaystyle w_{i}}$ со сдвигом, как показано на рисунке ниже.

Коэффициенты ${\displaystyle w_{i}}$ могут быть вычислены следующим образом: ${\displaystyle 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 перемножений: ${\displaystyle x_{i}\cdot y_{j}}$ для i, j=0,1,2, и будет эквивалентно простому перемножению.

Вместо этого был использован иной подход. ${\displaystyle X(t),Y(t)}$ вычисляются в (1) в 5 точках при разных ${\displaystyle t}$.

В таблице, представленной ниже, приведены значения полиномов в равенстве (1)

${\displaystyle t=0}$	${\displaystyle x_{0}\cdot y_{0}}$	${\displaystyle W(0)~~~=~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~w_{0}}$
${\displaystyle t=1}$	${\displaystyle (x_{2}+x_{1}+x_{0})\cdot (y_{2}+y_{1}+y_{0})}$	${\displaystyle W(1)~~~=~~~~w_{4}+~w_{3}+~~w_{2}+~w_{1}+w_{0}}$
${\displaystyle t=-1}$	${\displaystyle (x_{2}-x_{1}+x_{0})\cdot (y_{2}-y_{1}+y_{0})}$	${\displaystyle W(-1)~=~~~~w_{4}-~w_{3}+~~w_{2}-~w_{1}+w_{0}}$
${\displaystyle t=2}$	${\displaystyle (4x_{2}+2x_{1}+x_{0})\cdot (4y_{2}+2y_{1}+y_{0})}$	${\displaystyle W(2)~~~=~16w_{4}+8w_{3}+4w_{2}+2w_{1}+w_{0}}$
${\displaystyle t=\infty }$	${\displaystyle x_{2}\cdot y_{2}}$	${\displaystyle W(\infty )~~=~~~~w_{4}}$

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

Алгоритм Тоома-4

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

По такому же принципу как и в Toom-3 строим два полинома:

${\displaystyle X(t)=x3\cdot t^{3}+x2\cdot t^{2}+x1\cdot t+x0,}$

${\displaystyle Y(t)=y3\cdot t^{3}+y2\cdot t^{2}+y1\cdot t+y0.}$

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

${\displaystyle t=0}$	${\displaystyle x_{0}\cdot y_{0},}$ откуда сразу получаем ${\displaystyle w_{0}}$
${\displaystyle t=1/2}$	${\displaystyle (x_{3}+2x_{2}+4x_{1}+8x_{0})\cdot (y_{3}+2y_{2}+4y_{1}+8y_{0})}$
${\displaystyle t=-1/2}$	${\displaystyle (-x_{3}+2x_{2}-4x_{1}+8x_{0})\cdot (-y_{3}+2y_{2}-4y_{1}+8y_{0})}$
${\displaystyle t=1}$	${\displaystyle (x_{3}+x_{2}+x_{1}+x_{0})\cdot (y_{3}+y_{2}+y_{1}+y_{0})}$
${\displaystyle t=-1}$	${\displaystyle (-x_{3}+x_{2}-x_{1}+x_{0})\cdot (-y_{3}+y_{2}-y_{1}+y_{0})}$
${\displaystyle t=2}$	${\displaystyle (8x_{3}+4x_{2}+2x_{1}+x_{0})\cdot (8y_{3}+4y_{2}+2y_{1}+y_{0})}$
${\displaystyle t=\infty }$	${\displaystyle x_{3}\cdot y_{3},}$ откуда сразу получаем ${\displaystyle w_{6}}$

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

Алгоритм Тоома для произвольного разбиения

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

Перемножение методом Фурье

Данный алгоритм перемножения используется для больших и очень больших чисел[6].

Этот алгоритм перемножает два числа за время ${\displaystyle O(n\cdot \log n),}$ где ${\displaystyle n}$ — количество значащих цифр в перемножаемых числах (предполагая их равными). Создание приписывается Кули (Coolet) и Тюки (Tukey) — 1965 г. Также есть предположения, что данный алгоритм был известен и раньше, но не имел большой важности до того как изобрели первые компьютеры. Вероятными кандидатами на авторство изобретения данного алгоритма также называют Рунг (Runge) и Кёниг (Konig) — 1924 г., а также Гаусса — 1805 г.

Пусть имеется число, представим его в виде многочлена, как мы делали ранее. Назовем этот многочлен ${\displaystyle A(x).}$ Также введем дискретное преобразование Фурье многочлена как вектор, с координатами ${\displaystyle \left(b_{1},b_{2},b_{3},b_{4},\dots b_{n-1}\right)}$. Где ${\displaystyle b[i]}$ определены как ${\displaystyle w^{n}[i]}$ — комплексный корень ${\displaystyle n}$-ой степени из 1, не равный 1. Дело в том, что комплексный корень из 1 определен с точностью до фазового множителя, количество этих корней — ${\displaystyle n}$. Преобразование Фурье применено для того, чтобы свертку коэффициентов многочленов ${\displaystyle A}$ и ${\displaystyle B}$: ${\displaystyle (A(x)\cdot B(x))}$ — заменить на произведение их Фурье образов.

${\displaystyle F(A(x)\cdot B(x))=F(A)\cdot F(B)}$

${\displaystyle A(x)\cdot B(x)=F^{-1}(F(A)\cdot F(B)),}$

где под умножением ${\displaystyle F(A)\cdot F(B)}$ подразумевается скалярное произведение векторов.

Предположим, что ${\displaystyle n}$ есть степень двойки.

Нахождение ${\displaystyle F(A)}$ производится рекурсивным методом (разделяй и властвуй). Идея заключается в разбиении исходного многочлена ${\displaystyle A(x)=a_{0}x_{0}+a_{1}x_{1}+...+a_{n-1}x_{n-1}}$ на два многочлена,

${\displaystyle A0(x)=a_{0}x_{0}+a_{2}x_{1}+a_{4}x_{2}+\dots +a_{n-2}x_{\frac {n-2}{2}}}$

${\displaystyle A1(x)=a_{1}x_{0}+a_{3}x_{1}+a_{5}x_{2}+\dots +a_{n-1}x_{\frac {n-2}{2}}}$

Тогда ${\displaystyle A(x)=A0(x^{2})+x\cdot A1(x^{2})}$.

Заметим, что среди всех чисел ${\displaystyle \left(w_{i}^{n}\right)^{2}(0\leq i<n)}$, только ${\displaystyle {\frac {n}{2}}}$ различных. Поэтому, ДПФ ${\displaystyle A0}$ и ${\displaystyle A1}$ будут ${\displaystyle {\frac {n}{2}}}$-элементными. А так как ДПФ ${\displaystyle A0}$ и ${\displaystyle A1}$ состоит из ${\displaystyle {\frac {n}{2}}}$ элементов, то комплексным корнем из 1 там будет корень степени ${\displaystyle {\frac {n}{2}}}$.

Значит,

${\displaystyle A(w_{k}^{n})=A0(w_{2k}^{n})+w_{k}^{n}\cdot A1(w_{2k}^{n})=A0(w_{k}^{\frac {n}{2}})+w_{k}^{n}\cdot A1(w_{k}^{\frac {n}{2}}),}$

где ${\displaystyle 0\leq k<n/2}$ и

${\displaystyle A(w_{k+{\frac {n}{2}}}^{n})=A0(w_{2\cdot {k+{\frac {n}{2}}}}^{n})+w_{k+{\frac {n}{2}}}^{n}\cdot A1(w_{2\cdot {k+{\frac {n}{2}}}}^{n})=A0(w_{k+{\frac {n}{2}}}^{n/2})+w_{k+{\frac {n}{2}}}^{n}\cdot A1(w_{k+{\frac {n}{2}}}^{\frac {n}{2}})=A0(w_{k}^{\frac {n}{2}})-w_{k}^{n}\cdot A1(w_{k}^{\frac {n}{2}}).}$

Мы использовали свойства комплексных чисел: различных корней степени ${\displaystyle n}$ всего ${\displaystyle n}$. ${\displaystyle w_{k+{\frac {n}{2}}}^{n}=w_{k}^{n}\cdot e^{i\cdot {\frac {2\pi }{n}}\cdot {\frac {n}{2}}}=w_{k}^{n}\cdot e^{i\cdot \pi }=-w_{k}^{n}}$.

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

Алгоритмы извлечения корня

Квадратный корень

Одним из алгоритмов вычисления квадратного корня является алгоритм «Karatsuba Square Root». На данный момент это самый известный метод вычисления квадратного корня n-значного числа. Этот алгоритм использует быстрое преобразование Фурье и метод Ньютона со сложностью 5M(n)[7].

Представленный алгоритм основан на делении Бурникеля — Циглера (Burnikel-Ziegler) Карацубы. Имея целое число n, алгоритм подсчитывает одновременно его целый квадратный корень ${\displaystyle s=\lfloor {\sqrt {n}}\rfloor }$ и соответствующий остаток, который равен ${\displaystyle r=n-s^{2}.}$ Это не является асимптотически оптимальным, но очень эффективно на практике со сложностью порядка ${\displaystyle {\frac {3}{2}}K(n)}$ операций, где K(n) — это количество операций, необходимых чтобы умножить два n-разрядных числа, используя алгоритм Карацубы (Karatsuba). Причина этой низкой сложности в красивом делении Карацубы (Karatsuba), недавно открытом Бурникелем и Циглером (Burnikel and Ziegler), а также в осторожном обращении с остатками, которое избегает ненужных вычислений.

Теорема. Число операций, которые алгоритм SqrtRem использует со 2n-разрядным входом, ограничено

${\displaystyle {\frac {3}{2}}K(n)+O(n\log n),}$

где K(n) — число операций, необходимых для умножения 2n-разрядных чисел, используя алгоритм Карацубы.

Алгоритм SqrtRem ${\displaystyle (n=a_{3}b^{3}+a_{2}b^{2}+a_{1}b+a_{0})}$
    Вход: ${\displaystyle 0\leq a_{i}<b}$  with ${\displaystyle a_{3}\geq b/4}$
    Выход: ${\displaystyle (s,r)}$ такие, что ${\displaystyle s^{2}\leq n=s^{2}+r<(s+1)^{2}}$
    ${\displaystyle (s',r')\leftarrow SqrtRem(a_{3}b+a_{2})}$
    ${\displaystyle (q,u)\leftarrow DivRem(r'b+a_{1},2s')}$
    ${\displaystyle s\leftarrow ub+a_{0}-q^{2}}$
    if ${\displaystyle r<0}$ then
         ${\displaystyle r\leftarrow r+2s-1}$
         ${\displaystyle s\leftarrow s-1}$
    return ${\displaystyle (s,r)}$

Алгоритмы преобразования системы счисления

Предположим, что выполняется преобразование из системы счисления по основанию b в систему счисления по основанию В[8].

Способы преобразования целых чисел

Метод 1 (Деление на В с использованием представления чисел в формате по основанию b). Для заданного целого числа u можно
получить представление в формате по основанию В вида ${\displaystyle (\dots U_{2}U_{1}U_{0})_{B}}$, выполняя

${\displaystyle U_{0}=u\!\!\!\!\mod B}$, ${\displaystyle U_{1}=\left\lfloor {\frac {u}{B}}\right\rfloor \!\!\!\!\mod B}$, ${\displaystyle U_{2}=\left\lfloor \left\lfloor {\frac {u}{B}}\right\rfloor \right\rfloor \!\!\!\!\mod B}$, до тех пор, пока не окажется ${\displaystyle \left\lfloor \dots {\left\lfloor {\left\lfloor {\frac {u}{B}}\right\rfloor }\right\rfloor }{\dots /B}\right\rfloor =0}$.

Метод 2 (Умножение на В с использованием представления чисел в формате по основанию b). Если представление числа u по основанию b имеет вид ${\displaystyle (u_{m}\dots u_{1}u_{0})_{b}}$, то можно, воспользовавшись арифметическими операциями с числами, которые представлены в формате по основанию В, получить полином ${\displaystyle u_{m}b^{m}+\dots +u_{1}b+u_{m}u_{0}=u}$ в виде
((${\displaystyle \dots (u_{m}b+u_{m-1}){b}+\dots )b+u_{1}b+u_{0}}$ .

Метод 1 (a) (Умножение на b с использованием представления чисел в формате по основанию В). Для данного дробного числа и можно вычислить значения разрядов ${\displaystyle (.U_{-1}U_{-2}...)_{B}}$ его представления по основанию В следующим образом:
${\displaystyle U_{-1}=\left\lfloor \ {uB}\right\rfloor }$, ${\displaystyle U_{-2}{=}\left\lfloor \ {{uB}B}\right\rfloor }$, ${\displaystyle U_{-3}=\left\lfloor \ {((uB)B)B}\right\rfloor }$ ,… где {х} означает xmod1 = х- ${\displaystyle \left\lfloor \ {x}\right\rfloor }$. Чтобы округлить результат до М разрядов, вычисления можно прервать после получения ${\displaystyle U_{M}}$, причем если {…{{uВ}В}...В} больше 1/2, то значение ${\displaystyle U_{M}}$ следует увеличить на единицу. (Заметим, однако, что эта операция может привести к необходимости выполнения переносов, которые должны быть при помощи арифметических операций по основанию В включены в результат. Было бы проще перед началом вычислений прибавить к исходному числу u константу ${\displaystyle 1/2B^{-M}}$, но это может привести к неправильному результату, если в компьютере число ${\displaystyle 1/2B^{-M}}$ не может быть точно представлено в формате по основанию b. Заметим также, что возможно округление результата до ${\displaystyle (1.00...0)^{B}}$, если ${\displaystyle b^{m}}$ ${\displaystyle \geq }$ ${\displaystyle 2B^{M}}$).
Метод 2 (a) (Умножение на В с использованием представления чисел в формате по основанию b). Если представление числа и по основанию b имеет вид ${\displaystyle (u_{m}{...}u_{1}u_{0})_{b}}$, то можно, воспользовавшись арифметическими операциями с числами, которые представлены в формате по основанию В, получить полином ${\displaystyle u_{m}b^{m}+{...}+u_{1}b+u_{m}u_{0}=u}$ в виде
((… ${\displaystyle (u_{m}b+u_{m-1}){b}}$ + …) ${\displaystyle b}$ + ${\displaystyle u_{1}b+u_{0}}$ .

Способы преобразования дробных чисел

Метод 1 (b) (Умножение на b с использованием представления чисел в формате по основанию В). Для данного дробного числа u можно вычислить значения разрядов ${\displaystyle (0.U_{-1}U_{-2}...)_{B}}$ его представления по основанию В следующим образом:
${\displaystyle U_{-1}=\left\lfloor \ {uB}\right\rfloor }$, ${\displaystyle U_{-2}{=}\left\lfloor \ {{uB}B}\right\rfloor }$, ${\displaystyle U_{-3}=\left\lfloor \ {((uB)B)B}\right\rfloor }$ ,… где {х} означает xmod1 = х- ${\displaystyle \left\lfloor \ {x}\right\rfloor }$. Чтобы округлить результат до М разрядов, вычисления можно прервать после получения ${\displaystyle U_{M}}$, причем если {…{{uВ}В}...В} больше 1/2, то значение ${\displaystyle U_{M}}$ следует увеличить на единицу. (Заметим, однако, что эта операция может привести к необходимости выполнения переносов, которые должны быть при помощи арифметических операций по основанию В включены в результат. Было бы проще перед началом вычислений прибавить к исходному числу u константу ${\displaystyle 1/2B^{-M}}$, но это может привести к неправильному результату, если в компьютере число ${\displaystyle 1/2B^{-M}}$ не может быть точно представлено в формате по основанию b. Заметим также, что возможно округление результата до ${\displaystyle (1.00...0)^{B}}$, если ${\displaystyle b^{m}}$ ${\displaystyle \geq }$ ${\displaystyle 2B^{M}}$ ).

Метод 2 (b)(Деление на b с использованием представления чисел в формате по основанию В). Если число u представлено по основанию b в виде ${\displaystyle (0.u_{-1}u_{-2}...u_{-m})_{b}}$, то можно, используя арифметические операции по основанию В, вычислить ${\displaystyle u_{-1}b^{-1}+u_{-2}b^{-2}+{...}+u_{-m}b{-m}}$ в виде
${\displaystyle ((...(u_{-m}/b+u_{1-m})/b+...+u_{-2})/b+u_{-1})/b}$. Необходимо внимательно следить за погрешностями, возникающими при усечениях или округлениях во время выполнения операции деления на b; они, как правило, незначительны, но это бывает не всегда.

Преобразование с многократной точностью

Начинать преобразование очень длинных чисел удобнее всего с преобразования блоков разрядов, операции с которыми можно выполнять с однократной точностью. Затем следует объединить эти блоки, пользуясь простыми способами, которые специфичны для многократной точности. Например, пусть 10n-наивысшая степень 10, меньшая, чем размер машинного слова. Тогда:
а) чтобы преобразовать целое "Число с многократной точностью из двоичного формата в десятичный, необходимо многократно разделить его на 10n (выполняя таким образом преобразование из двоичной системы счисления в десятичную с основанием 10n по методу 1, а); при помощи операций с однократной точностью получим n десятичных разрядов для каждой единицы представления в системе счисления с основанием 10n;
b) чтобы преобразовать дробную "Часть числа с многократной точностью из двоичного формата в десятичный, поступим подобным образом, умножив его на ${\displaystyle 10^{n}}$: (т.е. использовав метод 2, а, где В= 10n);
с) чтобы преобразовать целое число с многократной точностью из десятичной системы счисления в двоичную, преобразуем сначала блоки по n разрядов; затем для перехода из системы счисления с основанием 10n в двоичный формат используем метод 1, b;
d) для преобразования дробной части с многократной точностью из представления в десятичном формате в двоичный сначала выполним преобразование в систему с основанием 10n, как и в процедуре (с), а затем используем метод 2, b.

Алгоритмы деления

Алгоритм деления n-битового числа u на n-битовое число v должен выдавать результатом два n-битовых числа - u mod v и u div v. Описанные ниже алгоритмы не применимы на практике, так как находят вещественное число, а не два n-битовых числа, результата деления.

В теории чтобы разделить n-битовое число u на n - битовое число v, можно сначала найти n-битовое приближение к числу 1/v, затем умножить его на u, что даст приближение ${\displaystyle {\hat {q}}}$ к ${\displaystyle u/v}$ , И наконец выполнить ещё одно умножение для внесения небольшой коррекции в ${\displaystyle {\hat {q}}}$ , чтобы убедиться, что выполняется неравенство ${\displaystyle 0\leq u-qv<v}$ . Исходя из сказанного, достаточно иметь эффективный алгоритм, который формировал бы по заданному n-битовому числу приближенное значение числа, обратного n-битовому числу. Далее применить алгоритм умножения n-битовых чисел.[9]

Алгоритм R (Получение обратной величины с высокой точностью) Пусть число v имеет двоичное представление ${\displaystyle v=(0.v_{1}v_{2}v_{3})_{2}}$, где ${\displaystyle v_{1}=1}$. Этот алгоритм вычисляет приближение z числа ${\displaystyle 1/v}$, такое, что
${\displaystyle |z-1/v|\leq 2^{-n}}$.
R1(Начальное приближение) Присвоить ${\displaystyle z\leftarrow {\frac {1}{4}}\left\lfloor {\frac {32}{(4v_{1}+2v_{2}+v_{3})}}\right\rfloor }$ и ${\displaystyle k\leftarrow 0}$.
R2 (Итерация по Ньютону) Здесь имеем число z в двоичном виде ${\displaystyle (xx.xx...x)_{2}}$ с ${\displaystyle 2^{k}+1}$ знаками после разделяющей точки и ${\displaystyle z\leq 2}$ . При помощи программы быстрого умножения точно вычислить ${\displaystyle z^{2}=(xx.xx...x)_{2}}$ . После этого точно вычислить ${\displaystyle V_{k}z^{2}}$, где ${\displaystyle V_{k}=(0.v_{1}v_{2}...v_{2^{k+1}+3})_{2}}$ . Затем присвоить ${\displaystyle z\leftarrow 2z-V_{k}z^{2}+r}$, где ${\displaystyle r}$ , удовлетворяющее неравенству ${\displaystyle 0\leq r<2^{-2^{k+1}-1}}$ , прибавляется при необходимости для округления ${\displaystyle z}$, чтобы ${\displaystyle z}$ было кратным ${\displaystyle 2^{-2^{k+1}-1}}$ . И наконец присвоить ${\displaystyle k\leftarrow k+1}$ .
R3 Если ${\displaystyle 2^{k}<n}$ , то вернуться к шагу R2; в противном случае выполнение алгоритма заканчивается.

Другие алгоритмы

Примечания

1. 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  (неопр.). Дата обращения: 13 декабря 2013. Архивировано 14 марта 2013 года.
6. Donald E. Knuth «The Art of Computer Programming», Секция 4.3.3, часть С
7. Paul Zimmermann. Karatsuba Square Root. [Research Report] RR-3805, 1999, pp.8. <inria-00072854 Архивная копия от 2 декабря 2014 на Wayback Machine>
8. Donald E. Knuth «The Art of Computer Programming», том 2, Секция 4.4
9. Donald E. Knuth «The Art of Computer Programming», том 2, Секция 4.3.3

Литература

• 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
• Электронные средства и системы управления : Материалы докладов Международной научно-практической конференции (13-16 октября 2010 г.). — Томск: В-Спектр, 2011: В 2 ч. — Ч. 2. — 178 с. ISBN 978-5-91191-223-6, С.123-129