Зазвичай в обчислювальних машинах для поділу широко використовується інший метод, називаний методом виконання ділення без відновлення залишку. Цей метод заснований на прямому копіюванні дій при ручному діленні («в стовпчик»). При реалізації цього методу, якщо результат віднімання вийшов негативний, частковий залишок не відновлюється шляхом додавання дільника, а на наступному кроці ділення замість віднімання діленого проводиться його поповнення до часткового залишку. Якщо результат при цьому залишився негативним, то в чергову цифру приватного записується нуль і на наступному кроці також виконується складання. Якщо результат складання вийшов позитивним, то в черговий розряд приватного записується одиниця і на наступному кроці проводиться віднімання. Часткові залишки при діленні без відновлення залишку виходять такими ж, як і залишки після зсуву відновленого залишку при діленні з відновленням залишку.
Розподіл без відновлення залишку завжди вимагає для отримання однієї цифри приватного тільки двох тактів: такту додавання або віднімання і такту зсуву. Тим самим швидкість обчислення цим методом виявляється вище ніж в методі поділу з відновленням залишку.
Виходячи з розглянутих методів ділення в обчислювальних машинах, найбільш швидкісним і простим методом є метод поділу без відновлення залишку, так як при використанні даного методу для отримання однієї цифри приватного необхідно виконати всього лише два такту, в той час як у методі з відновленням часткового залишку для отримання одной цифри приватного потрібно три такту.
Позиційні системи числення, в яких представляється і обробляється інформація в сучасних обчислювальних машинах, мають істотним недоліком - наявністю межразрядних зв'язків, які накладають свій відбиток на способи реалізації арифметичних операцій, ускладнюють апаратуру і обмежують швидкодію. Особливо цей недолік проявляється при роботі з багаторозрядних числами. Пошуки нових шляхів підвищення продуктивності обчислювальних пристроїв привели дослідників до об'єктивного висновку, що в цьому напрямку позиційна система числення свої можливості вичерпала. Тому для того щоб значно підвищити продуктивність обчислювальних пристроїв необхідне застосування систем числення позбавлених подібного недоліку [4].
1.2 Представлення і обробка цілих чисел у системі залишкових класів
Основний теоретико-числовий базою системи залишкових класів (СОК) є теорія порівнянь. СОК дає нестандартне уявлення для чисел і використовується для підвищення ефективності операцій над кодами в залишках. У даній системі числа представляються своїми залишками від ділення на обрану систему підстав і всі раціональні операції можуть виконуватися паралельно над цифрами кожного розряду окремо.
Теорія чисел стосовно наданню й обробці інформації модулярную кодами починається з елементарної ідеї поділу.
Нехай А і р - дві довільних цілих числа, причому р - позитивне число. Тоді в результаті ділення числа А на число р виходять приватне і залишок. Подільність А на р задовольняє рівності
(1.2)
і нерівності
(1.3)
де l носить назву приватного, а - залишку.
Згідно (1.2) величина називається також найменшим ненегативним вирахуванням цілого числа А по і позначається символом.
Якщо залишок, то р і l - подільники числа А; тоді говорять, що р ділить А і пишуть. Отже,
.
Без урахування негативних дільників можна сказати, що кожне ціле число має принаймні два дільника:
(1.4)
Це не виключає існування інших дільників.
Якщо А не має дільників, відмінних від 1 і А, то А - просте число. Число 1 не рахується простим, а 2 є єдиним парних простим числом. Інші цілі числа, що мають кілька дільників, називаються складовими. Наприклад, першими в натуральному ряду складовими числами є 4, 6, 8, 9, ....
Припустимо, що А - складене число, а р - його дільник. Тоді
(1.5)
де l - інший дільник.
Отже, р і l або є простими числами, або хоча б одне з них розкладається на множники. У другому випадку, продовжуючи процес розкладання на множники, можна отримати уявлення А у вигляді добутку лише простих чисел.
Приклад.,.
Кожне складене число може бути представлено у вигляді твору ступенів простих чисел c позитивними цілими:
(1.6)
Основна теорема арифметики стверджує, що це подання єдино.
Найбільше позитивне ціле, подумки ділить цілі числа А і р, називається найбільшим спільним дільником (НОД) і позначається
Якщо, то А і р не мають спільних дільників, відмінних від 1, і називаються взаємно-простими.
Най...
