Відкрити головне меню

Зміни

нема опису редагування
'<big>''Довга арифметика''',&nbsp;— в обчислювальній техніці, операції над числами, розрядність яких перевищує довжину [[машинне слово | машинного слова]] даної обчислювальної машини{{fact}}. По суті арифметика з великими числами являє собою набір алгоритмів виконання базових операцій (додавання, множення, зведення в ступінь …) над числами, реалізованими не апаратно, а програмно, використовуючи більш базові апаратні засоби роботи з числами менших порядків. Окремий випадок&nbsp;— -'' 'арифметика довільної точності'''&nbsp;— відноситься до арифметики, в якій довжина чисел обмежена лишетільки обсягомоб'ємом доступної пам'яті.
 
== Основні споживачі ==
== Сфери використання ==
 
* Комп'ютери знизької низькою розрядністюрозрядності, [[мікроконтролер]] и. Наприклад, мікроконтролери серії [[AVR]] мають 8-бітний регістр і 10-бітний [[АЦП]]&nbsp;— так що при обробці інформації з АЦП без довгої арифметики не обійтися.
* [[Криптографія]]. Зокрема довга арифметика застосовується в алгоритмах авторизації по відкритому ключу&nbsp;— таких, як RSA і Diffie-Hellman. З метою запобігання відомих атак, розміри чисел повинні перевищувати 10 <sup> 309 </sup>. Втім досить поширені мови програмування, такі як ISO C і JAVA, вміють працювати тільки з числами, заданої десятковій точності. Зокрема для C99 максимальна довжина вбудованого типу даних long long не перевищує число 10 <sup> 19 </sup>. Втім у деяких інших мовах програмування, таких як Python, є вбудовані бібліотеки роботи з великими числами.
* [[Криптографія]].
* Математичне та фінансове ПЗ, яке вимагає, щоб результат обчислення на комп'ютері збігавсязбігся здо реальнимостаннього розряду з результатом обчислення на папері. Зокрема, [[калькулятор Windows]] (починаючи з [[Windows 95]]).
* [[Число з плаваючою комою | Числа з плаваючою комою]]. У комп'ютерах числа з плаваючою комою представлені у вигляді n = [[Sgn | s]] * m * b <sup> x </sup>, де n&nbsp;— саме число, [[Sgn | s]]&nbsp;— [[Sgn | знак числа]], m&nbsp;— [[Експоненціальна запис | мантиса]], b&nbsp;— підстава [[Показова функція | показовою функції]], x&nbsp;— [[показник ступеня]]. При обробці чисел підвищеної точності, розміри мантиси можуть перевищити апаратно допустимі норми. У цих випадках для роботи з мантиси можна використовувати алгоритми роботи з великими числами.
* «Спортивні» обчислення знаменитих [[трансцендентне число|трансцендентних чисел]] ([[пі (число)|π]], [[e (число)|e]] і тощо.) з високою точністю.
* Одна з улюблених тем [[спортивне програмування | спортивного програмування]]. З поширенням стандартних бібліотек для роботи з довгими числами поступово сходить нанівець.
* Високоякісні зображення [[фрактал]]ів.
 
== Апаратні засоби для роботи з довгою арифметикою ==
 
Строго кажучи, для реалізації арифметики довільної точності від процесора потрібна лише [[непряма адресація]]; в арифметиці фіксованої точності можна обійтися навіть без неї. Тим не менше, певні функції процесора прискорюють довгу арифметику, одночасно спрощуючи її програмування.
 
* [[Прапор переносу]]. Операції «скласти/відняти з перенесенням», «[[бітовий зсув|циклічний зсув через біт перенесення]]».
* Автоінкрементні і автодекрементні операції доступу до пам'яті.
 
== Порядок слів ==
 
== Реалізація в мовах програмування ==
 
Як говорилося вище, мови програмування мають вбудовані типи даних, розмір яких, в основному, не перевищує 64 біта. <br/>
Десяткова довга арифметика була реалізована в мові програмування Алмір-65 на ЕОМ [[СВІТ # МИР-1 | МИР-1]] і в мові програмування [[Аналітик (мова програмування) | АНАЛІТИК]] на ЕОМ [[СВІТ # МИР-2 | МИР-2]]. <br/>
Для роботи з великими числами, однак, існує досить багато готових оптимізованих бібліотек для довгої арифметики.
* [[GNU Multi-Precision Library | GMP]]
* [[LibTomMath]]
 
У більшості мов високого рівня існує арифметика довжиною у два слова. Більш довгу арифметику зазвичай доводиться писати своїми силами, в міру можливості [[оптимізація (програмування)|оптимізуючи]] на [[мова асемблера|асемблері]]&nbsp;— в мовах високого рівня таких абстракцій, як «реєстрова пара» і «біт перенесення», зазвичай немає.
 
У [[Turbo Pascal]] існував шестибайтовий емулюючий [[плаваюча кома|дробовий тип]]&nbsp;— ''Real'' (у [[Delphi (мова програмування)|Delphi]] перейменований в ''Real48''). Обчислення з ним також проводилися за допомогою довгої арифметики.
 
== АпаратніНеобхідні апаратні засоби для роботи з довгою арифметикою ==
 
Строго кажучи, для реалізації арифметики довільної точності від процесора потрібнавимагається лише [[непряма адресація]]; в арифметиці фіксованоїфіксованою точності можна обійтися навіть без неї. Тим не менше, певні функції процесора прискорюють довгу арифметику, одночасно спрощуючи її програмування.
 
* [[Прапор переносу]]. Операції «скласти / відняти з перенесенням», «[[бітовий зсув | циклічний зсув через біт перенесення]]».
* АвтоінкрементніАвтоінкрементний і автодекрементніавтодекрементние операції доступу до пам'яті.
 
== Алгоритми ==
 
=== Алгоритми множення ===
 
==== Базовий ====
Являє собою алгоритм по шкільному методом «в стовпчик». Займає час O (N * M), де N, M&nbsp;— розміри перемножуваних чисел. Його алгоритм докладно описаний в книзі [1]. Секція 4.3.1.
 
==== [[Множення Карацуба]] ====
Цей алгоритм також описаний в [1]. Секція 4.3.3, частина А. Даний алгоритм являє собою найбільш просту реалізацію ідеї поділу вхідних даних, яка стала базисною для нижчеперелічених алгоритмів.
 
==== FFT Multiplication ====
Алгоритм FFT перемноження використовується для великих і дуже великих чисел. Опис даного алгоритму можна знайти в різних джерелах, зокрема Кнут секція 4.3.3 частина С, або Lipson глава 9. Далі наводиться опис алгоритму.
Нехай в перемножуванні бере участь два числа x і y за модулем 2 <sup> N </sup> +1: x * y mod 2 ^ N +1. Якщо ми хочемо отримати результат «чистого» перемноження без модуля, то на N варто накласти наступне обмеження: <br/>
: N> = bits (x) + bits (y) <br/>
Алгоритм використовує операції поділу, поточечного множення, інтерполяції та сполуки, такі ж як і в алгоритмах Карацуби. Параметр k контролює поділ вхідних даних на 2 <sup> k </sup> частин, причому Рамерії M = N / 2 <sup> k </sup> кожна. Це накладає обмеження на N. Воно має ділитися без остачі.
Всі обчислення, поточечной перемноження виконуються по модулю 2 <sup> N '</sup>, де N' = 2 * M + k + 3&nbsp;— число, округлене до твору числа 2 <sup> k </sup> на процесорний розмір елементів в бітах. Результат інтерполяції можна представити в наступному вигляді, де вибір N 'дозволяє проводити розрахунки без усікання.
<math> w [n] = \ sum_ {i + j = b * 2 ^ k + n} ^ {b = 0,1} (-1) ^ b * x [i] * y [i] </math >. <br/>
Як і в попередніх алгоритмах, для того, що б вирішити дану систему, можна використовувати наступні точки: g ^ i, де i змінюється від 0 до 2 <sup> k </sup> −1, а g = 2 <sup> (2N '/ 2 <sup> k </sup>) </sup>. g є 2 <sup> k </sup>-им коренем одиниці по модулю 2 <sup> N '</sup> +1. Ці точки гарантують, що сіcтема буде дозволена. Таким чином в Фур'є перетворенні використовуються тільки зрушення, додавання і заперечення.
 
==== Other Multiplication ====
 
=== Алгоритми ділення ===
** Single Limb Division
** Basecase Division
** Divide and Conquer Division
** Block-Wise Barrett Division
** Exact Division
** Exact Remainder
** Small Quotient Division
 
=== Більш загальні алгоритми ділення ===
 
=== Алгоритми зведення в ступінь ===
 
=== Алгоритми добування кореня ===
 
=== Алгоритми перетворення системи числення ===
 
=== Інші алгоритми ===</big>
 
{{Compu-stub}}
{{Без джерел|дата=лютий 2011}}
 
 
[[Категорія:Довга арифметика|*]]
63

редагування