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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Джерела

[ред. | ред. код]
  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= (довідка)

Посилання

[ред. | ред. код]