- число модулів системи. Може бути запропонована деяка модифікація розглянутого алгоритму в тому плані, що операція ділення замінюється операцією множення. Для цього попередньо обчислюється констант, які задовольняють умові
,. (1.23)
Ці константи можна, наприклад, отримати з розширеного алгоритму Евкліда.
Тут слід зауважити той факт, що константи повністю визначаються вибраною системою підстав, тому можуть бути обчислені заздалегідь і зберігатися в деякій таблиці.
Якщо константи обчислені, то обчислення чисел ОПСС за алгоритмом (1.22) може бути переписано у вигляді:
,
,
,
...
. (1.24)
Константи прийнято також записувати у вигляді і називати зворотними елементами по множенню для чисел по модулю.
Приклад. Нехай дана система підстав,, обсяг діапазону. Перевести число в позиційну систему. Переклад в ОПСС зручно здійснювати, записуючи проміжні обчислення в таблицю.
Таблиця 1.1
ДействіяМодуліЦіфри ОПСA138715 - 11111 027614 671022 11037 - 1 111 0926 674 21424 - 222 01222 310175 - 1717 031 34 22
Згідно (1.21):
Перевага розглянутого методу перед методом ортогональних базисів полягає в тому, що всі обчислення виконуються в модулярной арифметиці, причому в окремих каналах, відповідних модулям, правда на жаль не паралельно.
1.3.3 Інтервальний метод перекладу
Досить ефективними методами переведення чисел з СОК в ПСС є інтервальні методи, засновані на інтервальних характеристиках чисел. Одна з таких характеристик - номер інтервалу.
Нехай СОК задана системою підстав, з об'ємом діапазону. Виберемо дробірующій модуль і проведемо дроблення заданого діапазону на інтервали шляхом ділення P на модуль. Тоді кількість інтервалів, а довжина інтервалу визначається величиною модуля. У результаті величину будь-якого числа А, заданого в СОК за обраними підстав можна визначити за номером інтервалу:
, (1.25)
в якому знаходиться число А і по цифрі числа Ав СОК по модулю, т.е.
. (1.26)
Так як, то по теоремі Ейлера:
(1.27)
де - функція Ейлера. Причому якщо - просте число, то. Підставляючи (1.27) в (1.20), враховуючи (1.18) і (1.19) число А можна записати у вигляді:
(1.28)
Для визначення номера інтервалу підставимо (1.28) в (1.25):
(1.29)
Враховуючи, що, перепишемо (1.29) у вигляді:
(1.30)
Так як є дільником чисел,, P, то
,
де, і - постійні коефіцієнти, певні системою підстав.
Таким чином,
(1.31)
Підставляючи (1.31) в (1.26), одержимо позиційне представлення числа А:
(1.32)
Приклад. Нехай дана система підстав,, обсяг діапазону. Перевести число в позиційну систему.
Виберемо як дробірующего підстави, згідно (1.31)
тоді.
Обчислюємо значення функції Ейлера для кожного з модулів
, тоді
.
В якості дробірующего модуля доцільніше вибирати найбільший з модулів системи. У цьому випадку модульні операції виконуються при меншій величині модуля, що веде до менших тимчасовим і апаратурним витратам.
Проведений порівняльний аналіз методів переведення чисел з СОК в ПСС показав деякі переваги методу переказу за допомогою ОПСС. Це пояснюється тим, що в методі ортогональних базисів дії додавання і множення виконуються в ПСС, причому величини ортогональних базисів досить великі. У разі інтервальних методів знову доводиться виконувати операції додавання, множення, зведення в ступінь в позиційній системі, причому можуть виходити досить великі величини при зведенні в ступінь. Правда, за рахунок обчислень по модулю їх можна відразу зменшити. Позитивне ж властивість інтервальних методів у можливості конвеєрної обробки. При перекладі ж за допомогою ОПСС всі обчислення виконуються в модулярной арифметиці в окремих каналах, відповідних кожному модулю СОК, але, на жаль, не паралельно [5].
1.4 Постановка мети і завдань дослідження
Створення арифметики в системі залишкових класів висуває свої специфічні проблеми, від успішного вирішення яких залежить її широке використання.
До достоїнств системи залишкових класів слід віднести:
· незалежність освіти розрядів числа, в силу чого кожен розряд несе інформацію про все вихідному числі, а не про проміжному числі, одержуваних у результаті утворення більш молодших розрядів (як це має місце в позиційній системі). Звідси випливає незалежність розрядів числа один від одного і можливість ї...
