Теоретические сведения
ПРИЛОЖЕНИЕ ДЛЯ ВЫПОЛНЕНИЯ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ НАД ДЛИННЫМИ ЧИСЛАМИ
БГУИР КР 1-31 03 04
Студент гр. 952002 Д. Ю. Скобелев
Руководитель М.В. Михневич
Минск 2012
СОДЕРЖАНИЕ
ТЕХНИЧЕСКОЕ ЗАДАНИЕ. 3
ВВЕДЕНИЕ. 5
1 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ.. 6
2 ОБЗОР СУЩЕСТУЮЩИХ БИБЛИОТЕК ДЛИННОЙ АРИФМЕТИКИ.. 9
3 ХРАНЕНИЕ ЧИСЛА В ПАМЯТИ.. 13
4 ПРОЕКТИРОВАНИЕ АЛГОРИТМОВ.. 14
4.1 Сравнение. 14
4.2 Сложение. 14
4.3 Вычитание. 15
4.4 Умножение. 15
4.5 Деление. 16
4.6 Служебные алгоритмы.. 17
5 ВЫБОР ЯЗЫКА РЕАЛИЗАЦИИ.. 18
6 ИНТЕРФЕЙС ПРОГРАММЫ.. 19
ЗАКЛЮЧЕНИЕ. 21
ПРИЛОЖЕНИЕ А.. 22
Руководство пользователя. 22
Диаграммы.. 23
Список использованных материалов. 24
Министерство образования Республики Беларусь
| Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ | ||||||||||||||||||
| Факультет | КСиС | Кафедра | Информатики | |||||||||||||||
| Специальность | 1-31 03 04 | Специализация | ||||||||||||||||
| УТВЕРЖДАЮ | ||||||||||||||||||
| Зав.кафедрой | ||||||||||||||||||
| « | » | г. | ||||||||||||||||
| ТЕХНИЧЕСКОЕ ЗАДАНИЕ | ||||||||||||||||||
| по курсовой работе студента | ||||||||||||||||||
| Скобелева Дмитрия Юрьевича | ||||||||||||||||||
| 1 Тема проекта (работы): | Приложение для выполнения арифметических | |||||||||||||||||
| операций над целыми числами | ||||||||||||||||||
| утверждена приказом по университету от | « | » | 20 г. | № | ||||||||||||||
| 2 Срок сдачи студентом законченной работы | ||||||||||||||||||
| 3 Исходные данные к проекту: | ||||||||||||||||||
| 4 Содержание пояснительной записки (перечень подлежащих разработке вопросов): | ||||||||||||||||||
| Введение | ||||||||||||||||||
| 1 Теоретические сведения. | ||||||||||||||||||
| 2 Обзор существующих библиотек длинной арифметики. | ||||||||||||||||||
| 3 Хранение числа в памяти | ||||||||||||||||||
| 4 Проектирование алгоритмов | ||||||||||||||||||
| 5 Выбор языка реализации | ||||||||||||||||||
| 6 Интерфейс программы | ||||||||||||||||||
| Заключение | ||||||||||||||||||
| Задание выдал | М. В. Михневич |
КАЛЕНДАРНЫЙ ПЛАН
| Наименование этапов дипломного проекта (работы) | Объём этапа, % | Срок выполнения этапа | Примечание |
| Анализ и выбор способа хранения числа в памяти | 20.02 – 26.02 | ||
| Написание и отладка программных алгоритмов | 27.02 – 14.04 | ||
| Разработка графического интерфейса | 15.04 – 24.04 | ||
| Тестирование программы | 25.04 – 01.05 | ||
| Оформление графического материала и поясни- тельной записки | 02.05 – 25.05 |
| Дата выдачи задания | 20.02.2012 | Руководитель | М.В. Михневич | |||
| Задание принял к исполнению | Д.Ю. Скобелев | |||||
ВВЕДЕНИЕ
Некоторые алгоритмы прикладной математики используют в вычислениях очень большие числа, причём точность в таких алгоритмах важна. То есть, нельзя положить, что число 1498687325427364823≈1.5*1018. При программировании таких алгоритмов на компьютере возникает проблема хранения и обработки таких чисел, так как стандартные типы данных могут не вместить эти значения. Для решения этой проблемы разработана так называемая длинная арифметика.
Другой задачей, которую можно решить с помощью длинной арифметики является выполнение алгоритмов с очень высокой точностью. Используя длинную арифметику с плавающей точкой можно добиться практически любого заданного уровня значимости.
Важным свойством любого приложения, реализующего работу с длинными числами, будет являться его быстродействие. В данной курсовой работе при написании алгоритмов будет использоваться язык assembler вставками в код на языке C. Ассемблерный код очень быстр, и считается, что самую эффективную программу можно написать только на ассемблере. Но это очень трудоёмкий и требующий большого внимания и практического опыта процесс. Поэтому реально на ассемблере пишутся критичные ко времени выполнения или расходованию памяти программы. Впоследствии он оформляются в виде подпрограмм и совмещаются с кодом на языке высокого уровня.[2]
ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Длинная арифметика - это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных. Необходимость реализации таких средств может возникать при программировании компьютеров низкой разрядности, микроконтроллеров; также при решении задач криптографии и математических вычислений повышенной точности.
Процесс работы с длинными числами напрямую зависит от того, как они будут размещены в памяти. Основная идея состоит в том, чтобы записать число в памяти в виде последовательности его цифр. Цифры можно хранить в массивах, в связных списках, в строках или в других специально написанных структурах данных.
Однако, это не единственный возможный способ хранения длинных чисел. Возможным вариантом является представление в факторизованном виде. Здесь идея заключается в том, чтобы хранить не само число, а его факторизацию, т.е. степени каждого входящего в него простого. Этот метод также весьма прост для реализации, и в нём очень легко производить операции умножения и деления, однако невозможно произвести сложение или вычитание. С другой стороны, этот метод значительно экономит память в сравнении с "классическим" поциферным подходом, и позволяет производить умножение и деление значительно (асимптотически) быстрее.
Этот метод часто применяется, когда необходимо производить деление по непростому модулю: тогда достаточно хранить число в виде степеней по простым делителям этого модуля, и ещё одного числа — остатка по этому же модулю. [3]
Ещё один вариант: длинная арифметика по системе простых модулей. Суть в том, что выбирается некоторая система модулей (обычно небольших, помещающихся в стандартные типы данных), и число хранится в виде вектора из остатков от его деления на каждый из этих модулей.
Этого достаточно, чтобы однозначно хранить любое число в диапазоне от 0 до произведения этих модулей минус один. При этом имеется алгоритм, который позволяет произвести это восстановление из модульного вида в обычную, "классическую", форму числа. [3]
Таким образом, этот метод позволяет экономить память по сравнению с "классической" длинной арифметикой (хотя в некоторых случаях не столь радикально, как метод факторизации). Кроме того, в модульном виде можно очень быстро производить сложения, вычитания и умножения, — все за асимптотически одинаковое время, пропорциональное количеству модулей системы. [3]
Однако всё это даётся ценой весьма трудоёмкого перевода числа из этого модульного вида в обычный вид, для чего, помимо немалых временных затрат, потребуется также реализация "классической" длинной арифметики с умножением. Помимо этого, производить деление чисел в таком представлении по системе простых модулей не представляется возможным. [3]
В курсовой работе реализована возможность работать не только с целыми, но и с дробными числами. Представить дробной длинное число тоже можно по-разному. Например, есть решение, когда число представляется в виде несократимой дроби a/b, где a и b - целые числа. Тогда все операции над дробными числами нетрудно свести к операциям над числителями и знаменателями этих дробей. Но обычно при этом для хранения числителя и знаменателя приходится также использовать длинную арифметику, хотя иногда оказывается достаточно встроенного 64-битного числового типа. [3]
Другой вариант - выделение позиции плавающей точки в отдельный тип. Иногда в задаче требуется производить расчёты с очень большими либо очень маленькими числами, но при этом не допускать их переполнения. Встроенный 10-байтовый тип double, как известно, допускает значения экспоненты в диапазоне [-308, 308], чего иногда может оказаться недостаточно.
Приём очень простой - вводится ещё одна целочисленная переменная, отвечающая за экспоненту, а после выполнения каждой операции дробное число нормализуется, т.е. возвращается в отрезок [0.1, 1) путём увеличения или уменьшения экспоненты.
При перемножении или делении двух таких чисел надо соответственно сложить либо вычесть их экспоненты. При сложении или вычитании перед выполнением этой операции числа следует привести к одной экспоненте, для чего одно из них умножается на 10 в степени разности экспонент. Наконец, не обязательно выбирать 10 в качестве основания экспоненты. Исходя из устройства встроенных типов с плавающей точкой, самым выгодным представляется принимать основание равным 2. [3]
После анализа возможных реализаций хранения длинных чисел была выбрана «классическая» реализация с хранением цифр числа в массиве. В таком виде легко реализуются все необходимые алгоритмы арифметических действий, а также ввода и вывода числа.