tify"> · обмеженість дії системи сферою цілих позитивних чисел;
· отримання у всіх випадках точного результату операції, що виключає можливість безпосереднього наближеного виконання операцій, округлення результату і т. п.
1.2 Вибір оптимальних підстав СОК
Нехай діапазон представлення чисел в СОК дорівнює P=p 1 p 2 ... pn. Оскільки бажано, щоб P було якомога більшим, найпростіше прийняти p 1 найбільшим непарним числом, відповідним машинному слову, як p 2 прийняти найбільшу непарне число < p 1, взаємно просте з p 1, а в якості p 3 - найбільше непарне число < p 2, взаємно просте як з p 1, так і з p 2, і т.д., поки не набереться стільки pj, скільки буде достатньо для утворення потрібного P [1].
При роботі на довічних комп'ютерах іноді бажано вибирати модулі pj іншим чином:
p j=2 ej - 1. (1.11)
Іншими словами, значення кожного модуля на одиницю менше черговий ступеня двійки. Такий вибір значення модуля pj часто спрощує виконання основних арифметичних операцій, тому що виконувати обчислення з числами, представленими за модулем 2 ej - 1, дещо простіше, ніж з числами, представленими у зворотному коді. Після того, як значення модулів обрані таким чином корисно дещо послабити умову 0? a i < pj і зажадати тільки, щоб
0? a i < 2 ej, (1.12)
a i? N (mod 2 ej - 1), (1.13)=(а 1, а 2, ..., а n). (1.14)
Таким чином, значення pj=2 ej - 1 приймається як оптимального, оскільки це означає, що pj може бути будь-яким ej - бітовим двійковим числом [1].
Для роботи з модулями виду 2 ej - 1 необхідно знати, за яких умов число 2 e - 1 є взаємно простим з числом 2 f - 1. На щастя для цього існує дуже просте правило
gcd (2 e - 1, 2 f - 1)=2 gcd (e, f) - 1. (1.15)
Формула (2.15) затверджує зокрема, що 2 e - 1 і 2 f - 1 взаємно прості тоді і тільки тоді, коли взаємно прості e і f. Формула (1.15) випливає з алгоритму Евкліда і тотожності
(2 e - 1) (mod (2 f - 1))=2 e (mod f) - 1. (1.16)
Тому на комп'ютері з довжиною слова 2 32 можна вибрати p 1=29 лютого - 1, p 2=25 лютого - 1, p 3=23 лютого - 1, p 4=19 лютого - 1, p 5=17 лютого - 1, p 6=2 13 - 1, p 7=11 лютого - 1, p 8=7 лютого - 1 що забезпечує ефективність додавання, віднімання та множення цілих чисел в інтервалі аж до p 1 p 2 p 3 p 4 p 5 p 6 p 7 p 8 < 2144. У даному курсовому проекті для подання 64-х бітних чисел використовується наступна система модулів: (13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61) - всі вони взаємно прості один з одним, їх добуток дорівнює 50 774 191 064 678 342 417> 18 446 744 073 709 551 616. Кожен з модулів не перевищує 6 біт, тобто операції додавання і множення будуть проводитися над 6-бітними числами.
1.3 Модулярні обчислення
Основною перевагою СОК є те, що арифметичні операції проводяться в ній незалежно по кожному з модулів, отже, вони можуть виконуватися паралельно по L обчислювальним каналами:
Узагальнена структура пристроїв цифрової обробки сигналів в модулярної арифметиці представлена ??на малюнку 1.1. Число X на ...
