Довга арифметика

Довга арифметика (в обчислювальній техніці) — операції над числами, розрядність яких перевищує довжину машинного слова обчислювальної машини. По суті арифметика з великими числами являє собою набір алгоритмів виконання базових операцій (додавання, множення, зведення в степінь …) над числами, реалізованими не апаратно, а програмно, застосовуючи базові апаратні засоби обчислення для операцій з числами фіксованого розміру, що обмежений наявним процесором чи обраною мовою програмування. Окремий випадок — арифметика довільної точності (англ. Arbitrary-precision arithmetic) — в якій довжина чисел обмежена тільки обсягом доступної пам'яті комп'ютера.

Потреба

• Комп'ютери малої розрядності, мікроконтролери. Наприклад, мікроконтролери серії AVR мають 8-бітні регістри й 10-бітний АЦП — так що при обробці інформації без довгої арифметики не обійтися.
• Довга арифметика застосовується в криптографічних протоколах RSA і Діффі — Геллмана. Із метою запобігання відомих атак, розміри чисел мають перевищувати 2¹⁰²⁴ (~10³⁰⁹). Поширені мови програмування, такі як C і Java, здебільшого можуть оперувати тільки числами обмеженої довжини.
• Математичне та фінансове ПЗ потребує, щоб результат обчислення на комп'ютері збігався з результатами обчислення на папері до останнього розряду. Зокрема, калькулятор Windows (починаючи з Windows 95).
• Числа з рухомою комою. У комп'ютерах числа з рухомою комою представлені у вигляді n = s * m * b^x, де n — саме число, s — знак числа, m — мантиса, b — основа показникової функції, x — показник степеня. При обробці чисел підвищеної точності, розміри мантиси можуть перевищити апаратні або програмні обмеження. У таких випадках для мантиси також доводиться застосовувати алгоритми роботи з великими числами.

Апаратні засоби для роботи з довгою арифметикою

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

• Прапор переносу. Операції «додати / відняти, з перенесенням», циклічний зсув через біт перенесення.
• Автоінкрементні чи автодекрементні операції доступу до пам'яті.

Порядок слів

Незалежно від апаратного порядку байтів та порядку байтів в операційній системі, у довгій арифметиці застосовується власний порядок слів: або «спочатку молодші» (англ. little-endian), або «спочатку старші» (big-endian). Частіше застосовується порядок «спочатку молодші» — оскільки більшість операцій із довгими числами починається з їх молодших розрядів.

Реалізація в мовах програмування

У більшості мов високого рівня реалізовано арифметику з числами довжиною два машинних слова. Спочатку процесори були переважно 16-бітовими, таким чином, можна було оперувати з числами довжиною до 32 біт (чотири байти). Арифметику з довшими числами зазвичай доводилося програмувати самостійно, у міру потреби оптимізуючи на асемблері — оскільки у мовах високого рівня зазвичай немає таких абстракцій як «регістрова пара» чи «біт перенесення».

Довга десяткова арифметика була реалізована в мові програмування Алмір-65 на ЕОМ МИР-1 (1965 рік) і в мові програмування АНАЛІТИК на ЕОМ МИР-2.

У Turbo Pascal (1980-і роки) існував шестибайтовий емулюючий дробовий тип — Real (у Delphi перейменований в Real48). Обчислення з ним також проводилися за допомогою довгої арифметики.

Після поширення 32-бітової архітектури (наприкінці 1900-х років) у багатьох мовах програмування з'явилася можливість оперувати 64-бітовими числами. Однак, вбудовані типи даних у мовах програмування мають розмір, який, здебільшого, не перевищує 64 біти. Наприклад, для C99 максимальна довжина вбудованого типу даних long становить 64 біти, що дозволяє оперувати з числами десь до 10¹⁹. Втім, у деяких мовах програмування, таких як Python, є спеціалізовані бібліотеки для обчислень з довгими числами.

На початку 2000-х років для роботи з великими числами розроблено декілька оптимізованих універсальних бібліотек, зокрема:

• GMP
• LibTomMath

Алгоритми

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

Базовий

Шкільний метод множення «у стовпчик» потребує часу O (N * M), де N, M — розміри перемножуваних чисел.

Ефективніші алгоритми базового множення розробили Кнут і Комба (англ. Comba P.G.). Хоча асимптотична складність їх методів така ж, як і у шкільного ($O(N^{2})$), але в них зберігається менше проміжних даних, тому вони працюють значно швидше.

Множення Карацуби

Алгоритм забезпечує найпростішу реалізацію з асимптотичною складністю меншою $O(N^{2})$.

У найпростішому варіанті метод Карацуби ґрунтується на формулі:

$(a+bx)(c+dx)=ac+((a+b)(c+d)-ac-bd)x+bdx^{2}.$

Таким чином обчислення добутку двох чисел довжиною 2 потребує лише трьох множень — $a\times c,\quad b\times d,\quad (a+b)\times (c+d)$ — замість чотирьох (як у базових методах) та додаткових додавання, віднімання і зсувів. Якщо операція множення потребує значно більшого часу ніж додаткові операції, то навіть безпосереднє застосування формули прискорює множення чисел подвійної точності.

Але основна ідея методу полягає в тому, що його можна застосовувати рекурсивно. Тоді для досить великих N час множення скорочується до межі $O(N^{\lg 3}\approx N^{1.585})$, що дає вельми відчутну перевагу.

Рекурсивне множення Карацуби стає ефективнішим за швидкі базові методи для чисел довжиною десь 450—620 біт (тобто, 135—185 десяткових розрядів).

Алгоритм Тоома — Кука

Метод Карацуби узагальнено в алгоритмі Тоома — Кука.

Наприклад, якщо поділити множники на три рівні частини (замість двох, як у методі Карацуби), то добуток можна обчислити за п'ять операцій множення таких частин (тоді як базовий алгоритм потребує дев'яти множень). Якщо ж поділити множники на чотири частини, то обчислення добутку потребує семи множень (замість 16 за базовими алгоритмами).

Загалом довгі числа можна поділяти на довільну кількість частин і таким чином отримати алгоритм з асимптотичною обчислювальною складністю $O(N\times 2^{\sqrt {2\log _{2}N}}\log _{2}N)$.

Алгоритм Шьонхаге — Штрассена

Застосування швидкого перетворення Фур'є для множення великих чисел запропонував 1968 року Штрассен. Разом із Шьоханге вони уточнили метод та опублікували алгоритм 1971 року.
Алгоритм множить числа x і y за модулем 2^N+1: x * y mod 2^N+1. Якщо потрібен повний результат множення (а не залишок по модулю), то на N слід накласти обмеження:

N >= bits (x) + bits (y)

Подібно до методу Карацуби, застосовується поділ вхідних чисел на 2^k частин, далі числа розглядають як поліноми від однієї змінної (основи системи числення), а для обчислення добутку поліномів застосовують дискретне перетворення Фур'є: обчислюють значення поліномів-множників у 2^k точках і виконують швидке перетворення Фур'є; образ добутку обчислюють шляхом попарного множення в 2^k точках (що потребує лише D=2^k операцій множення замість D² у звичайному алгоритмі множення поліномів); до результату застосовують обернене перетворення Фур'є; поліном-добуток будують шляхом інтерполяції за його значеннями в 2^k точках. Після обчислення многочлена-добутку в його коефіцієнтах потрібно зробити знесення старших розрядів, щоб отримати нормалізований запис числа-добутку в обраній системі числення.

Оскільки у швидкому перетворенні Фур'є (як у прямому, так і в оберненому) застосовуються лише операції додавання, віднімання і зсуву (ним замінено множення на степені двійки), то власне множення виконується лише для обчислення образу добутку.

Алгоритм потребує $O(N\cdot \log N\cdot \log \log N)$ бітових операцій, де $N$ — кількість двійкових цифр у добутку.

На практиці алгоритм Шенхаге — Штрассена стає швидшим методу Тоома — Кука для множення чисел із кількома десятками тисяч десяткових знаків ($10^{10000}$—$10^{40000}$).

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

Для цілочисельного ділення багаторозрядного числа на однорозрядне застосовується стандартне ділення стовпчиком.

У найпростішому випадку подібний алгоритм можна застосовувати й для ділення багаторозрядних чисел. Втім, Дональд Кнут у своєму Мистецтві програмування запропонував кращий алгоритм.

Рекурсивний алгоритм Бурнікеля — Циглера застосовується для ділення дуже довгих цілих чисел. У цьому алгоритмі, зокрема, виконується множення довгих чисел, тож його обчислювальна складність визначається застосованим методом множення:

• Якщо для множення застосовуються алгоритми Карацуби чи Тоома—Кука зі складністю $O(n^{\alpha })$, то складність ділення також буде $O(n^{\alpha })$.
• Якщо ж для множення застосовуються асимптотично швидші алгоритми, подібні до алгоритму Шьонхаге — Штрассена, зі складністю $O(n\cdot \log n\cdot \log \log n)$, то складність ділення становитиме $O(n\log ^{2}n\log \log n)$.

Приклади застосування

У пакеті GNU MP (GMP) версії 6.2.1 застосовуються такі алгоритми ділення:

• Найпростіший випадок — ділення багаторозрядного числа на однорозрядне (Single Limb Division).
• Базовий алгоритм ділення багатозначного числа на багатозначне (Basecase Division). Описано у Дональда Кнута в його Мистецтві програмування.
• Ділення методом «розділяй і володарюй» (Divide and Conquer Division).
• Block-Wise Barrett Division
• Exact Division — обчислюється тільки частка
• Exact Remainder — обчислюється тільки залишок
• Small Quotient Division — ділення з невеликою часткою

Посилання

• Knuth, Donald (2008). Seminumerical Algorithms. The Art of Computer Programming. Т. 2 (вид. 3rd). Addison-Wesley. ISBN 978-0-201-89684-8.
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — Москва : МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.