Перегляд вихідного коду сторінки Довга арифметика

'''Довга арифметика''' (в обчислювальній техніці) —  операції над числами, розрядність яких перевищує довжину [[машинне слово | машинного слова]] обчислювальної машини. По суті арифметика з великими числами являє собою набір алгоритмів виконання базових операцій (додавання, множення, зведення в степінь …) над числами, реалізованими не апаратно, а програмно, застосовуючи базові апаратні засоби [[обчислення]] для операцій з числами фіксованого розміру, що обмежений наявним [[процесор]]ом чи обраною [[мова програмування|мовою програмування]]. Окремий випадок — '''арифметика довільної точності''' ({{lang-en|Arbitrary-precision arithmetic}}) — в якій довжина чисел обмежена тільки обсягом доступної пам'яті комп'ютера.

== Потреба ==

* Комп'ютери малої розрядності, [[мікроконтролер]]и. Наприклад, мікроконтролери серії [[AVR]] мають 8-бітні регістри й 10-бітний [[АЦП]]&nbsp;— так що при обробці інформації без довгої арифметики не обійтися.
* Довга арифметика застосовується в [[Криптографія|криптографічних]] протоколах [[RSA]] і [[Протокол Діффі — Геллмана|Діффі — Геллмана]]. Із метою запобігання відомих атак, розміри чисел мають перевищувати 2<sup>1024</sup> (~10<sup>309</sup>). Поширені мови програмування, такі як [[C (мова програмування)|C]] і [[Java]], здебільшого можуть оперувати тільки числами обмеженої довжини. 
* Математичне та фінансове ПЗ потребує, щоб результат обчислення на комп'ютері збігався з результатами обчислення на папері до останнього розряду. Зокрема, калькулятор Windows (починаючи з [[Windows 95]]).
* [[Число з рухомою комою|Числа з рухомою комою]]. У комп'ютерах числа з рухомою комою представлені у вигляді n =  s * m * b<sup>x</sup>, де n&nbsp;— саме число,  s&nbsp;—  знак числа, m&nbsp;— мантиса, b&nbsp;— основа [[показникова функція|показникової функції]], x&nbsp;— показник степеня. При обробці чисел підвищеної точності, розміри мантиси можуть перевищити апаратні або програмні обмеження. У таких випадках для мантиси також доводиться застосовувати алгоритми роботи з великими числами.

== Апаратні засоби для роботи з довгою арифметикою ==

Строго кажучи, для реалізації арифметики довільної точності від процесора вимагається лише непряма адресація; в арифметиці фіксованої точності можна обійтися навіть без неї. Тим не менше, певні функції процесора прискорюють довгу арифметику, одночасно спрощуючи її програмування.

* Прапор переносу. Операції «додати / відняти, з перенесенням», циклічний [[бітовий зсув|зсув через біт перенесення]].
* Автоінкрементні чи автодекрементні операції доступу до пам'яті.

== Порядок слів ==

Незалежно від апаратного [[порядок байтів|порядку байтів]] та порядку байтів в [[Операційна система|операційній системі]], у довгій арифметиці застосовується власний порядок слів: або «спочатку молодші» ({{lang-en|little-endian}}), або «спочатку старші» ({{lang|en|big-endian}}). Частіше застосовується порядок «спочатку молодші»&nbsp;— оскільки більшість операцій із довгими числами починається з їх молодших розрядів.

== Реалізація в мовах програмування ==
У більшості [[мова програмування високого рівня|мов високого рівня]] реалізовано арифметику з числами довжиною два [[Машинне слово|машинних слова]]. Спочатку [[процесор]]и були переважно [[16-бітова архітектура|16-бітовими]], таким чином, можна було оперувати з числами довжиною до 32 біт (чотири байти). Арифметику з довшими числами зазвичай доводилося програмувати самостійно, у міру потреби оптимізуючи на [[мова асемблера|асемблері]]&nbsp;— оскільки у мовах високого рівня зазвичай немає таких абстракцій як «регістрова пара» чи «біт перенесення».

Довга десяткова арифметика була реалізована в мові програмування Алмір-65 на ЕОМ МИР-1 (1965 рік) і в мові програмування [[АНАЛІТИК]] на ЕОМ [[МИР (ЕОМ)|МИР-2]].

У [[Turbo Pascal]] (1980-ті роки) існував шестибайтовий емулюючий дробовий тип&nbsp;— ''Real'' (у [[Delphi (мова програмування)|Delphi]] перейменований в ''Real48''). Обчислення з ним також проводилися за допомогою довгої арифметики.

Після поширення [[32-бітова архітектура|32-бітової архітектури]] (наприкінці 1980-х років) у багатьох мовах програмування з'явилася можливість оперувати 64-бітовими числами.
Однак, вбудовані типи даних у [[Мова програмування|мовах програмування]] мають розмір, який, здебільшого, не перевищує 64 біти. 
Наприклад, для [[C99]] максимальна довжина вбудованого типу даних long становить 64 [[біт]]и, що дозволяє оперувати з числами десь до 10<sup>19</sup>. Втім, у деяких мовах програмування, таких як [[Python]], є спеціалізовані бібліотеки для обчислень з довгими числами.

На початку 2000-х років для роботи з великими числами розроблено декілька оптимізованих універсальних бібліотек, зокрема:
* GMP
* LibTomMath

== Алгоритми ==

=== Алгоритми множення ===

==== Базовий ====
Шкільний метод множення «у стовпчик» потребує часу O (N * M), де N, M&nbsp;— розміри перемножуваних чисел.

Ефективніші алгоритми базового множення розробили [[Дональд Кнут|Кнут]]{{sfn|Knuth|2008|loc=Section 4.3.1. Algorithm M}} і Комба ({{lang-en|Comba P.G.}})<ref>{{Публікація |стаття |автор=Comba P.G. |назва=Experiments in fast multiplication of integers |видання= Technical Report G320-2158 |видавець=IBM, Cambridge Scientific Center |дата=February 1989}}</ref>. Хоча асимптотична складність їх методів така ж, як і у шкільного (<math>O(N^2)</math>), але в них зберігається менше проміжних даних, тому вони працюють значно швидше{{sfn|Василенко|2003|p=256—258}}.

==== Множення Карацуби ====
Алгоритм забезпечує найпростішу реалізацію з [[Обчислювальна складність|асимптотичною складністю]] меншою <math>O(N^2)</math>.

{{Main|Множення Карацуби}}

У найпростішому варіанті метод Карацуби ґрунтується на формулі:
:<math> (a + bx) (c + dx) = ac + ((a + b) (c + d)-ac-bd) x + bdx ^ 2. </math>
Таким чином обчислення добутку двох чисел довжиною 2 потребує лише трьох множень — <math>a \times c, \quad b \times d, \quad (a + b) \times (c + d)</math> — замість чотирьох (як у базових методах) та додаткових додавання, віднімання і зсувів.
Якщо операція множення потребує значно більшого часу ніж додаткові операції, то навіть безпосереднє застосування формули прискорює множення чисел подвійної точності.

Але основна ідея методу полягає в тому, що його можна застосовувати рекурсивно. Тоді для досить великих N час множення скорочується до межі <math>O(N^{\lg 3} \approx N^{1.585})</math>, що дає вельми відчутну перевагу{{sfn|Knuth|2008|loc=Section 4.3.3, Algorithm A}}.

Рекурсивне множення Карацуби стає ефективнішим за швидкі базові методи для чисел довжиною десь 450—620 [[біт]] (тобто, 135—185 десяткових розрядів){{sfn|Василенко|2003|p=258—259}}.

==== Алгоритм Тоома — Кука ====
Метод Карацуби узагальнено в {{нп|алгоритм Тоома — Кука|алгоритмі Тоома — Кука||Toom–Cook multiplication}}.

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

Загалом довгі числа можна поділяти на довільну кількість частин і таким чином отримати алгоритм з асимптотичною [[обчислювальна складність|обчислювальною складністю]] 
<math>O(N \times 2^{\sqrt{2 \log_2 N}} \log_2 N)</math>{{sfn|Knuth|2008|loc=Section 4.3.3, Algorithm T}}.

==== Алгоритм Шьонхаге — Штрассена ====
{{Main|Алгоритм Шьонхаге — Штрассена}}

Застосування швидкого перетворення Фур'є для множення великих чисел запропонував 1968 року [[Фолькер Штрассен|Штрассен]]. Разом із Шьоханге вони уточнили метод та опублікували алгоритм 1971 року{{sfn|Knuth|2008|loc=Section 4.3.3, Algorithm С}}.<br/>
Алгоритм множить числа x і y за модулем 2<sup>N</sup>+1: x * y mod 2<sup>N</sup>+1. Якщо потрібен повний результат множення (а не [[Модульна арифметика|залишок по модулю]]), то на N слід накласти обмеження:
: N >= bits (x) + bits (y)
Подібно до методу Карацуби, застосовується поділ вхідних чисел на 2<sup>k</sup> частин, далі числа розглядають як поліноми від однієї змінної (основи [[Система числення|системи числення]]), а для обчислення добутку поліномів застосовують [[дискретне перетворення Фур'є]]: обчислюють значення поліномів-множників у 2<sup>k</sup> точках і виконують [[швидке перетворення Фур'є]]; образ добутку обчислюють шляхом попарного множення в 2<sup>k</sup> точках (що потребує лише D=2<sup>k</sup> операцій множення замість D<sup>2</sup> у звичайному алгоритмі множення поліномів); до результату застосовують обернене перетворення Фур'є; поліном-добуток будують шляхом [[Інтерполяція|інтерполяції]] за його значеннями в 2<sup>k</sup> точках. Після обчислення многочлена-добутку в його коефіцієнтах потрібно зробити знесення старших розрядів, щоб отримати нормалізований запис числа-добутку в обраній системі числення.

Оскільки у швидкому перетворенні Фур'є (як у прямому, так і в оберненому) застосовуються лише операції додавання, віднімання і зсуву (ним замінено множення на степені двійки), то власне множення виконується лише для обчислення образу добутку.

Алгоритм потребує <math>O(N \cdot \log N \cdot\log \log N)</math> [[Бітові операції|бітових операцій]], де <math>N</math>&nbsp;— кількість двійкових цифр у добутку{{sfn|Knuth| 2008|loc= Section 4.3.3, Algorithm С}}.

На практиці алгоритм Шенхаге&nbsp;— Штрассена стає швидшим [[алгоритм Тоома — Кука|методу Тоома — Кука]] для множення чисел із кількома десятками тисяч десяткових знаків (<math>10^{10000}</math>—<math>10^{40000}</math>)<ref>{{Стаття|author=Meter van R., Itoh K. M.|title=Fast quantum modular exponentiation|url=http://www.appi.keio.ac.jp/Itoh_group/publications/PhysRevA_71_052320.pdf|видання=Physical Review A|рік=2005|том=71|accessdate=2023-06-20|archivedate=2006-02-07|archiveurl=https://web.archive.org/web/20060207005342/http://www.appi.keio.ac.jp/Itoh_group/publications/PhysRevA_71_052320.pdf}}</ref><ref>{{Стаття|author= Luis Carlos Coronado García|title=Can Schönhage multiplication speed up the RSA encryption or decryption?|url=https://api.semanticscholar.org/CorpusID:15232656|видання=University of Technology|place=Darmstadt|рік=2005}}</ref>.

==== Інші алгоритми множення ====
{{Розширити розділ}}

=== Алгоритми ділення ===
Для цілочисельного ділення багаторозрядного числа на однорозрядне застосовується стандартне [[ділення стовпчиком]]{{sfn|Василенко|2003|p=259}}.

У найпростішому випадку подібний алгоритм можна застосовувати й для ділення багаторозрядних чисел{{sfn|Василенко|2003|p=260—262}}. Втім, [[Дональд Кнут]] у своєму [[Мистецтво програмування|Мистецтві програмування]] запропонував кращий алгоритм{{sfn|Василенко|2003|p=262—269}}{{sfn|Knuth| 2008|loc= Section 4.3.1, Algorithm D}}.

Рекурсивний {{нп|алгоритм Бурнікеля — Циглера||de|Burnikel-Ziegler-Verfahren}} застосовується для ділення дуже довгих цілих чисел. У цьому алгоритмі, зокрема, виконується множення довгих чисел, тож його [[обчислювальна складність]] визначається застосованим методом множення<ref>{{cite web|url=http://cr.yp.to/bib/1998/burnikel.ps|title=Fast Recursive Division|publisher=Max-Planck-Institut für Informatik|author=Christoph Burnikel|coauthors=Joachim Ziegler|date=1998-10|accessdate=2014-06-27|lang=en|archive-date=2013-12-03|archive-url=https://web.archive.org/web/20131203183202/http://cr.yp.to/bib/1998/burnikel.ps|deadlink=no}}</ref>:
* Якщо для множення застосовуються алгоритми [[Множення Карацуби|Карацуби]] чи Тоома—Кука зі складністю <math>O(n^{\alpha})</math>, то складність ділення також буде <math>O(n^{\alpha})</math>. 
* Якщо ж для множення застосовуються асимптотично швидші алгоритми, подібні до [[Алгоритм Шьонхаге — Штрассена|алгоритму Шьонхаге — Штрассена]], зі складністю <math>O(n \cdot \log n \cdot\log \log n)</math>, то складність ділення становитиме <math>O(n \log^2 n \log \log n)</math>.

==== Приклади застосування ====
У пакеті {{нп|GNU MP|||GNU Multiple Precision Arithmetic Library}} (GMP) версії 6.2.1 застосовуються такі алгоритми ділення<ref name="gmplib_Division-algorithms"/>: 
* Найпростіший випадок — ділення багаторозрядного числа на однорозрядне (Single Limb Division).
* Базовий алгоритм ділення багатозначного числа на багатозначне (Basecase Division). Описано у [[Дональд Кнут|Дональда Кнута]] в його [[Мистецтво програмування|Мистецтві програмування]]{{sfn|Knuth|2008|loc=Section 4.3.1, Algorithm D}}.  
* Ділення методом «[[Розділяй та володарюй (інформатика)|розділяй і володарюй]]» (Divide and Conquer Division).
* Block-Wise Barrett Division
* Exact Division — обчислюється тільки частка
* Exact Remainder — обчислюється тільки залишок
* Small Quotient Division — ділення з невеликою часткою

== Джерела ==
{{reflist|refs=
<ref name="gmplib_Division-algorithms">{{cite web|title=Division Algorithms |url=https://gmplib.org/manual/Division-Algorithms#index-Division-algorithms|work=GNU MP 6.2.1|date=|accessdate=2023-06-20}}</ref>
}}

== Посилання ==
* {{Cite book|last=Knuth |first=Donald |author-link=Дональд Кнут |title=Seminumerical Algorithms |series=[[Мистецтво програмування|The Art of Computer Programming]] |volume=2 |year=2008 |edition=3rd |publisher=Addison-Wesley |isbn=978-0-201-89684-8 |ref=harv}}
* {{книга
 |автор       = Василенко О. Н.
 |назва       = Теоретико-числовые алгоритмы в криптографии
 |link        = http://www.ict.edu.ru/ft/002416/book.pdf
 |місто       = Москва
 |видавництво = МЦНМО
 |рік         = 2003
 | сторінок   = 328
 |ref         = Василенко
 |isbn        = 5-94057-103-4
}}

{{Алгоритми теорії чисел}}

[[Категорія:Довга арифметика|*]]
[[Категорія:Алгоритми]]
[[Категорія:Комп'ютерна арифметика]]
[[Категорія:Типи даних]]