Довга арифметика (в обчислювальній техніці) — операції над числами, розрядність яких перевищує довжину машинного слова обчислювальної машини. По суті арифметика з великими числами являє собою набір алгоритмів виконання базових операцій (додавання, множення, зведення в степінь …) над числами, реалізованими не апаратно, а програмно, застосовуючи базові апаратні засоби обчислення для операцій з числами фіксованого розміру, що обмежений наявним процесором чи обраною мовою програмування. Окремий випадок — арифметика довільної точності () — в якій довжина чисел обмежена тільки обсягом доступної пам'яті комп'ютера.
Потреба
Комп'ютери малої розрядності, мікроконтролери. Наприклад, мікроконтролери серії AVR мають 8-бітні регістри й 10-бітний АЦП — так що при обробці інформації без довгої арифметики не обійтися. Довга арифметика застосовується в криптографічних протоколах RSA і Діффі — Геллмана. Із метою запобігання відомих атак, розміри чисел мають перевищувати 21024 (~10309). Поширені мови програмування, такі як C і Java, здебільшого можуть оперувати тільки числами обмеженої довжини. Математичне та фінансове ПЗ потребує, щоб результат обчислення на комп'ютері збігався з результатами обчислення на папері до останнього розряду. Зокрема, калькулятор Windows (починаючи з Windows 95). Числа з рухомою комою. У комп'ютерах числа з рухомою комою представлені у вигляді n = s * m * bx, де n — саме число, s — знак числа, m — мантиса, b — основа показникової функції, x — показник степеня. При обробці чисел підвищеної точності, розміри мантиси можуть перевищити апаратні або програмні обмеження. У таких випадках для мантиси також доводиться застосовувати алгоритми роботи з великими числами.
Апаратні засоби для роботи з довгою арифметикою
Строго кажучи, для реалізації арифметики довільної точності від процесора вимагається лише непряма адресація; в арифметиці фіксованої точності можна обійтися навіть без неї. Тим не менше, певні функції процесора прискорюють довгу арифметику, одночасно спрощуючи її програмування.
Прапор переносу. Операції «додати / відняти, з перенесенням», циклічний зсув через біт перенесення. Автоінкрементні чи автодекрементні операції доступу до пам'яті.
Порядок слів
Незалежно від апаратного порядку байтів та порядку байтів в операційній системі, у довгій арифметиці застосовується власний порядок слів: або «спочатку молодші» (), або «спочатку старші» (). Частіше застосовується порядок «спочатку молодші» — оскільки більшість операцій із довгими числами починається з їх молодших розрядів.
Реалізація в мовах програмування У більшості мов високого рівня реалізовано арифметику з числами довжиною два машинних слова. Спочатку процесори були переважно 16-бітовими, таким чином, можна було оперувати з числами довжиною до 32 біт (чотири байти). Арифметику з довшими числами зазвичай доводилося програмувати самостійно, у міру потреби оптимізуючи на асемблері — оскільки у мовах високого рівня зазвичай немає таких абстракцій як «регістрова пара» чи «біт перенесення».
Довга десяткова арифметика була реалізована в мові програмування Алмір-65 на ЕОМ МИР-1 (1965 рік) і в мові програмування АНАЛІТИК на ЕОМ МИР-2.
У Turbo Pascal (1980-ті роки) існував шестибайтовий емулюючий дробовий тип — Real (у Delphi перейменований в Real48). Обчислення з ним також проводилися за допомогою довгої арифметики.
Після поширення 32-бітової архітектури (наприкінці 1980-х років) у багатьох мовах програмування з'явилася можливість оперувати 64-бітовими числами. Однак, вбудовані типи даних у мовах програмування мають розмір, який, здебільшого, не перевищує 64 біти. Наприклад, для C99 максимальна довжина вбудованого типу даних long становить 64 біти, що дозволяє оперувати з числами десь до 1019. Втім, у деяких мовах програмування, таких як Python, є спеціалізовані бібліотеки для обчислень з довгими числами.
На початку 2000-х років для роботи з великими числами розроблено декілька оптимізованих універсальних бібліотек, зокрема: GMP LibTomMath
Алгоритми
Алгоритми множення
Базовий Шкільний метод множення «у стовпчик» потребує часу O (N * M), де N, M — розміри перемножуваних чисел.
Ефективніші алгоритми базового множення розробили Кнут і Комба (). Хоча асимптотична складність їх методів така ж, як і у шкільного (), але в них зберігається менше проміжних даних, тому вони працюють значно швидше.
Множення Карацуби Алгоритм забезпечує найпростішу реалізацію з асимптотичною складністю меншою .
У найпростішому варіанті метод Карацуби ґрунтується на формулі:
Таким чином обчислення добутку двох чисел довжиною 2 потребує лише трьох множень — — замість чотирьох (як у базових методах) та додаткових додавання, віднімання і зсувів. Якщо операція множення потребує значно більшого часу ніж додаткові операції, то навіть безпосереднє застосування формули прискорює множення чисел подвійної точності.
Але основна ідея методу полягає в тому, що його можна застосовувати рекурсивно. Тоді для досить великих N час множення скорочується до межі , що дає вельми відчутну перевагу.
Рекурсивне множення Карацуби стає ефективнішим за швидкі базові методи для чисел довжиною десь 450—620 біт (тобто, 135—185 десяткових розрядів).
Алгоритм Тоома — Кука Метод Карацуби узагальнено в .
Наприклад, якщо поділити множники на три рівні частини (замість двох, як у методі Карацуби), то добуток можна обчислити за п'ять операцій множення таких частин (тоді як базовий алгоритм потребує дев'яти множень). Якщо ж поділити множники на чотири частини, то обчислення добутку потребує семи множень (замість 16 за базовими алгоритмами).
Загалом довгі числа можна поділяти на довільну кількість частин і таким чином отримати алгоритм з асимптотичною обчислювальною складністю .
Алгоритм Шьонхаге — Штрассена
Застосування швидкого перетворення Фур'є для множення великих чисел запропонував 1968 року Штрассен. Разом із Шьоханге вони уточнили метод та опублікували алгоритм 1971 року. Алгоритм множить числа x і y за модулем 2N+1: x * y mod 2N+1. Якщо потрібен повний результат множення (а не залишок по модулю), то на N слід накласти обмеження: N >= bits (x) + bits (y) Подібно до методу Карацуби, застосовується поділ вхідних чисел на 2k частин, далі числа розглядають як поліноми від однієї змінної (основи системи числення), а для обчислення добутку поліномів застосовують дискретне перетворення Фур'є: обчислюють значення поліномів-множників у 2k точках і виконують швидке перетворення Фур'є; образ добутку обчислюють шляхом попарного множення в 2k точках (що потребує лише D=2k операцій множення замість D2 у звичайному алгоритмі множення поліномів); до результату застосовують обернене перетворення Фур'є; поліном-добуток будують шляхом інтерполяції за його значеннями в 2k точках. Після обчислення многочлена-добутку в його коефіцієнтах потрібно зробити знесення старших розрядів, щоб отримати нормалізований запис числа-добутку в обраній системі числення.
Оскільки у швидкому перетворенні Фур'є (як у прямому, так і в оберненому) застосовуються лише операції додавання, віднімання і зсуву (ним замінено множення на степені двійки), то власне множення виконується лише для обчислення образу добутку.
Алгоритм потребує бітових операцій, де — кількість двійкових цифр у добутку.
На практиці алгоритм Шенхаге — Штрассена стає швидшим методу Тоома — Кука для множення чисел із кількома десятками тисяч десяткових знаків (—).
Інші алгоритми множення
Алгоритми ділення Для цілочисельного ділення багаторозрядного числа на однорозрядне застосовується стандартне ділення стовпчиком.
У найпростішому випадку подібний алгоритм можна застосовувати й для ділення багаторозрядних чисел. Втім, Дональд Кнут у своєму Мистецтві програмування запропонував кращий алгоритм.
Рекурсивний застосовується для ділення дуже довгих цілих чисел. У цьому алгоритмі, зокрема, виконується множення довгих чисел, тож його обчислювальна складність визначається застосованим методом множення: Якщо для множення застосовуються алгоритми Карацуби чи Тоома—Кука зі складністю , то складність ділення також буде . Якщо ж для множення застосовуються асимптотично швидші алгоритми, подібні до алгоритму Шьонхаге — Штрассена, зі складністю , то складність ділення становитиме .
Приклади застосування У пакеті (GMP) версії 6.2.1 застосовуються такі алгоритми ділення: Найпростіший випадок — ділення багаторозрядного числа на однорозрядне (Single Limb Division). Базовий алгоритм ділення багатозначного числа на багатозначне (Basecase Division). Описано у Дональда Кнута в його Мистецтві програмування. Ділення методом «розділяй і володарюй» (Divide and Conquer Division). Block-Wise Barrett Division Exact Division — обчислюється тільки частка Exact Remainder — обчислюється тільки залишок Small Quotient Division — ділення з невеликою часткою
Джерела
Посилання