Довга арифметика
Довга арифметика (в обчислювальній техніці) — операції над числами, розрядність яких перевищує довжину машинного слова обчислювальної машини. По суті арифметика з великими числами являє собою набір алгоритмів виконання базових операцій (додавання, множення, зведення в степінь …) над числами, реалізованими не апаратно, а програмно, застосовуючи базові апаратні засоби обчислення для операцій з числами фіксованого розміру, що обмежений наявним процесором чи обраною мовою програмування. Окремий випадок — арифметика довільної точності (англ. Arbitrary-precision arithmetic) — в якій довжина чисел обмежена тільки обсягом доступної пам'яті комп'ютера.
- Комп'ютери малої розрядності, мікроконтролери. Наприклад, мікроконтролери серії AVR мають 8-бітні регістри й 10-бітний АЦП — так що при обробці інформації без довгої арифметики не обійтися.
- Довга арифметика застосовується в криптографічних протоколах RSA і Діффі — Геллмана. Із метою запобігання відомих атак, розміри чисел мають перевищувати 21024 (~10309). Поширені мови програмування, такі як C і Java, здебільшого можуть оперувати тільки числами обмеженої довжини.
- Математичне та фінансове ПЗ потребує, щоб результат обчислення на комп'ютері збігався з результатами обчислення на папері до останнього розряду. Зокрема, калькулятор Windows (починаючи з Windows 95).
- Числа з рухомою комою. У комп'ютерах числа з рухомою комою представлені у вигляді n = s * m * bx, де 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 біти, що дозволяє оперувати з числами десь до 1019. Втім, у деяких мовах програмування, таких як Python, є спеціалізовані бібліотеки для обчислень з довгими числами.
На початку 2000-х років для роботи з великими числами розроблено декілька оптимізованих універсальних бібліотек, зокрема:
- GMP
- LibTomMath
Шкільний метод множення «у стовпчик» потребує часу O (N * M), де N, M — розміри перемножуваних чисел.
Ефективніші алгоритми базового множення розробили Кнут[1] і Комба (англ. Comba P.G.)[2]. Хоча асимптотична складність їх методів така ж, як і у шкільного (), але в них зберігається менше проміжних даних, тому вони працюють значно швидше[3].
Алгоритм забезпечує найпростішу реалізацію з асимптотичною складністю меншою .
У найпростішому варіанті метод Карацуби ґрунтується на формулі:
Таким чином обчислення добутку двох чисел довжиною 2 потребує лише трьох множень — — замість чотирьох (як у базових методах) та додаткових додавання, віднімання і зсувів. Якщо операція множення потребує значно більшого часу ніж додаткові операції, то навіть безпосереднє застосування формули прискорює множення чисел подвійної точності.
Але основна ідея методу полягає в тому, що його можна застосовувати рекурсивно. Тоді для досить великих N час множення скорочується до межі , що дає вельми відчутну перевагу[4].
Рекурсивне множення Карацуби стає ефективнішим за швидкі базові методи для чисел довжиною десь 450—620 біт (тобто, 135—185 десяткових розрядів)[5].
Метод Карацуби узагальнено в алгоритмі Тоома — Кука[en].
Наприклад, якщо поділити множники на три рівні частини (замість двох, як у методі Карацуби), то добуток можна обчислити за п'ять операцій множення таких частин (тоді як базовий алгоритм потребує дев'яти множень). Якщо ж поділити множники на чотири частини, то обчислення добутку потребує семи множень (замість 16 за базовими алгоритмами).
Загалом довгі числа можна поділяти на довільну кількість частин і таким чином отримати алгоритм з асимптотичною обчислювальною складністю [6].
Застосування швидкого перетворення Фур'є для множення великих чисел запропонував 1968 року Штрассен. Разом із Шьоханге вони уточнили метод та опублікували алгоритм 1971 року[7].
Алгоритм множить числа x і y за модулем 2N+1: x * y mod 2N+1. Якщо потрібен повний результат множення (а не залишок по модулю), то на N слід накласти обмеження:
- N >= bits (x) + bits (y)
Подібно до методу Карацуби, застосовується поділ вхідних чисел на 2k частин, далі числа розглядають як поліноми від однієї змінної (основи системи числення), а для обчислення добутку поліномів застосовують дискретне перетворення Фур'є: обчислюють значення поліномів-множників у 2k точках і виконують швидке перетворення Фур'є; образ добутку обчислюють шляхом попарного множення в 2k точках (що потребує лише D=2k операцій множення замість D2 у звичайному алгоритмі множення поліномів); до результату застосовують обернене перетворення Фур'є; поліном-добуток будують шляхом інтерполяції за його значеннями в 2k точках. Після обчислення многочлена-добутку в його коефіцієнтах потрібно зробити знесення старших розрядів, щоб отримати нормалізований запис числа-добутку в обраній системі числення.
Оскільки у швидкому перетворенні Фур'є (як у прямому, так і в оберненому) застосовуються лише операції додавання, віднімання і зсуву (ним замінено множення на степені двійки), то власне множення виконується лише для обчислення образу добутку.
Алгоритм потребує бітових операцій, де — кількість двійкових цифр у добутку[7].
На практиці алгоритм Шенхаге — Штрассена стає швидшим методу Тоома — Кука для множення чисел із кількома десятками тисяч десяткових знаків (—)[8][9].
![]() | Цей розділ потребує доповнення. |
Для цілочисельного ділення багаторозрядного числа на однорозрядне застосовується стандартне ділення стовпчиком[10].
У найпростішому випадку подібний алгоритм можна застосовувати й для ділення багаторозрядних чисел[11]. Втім, Дональд Кнут у своєму Мистецтві програмування запропонував кращий алгоритм[12][13].
Рекурсивний алгоритм Бурнікеля — Циглера[de] застосовується для ділення дуже довгих цілих чисел. У цьому алгоритмі, зокрема, виконується множення довгих чисел, тож його обчислювальна складність визначається застосованим методом множення[14]:
- Якщо для множення застосовуються алгоритми Карацуби чи Тоома—Кука зі складністю , то складність ділення також буде .
- Якщо ж для множення застосовуються асимптотично швидші алгоритми, подібні до алгоритму Шьонхаге — Штрассена, зі складністю , то складність ділення становитиме .
У пакеті GNU MP[en] (GMP) версії 6.2.1 застосовуються такі алгоритми ділення[15]:
- Найпростіший випадок — ділення багаторозрядного числа на однорозрядне (Single Limb Division).
- Базовий алгоритм ділення багатозначного числа на багатозначне (Basecase Division). Описано у Дональда Кнута в його Мистецтві програмування[13].
- Ділення методом «розділяй і володарюй» (Divide and Conquer Division).
- Block-Wise Barrett Division
- Exact Division — обчислюється тільки частка
- Exact Remainder — обчислюється тільки залишок
- Small Quotient Division — ділення з невеликою часткою
- ↑ Knuth, 2008, Section 4.3.1. Algorithm M.
- ↑ Comba P.G. Experiments in fast multiplication of integers // Technical Report G320-2158.
- ↑ Василенко, 2003, с. 256—258.
- ↑ Knuth, 2008, Section 4.3.3, Algorithm A.
- ↑ Василенко, 2003, с. 258—259.
- ↑ Knuth, 2008, Section 4.3.3, Algorithm T.
- ↑ а б Knuth, 2008, Section 4.3.3, Algorithm С.
- ↑ Meter van R., Itoh K. M. Fast quantum modular exponentiation // Physical Review A. — 2005. — Т. 71. Архівовано з джерела 7 лютого 2006. Процитовано 2023-06-20.
- ↑ Luis Carlos Coronado García. Can Schönhage multiplication speed up the RSA encryption or decryption? // University of Technology. — Darmstadt, 2005.
- ↑ Василенко, 2003, с. 259.
- ↑ Василенко, 2003, с. 260—262.
- ↑ Василенко, 2003, с. 262—269.
- ↑ а б Knuth, 2008, Section 4.3.1, Algorithm D.
- ↑ Christoph Burnikel; Joachim Ziegler (1998-10). Fast Recursive Division (англ.). Max-Planck-Institut für Informatik. Архів оригіналу за 3 грудня 2013. Процитовано 27 червня 2014.
- ↑ Division Algorithms. GNU MP 6.2.1. Процитовано 20 червня 2023.
{{cite web}}
: Cite має пустий невідомий параметр:|1=
(довідка)
- 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.
![]() |
Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її. |