ня відрахувань і з кожного модуля незалежно один від одного. Якщо
вибрано як добуток великого числа малих модулів, то навіть дії з вельми великими числами можуть бути виконані в такій системі з великим числом малих за величиною модулів. P - обсяг діапазону представимо чисел. Як і в узагальненій позиційній системі, діапазон представимо чисел росте як твір підстав, а розрядність чисел A росте як сума розрядностей тих же підстав. У цій системі числення шляхом вибору досить великих взаємно простих множників можна представити які завгодно великі числа. Вибір взаємно простих множників може бути здійснений шляхом вибору чисел в натуральному ряду. Послідовність простих чисел необмежена.
Для того, щоб з безлічі натуральних чисел виділити прості, можна скористатися способом решета Ератосфена, суть якого полягає в наступному: якщо в безлічі натуральних чисел 2, 3, 4, ..., N закреслити числа, кратні перший r простим числам- 2, 3, ..., р, то перше (найменше) незачеркнутое число буде простим.
Якщо викреслити всі числа, кратні всім простим числам до, тобто вибрати r так, що, то що залишилися числа будуть збігатися з безліччю всіх простих чисел р таких, що.
Алгоритм знаходження простих чисел в множині натуральних чисел 2, 3, 4, 5, 6, ..., N наступний. Перше число 2 - просте. Викреслюються всі числа, кратні 2; перший невикреслене число 3 - просте. Викреслюються всі числа, кратні 3; перший невикреслене число 5 - просте і т. д. Продовжуємо цей процес, поки не викреслимо всі числа, кратні знайденим простим числам 2, 3, ..., р, де, а наступне просте. Всі залишилися невикреслених числа дадуть нам безліч простих чисел, що лежать між і (включаючи N, якщо воно просте), а разом з раніше знайденими простими 2, 3, ..., р будуть отримані всі прості числа, що не перевершують N.
Принципова можливість застосування СОК в обчислювальних алгоритмах обумовлюється наявністю певного ізоморфізму між математичними операціями над цілими числами і відповідними операціями над системою цілих невід'ємних залишків по окремих модулів. Причому додавання, множення, зведення в цілу позитивну ступінь будь-яких цілих позитивних чисел абсолютно ідентичні відповідним операціями, виконуваним над системою залишків.
Розглянемо правила виконання операцій додавання і множення в системі залишкових класів у випадку, якщо обидва числа і результат операції знаходяться в діапазоні. Нехай операнди A і B представлені відповідно залишками і з підстав прі. Результати операцій додавання і множення і представлені відповідно залишками і з тих самих підстав, т. Е.
;
;
;
.
і при цьому мають місце співвідношення:
,,,
Стверджується, що
.
при цьому в якості цифри результату береться відповідно
(1.16)
(1.17)
Ці операції відносять до числа модульних операцій, вони можуть бути распараллелен з кожного модуля. Таким чином, одне з достоїнств СОК - це незалежність освіти розрядів числа, в силу чого кожен розряд несе інформацію про все числі, а отже, виникає можливість незалежної паралельної обробки розрядів, тобто порозрядного виконання операцій. При виконанні додавання, віднімання, множення кожна цифра залежить лише від відповідних цифр операндів.
Розглянемо приклади, що ілюструють наведені вище правила виконання операцій додавання і множення.
Приклад. Нехай підставами системи є
. Діапазон системи визначиться як. Складемо число з числом.
За вибраними підставах числа A і B в системі залишкових класів будуть представлені як
Відповідно до (2.20) отримаємо. Легко перевіряється, що число є і дорівнює сумі операндів.
Приклад. Помножимо число на число (підстави колишні).
В системі залишкових класів числа і будуть представлені як
.
Відповідно до (2.21) отримаємо. Легко перевіряється, що число є і дорівнює добутку операндів [11].
1.3 Методи переведення чисел із системи залишкових класів у позиційну систему числення
Операція переведення чисел з СОК в ПСС відноситься до числа немодульних операцій, причому можна вважати її однією з основних, так як визначення величини числа необхідно і для ряду інших немодульних операцій. Тому ефективність визначення величини числа визначає ефективність і цих операцій.
Розглянемо основні методи переведення чисел з СОК в ПСС. Система залишкових класів володіє однією особливістю, яку можна віднести до недоліків цієї системи: не можна візуально визначити величину числа, представленого в СОК, а отже скрутно і виконання таких операцій, як порівняння чисел, визначення знака числа. Один із шляхів вирішення цієї проблеми полягає в перетворенні чисел з СОК в позиційну систему числення. Оцінимо існуючі способи ...
