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

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

Алгоритм потребує   бітових операцій, де   — кількість двійкових цифр у добутку[7].

На практиці алгоритм Шенхаге — Штрассена стає швидшим методу Тоома — Кука для множення чисел із кількома десятками тисяч десяткових знаків (  )[8][9].

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

 .

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

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

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

Для цілочисельного ділення багаторозрядного числа на однорозрядне застосовується стандартне ділення стовпчиком[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 — ділення з невеликою часткою

Джерела ред.

  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 web}}: Cite має пустий невідомий параметр: |1= (довідка)

Посилання ред.