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