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

Довга арифметика (в обчислювальній техніці) — операції над числами, розрядність яких перевищує довжину машинного слова обчислювальної машини. По суті арифметика з великими числами являє собою набір алгоритмів виконання базових операцій (додавання, множення, зведення в степінь …) над числами, реалізованими не апаратно, а програмно, застосовуючи базові апаратні засоби обчислення для операцій з числами фіксованого розміру, що обмежений наявним процесором чи обраною мовою програмування. Окремий випадок — арифметика довільної точності (англ. 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.). Хоча асимптотична складність їх методів така ж, як і у шкільного (${\displaystyle O(N^{2})}$), але в них зберігається менше проміжних даних, тому вони працюють значно швидше.

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

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

Докладніше: Множення Карацуби

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

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

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

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

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

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

Метод Карацуби узагальнено в ^[en].

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

Загалом довгі числа можна поділяти на довільну кількість частин і таким чином отримати алгоритм з асимптотичною обчислювальною складністю ${\displaystyle 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)

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

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

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

Докладніше: Швидке перетворення Фур'є

Параметр k контролює поділ вхідних даних на 2^k частин, розміром M = N / 2^k кожна. Це накладає обмеження на N: воно має ділитися без остачі на 2^k. Попарне множення виконується по модулю 2^N', де N' = 2 * M + k + 3 — число, округлене до добутку числа 2^k на процесорний розмір елементів у бітах. Такий вибір N' дозволяє проводити розрахунки без втрат через переповнення. Результат інтерполяції можна представити в наступному вигляді:

${\displaystyle w[n]=\sum _{i+j=b*2^{k}+n}^{b=0,1}(-1)^{b}*x[i]*y[i]}$.

Щоб розв'язати цю систему рівнянь, можна взяти точки g_i, де і змінюється від 0 до 2^k−1, а g = 2^{(2N' / 2k)} . g є 2^k-им первісним коренем по модулю 2^N' +1. Такий вибір вузлів інтерполяції гарантує, що система буде дозволена. Таким чином, у швидкому перетворенні Фур'є застосовуються тільки операції зсуву, додавання й віднімання.

Інші алгоритми множення

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

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

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

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

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

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

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

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

Джерела

1. Knuth, 2008, Section 4.3.1. Algorithm M.
2. Comba P.G. Experiments in fast multiplication of integers // Technical Report G320-2158.
3. Василенко, 2003, с. 256—258.
4. Knuth, 2008, Section 4.3.3, Algorithm A.
5. Василенко, 2003, с. 258—259.
6. Knuth, 2008, Section 4.3.3, Algorithm T.
7. Knuth, 2008, Section 4.3.3, Algorithm С.
8. Meter van R., Itoh K. M. Fast quantum modular exponentiation // Physical Review A. — 2005. — Т. 71. з джерела 7 лютого 2006. Процитовано 2023-06-20.
9. Luis Carlos Coronado García. Can Schönhage multiplication speed up the RSA encryption or decryption? // University of Technology. — Darmstadt, 2005.
10. Василенко, 2003, с. 259.
11. Василенко, 2003, с. 260—262.
12. Василенко, 2003, с. 262—269.
13. Knuth, 2008, Section 4.3.1, Algorithm D.
14. Christoph Burnikel; Joachim Ziegler (1998-10). Fast Recursive Division (англ.). Max-Planck-Institut für Informatik. оригіналу за 3 грудня 2013. Процитовано 27 червня 2014.
15. Division Algorithms. GNU MP 6.2.1. Процитовано 20 червня 2023. {{}}: Cite має пустий невідомий параметр: |1= ()

Посилання

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