ЗМІСТ
ВСТУП
АНАЛІТИЧНИЙ ОГЛЯД МЕТОД І АЛГОРИТМІВ ОБРОБКИ ЧИСЕЛ
.1 Арифметичні операції над числами, представленими в позиційних системах числення
.2 Представлення і обробка цілих чисел у системі залишкових класів
.3 Методи переведення чисел із системи залишкових класів у позиційну систему числення
.3.1 Метод ортогональних базисів
.3.2 Переклад в узагальнену позиційну систему числення
.3.3 Інтервальний метод перекладу
.4 Постановка мети і завдань дослідження
Висновки по першому розділу
АНАЛІЗ РІЗНИХ ВИПАДКІВ ділення цілих ЧИСЕЛ В СИСТЕМІ ЗАЛИШКОВИХ КЛАСІВ
.1 Формальне поділ, поділ на твір модулів системи залишкових класів, масштабування
.2 Розподіл довільних чисел в системі залишкових класів на основі методу Ферма
.3 Програмна реалізація та аналіз методу Ферма в системі комп'ютерної алгебри Maple
Висновки по другому розділу
ВИСНОВОК
СПИСОК ЛІТЕРАТУРИ
ДОДАТОК
ВСТУП
У сучасних цифрових обчислювальних машинах, що працюють в позиційній системі числення, операція ділення займає особливе місце, і час її виконання приблизно на порядок вище часу виконання більшості елементарних операцій. Час виконання операції ділення істотно зростає у випадку багаторозрядних чисел.
В системі залишкових класів час, що витрачається на виконання операцій, не залежить від розрядності числа, але труднощі поділу посилюються тим, що ця операція в загальному випадку не є модульною, тобто цифра приватного за окремим основи вже не визначається тільки цифрами діленого і дільника за цим пунктом, а вимагає в тій чи іншій формі інформації про значення діленого і дільника в цілому.
Мета роботи: підвищення швидкості виконання операції ділення в системі залишкових класів.
Об'єкт дослідження: модулярні обчислювальні структури.
Предмет дослідження: методи й алгоритми виконання операції ділення в системі залишкових класів.
Основні завдання:
· аналіз методів і алгоритмів обробки чисел в позиційних системах числення;
· огляд подання та обробки чисел в системі залишкових класів;
· розвиток методів поділу в системі залишкових класів;
· моделювання та аналіз методу ділення Ферма в системі залишкових класів.
Поставлені в роботі завдання вирішувалися у двох розділах випускної кваліфікаційної роботи. У першому розділі досліджувалися основні методи і алгоритми обробки чисел. Були розглянуті способи виконання арифметичних операцій в різних системах числення. У другому розділі детально була розглянута операція ділення, представлено розроблене програмне забезпечення для реалізації поділу довільних чисел методом Ферма, наведені результати тестування розробленої програми.
1 АНАЛІТИЧНИЙ ОГЛЯД МЕТОД І АЛГОРИТМІВ ОБРОБКИ ЧИСЕЛ
Системою числення називається сукупність прийомів найменування і запису чисел. У будь-якій системі числення для подання чисел вибираються деякі символи (їх називають цифрами), а інші числа виходять в результаті яких-небудь операцій над цифрами даної системи числення. Від особливостей системи числення залежать наочність представлення числа за допомогою цифр і складність виконання арифметичних операцій.
. 1 Арифметичні операції над числами, представленими в позиційних системах числення
Система називається позиційною, якщо значення кожної цифри (її вага) змінюється залежно від її положення (позиції) в послідовності цифр, що зображують число. Число одиниць якого-небудь розряду, що об'єднуються в одиницю більш старшого розряду, називають підставою позиційної системи числення. Якщо число таких одиниць одно, то система числення називається p-ічной. Підстава системи числення збігається з кількістю цифр, використовуваних для запису чисел в цій системі числення. Запис довільного числа в p-ічной позиційній системі числення грунтується на уявленні цього числа у вигляді многочлена
(1.1)
Позиційна система числення має низку важливих властивостей:
1) Підстава системи числення в ній самій завжди записується як; наприклад, в двійковій системі числення означає число.
) Для запису числа в p-ічной системі числення потрібно цифр, де - ціла частина числа.
) Порівняння чисел проводиться поразрядно зліва направо.
В даний час для більшості обчислювальних машин основною системою числення є позиційна двійкова система числення.
Існують два основні формати подання чисел у пам'яті комп'ютера. Один з ни...