х незалежної паралельної обробки;
· малоразрядность залишків, що представляють число. Зважаючи на малу кількість можливих кодових комбінацій відкривається можливість побудови табличній арифметики, завдяки чому більшість операцій, які виконуються арифметичним пристроєм, перетворюються на однотактний, виконувані простий вибіркою з таблиці.
До недоліків СОК слід віднести:
· неможливість візуального зіставлення чисел, так як зовнішня запис числа не дає уявлення про його величині;
· відсутність простих ознак виходу результатів операцій за межі діапазону;
· обмеженість дії системи сферою цілих позитивних чисел;
· отримання у всіх випадках точного результату операції, що виключає можливість безпосереднього наближеного виконання операцій, округлення результату і т. п.
Основним з достоїнств СОК є незалежність освіти розрядів числа, в силу чого кожен розряд несе інформацію про все числі, отже, виникає можливість незалежної паралельної обробки розрядів, тобто порозрядного виконання операцій. При виконанні модульних операцій: додавання, віднімання, множення, застосування апарату СОК істотно полегшує знаходження результату, особливо у випадку багаторозрядних чисел. Однак, через неможливість візуального зіставлення чисел і, насамперед, обмеженості дії системи сферою цілих позитивних чисел, ускладнюється реалізація в СОК немодульних операцій, основними з яких є переклад чисел в позиційну систему числення і операція ділення.
Навіть у цифрових обчислювальних машинах, що працюють в позиційній системі числення (наприклад, в двійковій), операція ділення стоїть осібно і час її виконання приблизно на порядок вище часу виконання більшості елементарних операцій.
В системі залишкових класів труднощі поділу посилюються тим, що ця операція в загальному випадку не є «залишкової», т. е. цифра приватного за окремим основи вже не визначається тільки цифрами діленого і дільника за цим пунктом, а вимагає в тій чи іншій формі інформації про значення діленого і дільника в цілому.
У загальному випадку ділення числа А на константу d слід розрізняти дві можливості: коли d не є підставою системи і коли d входить в систему підстав.
У першому випадку складність полягає у встановленні самого факту подільності A на d або, що те ж, у приведенні числа до найближчого до нього числу А ', що поділяється остачі на d. Саме ж поділ може проводитися поразрядно.
У другому випадку легко визначається, чи ділиться А на d, також легко визначається і найближче до А число А ', що ділиться без остачі на d, але зате визначення цифри приватного по підставі вимагає розкриття невизначеності, для чого і виникає необхідність залучення інформації про всім числі [6].
Мета дослідження: аналіз основних методів і алгоритмів ділення довільних цілих позитивних чисел в системі залишкових класів.
Завдання дослідження:
1) розглянути вищеперелічені випадки ділення в системі залишкових класів;
) вивчити метод поділу Ферма довільних чисел в системі залишкових класів;
) реалізувати і проаналізувати метод поділу Ферма довільних чисел в системі залишкових класів.
Висновки по першому розділу
У даному розділі були розглянуті способи обробки чисел, наведено методи виконання операцій над ними в позиційних і непозиційних системах числення. Так само були розглянуті основні методи переведення чисел з непозиційної системи залишкових класів у позиційну десяткову систему числення. Були відзначені переваги і недоліки непозиційної системи залишкових класів перед позиційної двійковій системою числення, в разі побудови машинної арифметики на базі даних систем. В останньому підрозділі були сформульовані мета і завдання пов'язані з труднощами виконання операції ділення довільних чисел в системі залишкових класів.
2 АНАЛІЗ РІЗНИХ ВИПАДКІВ ділення цілих ЧИСЕЛ В СИСТЕМІ ЗАЛИШКОВИХ КЛАСІВ
. 1 Формальне поділ, поділ на твір модулів системи залишкових класів, масштабування
Розглянемо найбільш простий випадок, коли ділене остачі ділиться на дільник.
Модульні операції і їх результати називаються формальними, якщо при виконанні цих операцій нехтують можливим виходом за межі діапазону. Під формальним розподілом числа А на число В будемо розуміти такий процес, при якому цифри приватного виходять як результат поразрядного ділення чисел діленого на відповідні цифри дільника.
Нехай дано два числа в системі з підставами, а саме:
,
і нехай число є частка від ділення А на В, т.е.
