ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

ПРИЛОЖЕНИЕ ДЛЯ ВЫПОЛНЕНИЯ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ НАД ДЛИННЫМИ ЧИСЛАМИ

БГУИР КР 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

Министерство образования Республики Беларусь

КАЛЕНДАРНЫЙ ПЛАН

ВВЕДЕНИЕ

Некоторые алгоритмы прикладной математики используют в вычислениях очень большие числа, причём точность в таких алгоритмах важна. То есть, нельзя положить, что число 1498687325427364823≈1.5*10¹⁸. При программировании таких алгоритмов на компьютере возникает проблема хранения и обработки таких чисел, так как стандартные типы данных могут не вместить эти значения. Для решения этой проблемы разработана так называемая длинная арифметика.

Другой задачей, которую можно решить с помощью длинной арифметики является выполнение алгоритмов с очень высокой точностью. Используя длинную арифметику с плавающей точкой можно добиться практически любого заданного уровня значимости.

Важным свойством любого приложения, реализующего работу с длинными числами, будет являться его быстродействие. В данной курсовой работе при написании алгоритмов будет использоваться язык 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]

После анализа возможных реализаций хранения длинных чисел была выбрана «классическая» реализация с хранением цифр числа в массиве. В таком виде легко реализуются все необходимые алгоритмы арифметических действий, а также ввода и вывода числа.