В настоящее время существует необходимость проводить вычисления с очень большими целыми числами (то есть с числами, не помещающимися в разрядную сетку регистров АЛУ процессора) в таких областях как кодирование информации, криптография, физика, астрономия и т.д.

Архитектура 32-х разрядных систем позволяет обрабатывать числа в достаточно большом диапазоне (int64). Но это слишком узкий диапазон натуральных чисел для решения многих прикладных задач. Для расширения диапазона разработчики программного обеспечения предлагают разнообразные методы решения данной задачи.

1. Постановка задачи

Целью данного курсового проекта является создание модуля для работы с длинным числами. Реализация в данном модуле таких операций как сложение, вычитание, умножение и деление.

Необходимо осуществить представления длинных чисел в среде программирования Delphi. А также реализовать необходимые операции в наиболее лучшем соотношении скорости и точности.

2. Обзор литературы

Представление целых чисел

Для множества приложений предоставляемых процессором базовых типов вполне хватает. Однако встречается много задач, исходные данные которых слишком велики. Число из 1000 цифр не поместится ни в один регистр. Поэтому компьютерное представление таких чисел и операции над ними приходится реализовывать самостоятельно. При этом время выполнения внешнего алгоритма, использующего такие числа, очень сильно зависит от эффективности их реализации. Поэтому в этой главе мы будем, пожалуй, наиболее серьезно заинтересованы не просто в правильных, но возможно более эффективных алгоритмах, которые при необходимости можно реализовать на приличном уровне. Обычно, неотрицательное целое число N длины n представляется в виде N = a₀ + a₁*BASE + a₂*BASE² +… + a_n-1*BASE^n-1, где BASE - основание системы счисления, все коэффициенты 0 ? a_i < BASE.

Например, число 12345₁₀ в этой интерпретации будет иметь вид 12345₁₀ = 5 + 4*10 + 3*10² + 2*10³ + 1*10⁴ (BASE=10). Длинное число хранится в массиве, где i-й элемент соответствует коэффициенту числа при BASEⁱ. В качестве примера, рассмотрим массив для 12345₁₀: (5, 4, 3, 2, 1). Как видно, цифры хранятся в обратном порядке. Это - некая «заготовка на будущее»: дело в том, что реализации алгоритмов при этом имеют более естественный вид. Такое представление N является частным случаем многочлена n-й степени P(x) = a₀ + a₁*x + a₂*x² +… + a_n-1 x^n-1, который также удобно хранить в виде массива коэффициентов. Поэтому большинство основных операций над числами при соответствующем упрощении алгоритмов работают для произвольных многочленов (сложение, умножение и т.п.).

Основание системы счисления BASE обычно зависит от максимального размера базового типа данных на компьютере, и выбирается, исходя из следующих соображений:

1. Основание должно подходить под один из базовых типов данных

2. BASE должно быть как можно больше, чтобы уменьшить размер представления длинного числа и увеличить скорость операций с ними, но достаточно малого размера, чтобы все операции с коэффициентами использовали базовый тип данных.

3. Для удобства можно выбрать BASE как степень 10 (вывод информации, отладка).

Сложение и вычитание

Практически каждый умеет складывать длинные числа, используя для этого листок бумаги и карандаш. Перенесем имеющееся у нас понимание на язык, понимаемый компьютером. Схема для сложения очень проста: складываем цифры слева направо (цифры хранятся в обратном порядке).

Если зафиксировано переполнение (при сложении получена цифра, которая больше максимально возможной в данной системе счисления), то происходит «перенос» (carry) в следующий разряд.

Вычитание осуществляется аналогично, с той лишь разницей, что осуществляется перенос «заимствования».

Умножение

В случае с умножение, всё несколько сложнее. Тут необходимо учитывать, что может быть умножение длинного числа на короткое и длинного числа на длинное. Для начала рассмотрим умножение длинного числа на короткое.

В этом случае происходит простое умножение на него каждой цифры. При этом, конечно же, может произойти переполнение, поэтому необходимо вычислять переносы, которые при умножении могут принимать значения от 0 до BASE-1.

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

Умножение (A, B, результат C)

1. Обнулить C

2. i = 0

3. Вычислить временный результат, соответствующий умножению i-ой цифры A на число B, в процессе вычисления сразу прибавлять его к C, начиная с i-ой позиции. Если получившаяся цифра C больше BASE - сделать перенос.

4. Если A не кончилось, i++ и идти на шаг 3

Деление

Операция деление представляет собой знакомый многим еще со школы алгоритм деления в столбик. Из делимого «выносится» количество цифр, равное количеству цифр делимого, затем делитель последовательно умножается на цифры от 1 до 9, с целью найти такую цифру, при которой произведение этой цифры на делитель не будет больше «вынесенного» числа. Далее от «вынесенного» числа отнимается найденное произведение, и потом к этой разности добавляется следующая цифра делимого, после «вынесенного» числа и алгоритм повторяется до тех пор, пока «вынесенное» число не станет меньше делителя, это оставшееся число становится остатком, а найденные цифры записываются в ряд в порядке их нахождение. Таким образом, находится частное от деления и остаток.

Возведение в степень

Операция возведение в степень очень похожа на операцию умножение длинного числа на длинное, но с одной лишь разницей, умножать приходится не один раз, а столько, сколько это необходимо в поставленной задачи.

Вывод длинного числа

При выводе длинного числа в Delphi можно воспользоваться строковыми данными, путем несложных преобразований, значения чисел в массиве можно последовательно записать в строку, число за числом. А затем уже вывести всю строку целиком, содержащую наше число.

В случае если наше число было отрицательным, в начале строки просто вставляется знак «-» (минус).

3. Анализ задания

программа алгоритм число

При написании данной программы были определены некоторые требования, которым должна будет соответствовать данная программа.

Во-первых, это реализация четырех операций сложение, вычитание, умножение и деление, а также операции возведение в степень. Было принято решение реализовать операцию возведение в степень, так как такая операция необходима для полноценной функциональности калькулятора. Например когда требуется возвести большое число в большую степень, когда стандартные методы и различные калькуляторы отказываются работать в полной мере.

Во-вторых, это приведение исходных чисел, а также полученного числа к нормальному виду, то есть к виду 1,23456e N, где количество цифр после запятой определяет необходимая точность вычислений, а N - степень полученного числа.

В-третьих, это возможность, как минимум, складывать, вычитать и умножать не только целые, но и дробные числа. При написании операции деления выявился ряд трудностей, которые более подробно описаны в разделе 7.

3.2 Использование готовых разработок

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

Как уже неоднократно повторялось, программа написана на языке Delphi с использованием основных его возможностей.

4. Реализация программы

4.1 Тип данных

function CompareAPM (const a, b: TAPInt): Integer; - функция сравнивает два длинных числа, если результат меньше нуля, то первое число меньше второго, если результат больше нуля, то первое число больше второго, если результат равен нулю, то числа равны. Входные параметры - два длинных числа, выходной параметр - число типа Integer.

procedure CopyAPM (Source, Destination: TAPInt); - копирует длинное число из одной переменной в другую. Входные параметры - ячейка памяти откуда копируется число, и ячейка памяти куда копируется число.

procedure AddAPM (const a, b: TAPInt; var c: TAPInt); - операция сложение. Входные параметры - три длинных числа, третье число является результатом.

procedure SubAPM (const a, b: TAPInt; var c: TAPInt); - операция вычитания. Входные параметры - три длинных числа, третье число является результатом.

procedure MulAPM (const a, b: TAPInt; var c: TAPInt); - операция умножения. Входные параметры - три длинных числа, третье число является результатом.

procedure PowAPM (const a, b: TAPInt; var c: TAPInt); - операция возведение в степень, длинное число возводится в целую степень не превышающую 9999 (более подробно в главе 5: Описание программы для пользователя), при этом результатом является также длинное число.

procedure DivAPM (const a, b: TAPInt; var c: TAPInt; var d:TAPInt); - операция деление, длинное число делится на другое длинной число, при этом результатом является длинное число, а также остаток от деления (тоже длинное число).

procedure DivByWord (const a: TAPInt; const b: Word; var c: TAPInt; var d: Word); - операция деления, при которой длинное число делится на короткое, при этом получается длинное число и остаток (короткое число), процедура реализована для ускорения программы.

procedure MulByWord (const a: TAPInt; const b: Word; var c: TAPInt); - операция умножения длинного числа на короткое, результатом является длинное число, процедура реализована для ускорения программы.

function OddAPM (a: TAPInt): Boolean; - вспомогательная функция, результатом является True если первый элемент массива равен 1.

Блок-схема работы программы приведена в приложении А. В приложениях Б и В приведены пошаговые алгоритмы процедур сложения и деления.

5. Описание программы для пользователя

При запуске программы пользователь увидит окно с несколькими окнами для ввода, переключателями, а также кнопки для действий.

Общий вид программы

Пример работы программы

После ввода данных и нажатия на кнопку «Go!», а также после нажатий на кнопки «Преобразовать» пользователь увидит окно, которое изображено на рисунке.

При вводе данных и подсчете результатов важно помнить, что

1. Программа понимает только разделительный знак «.» (точка).

2. При выполнении операции деление необходимо вводить только целые, натуральные числа.

3. При выполнении операции возведение в степень в окно, куда вводится степень («Число №2»), нужно вводить только целые, натуральные числа, и только до числа 9999, так как при введении большей степени программа просто не будет его считать. То же самое произойдет, если ввести дробное число, либо отрицательную степень.

Заключение

В результате, был написан модуль для работы с длинными числами. При создании данного модуля был ряд трудностей: проблемы реализации процедур сложения, умножения и деления. При написании операции сложения проблемой было написание большого количества условий для сложения дробных чисел с одинаковым количеством цифр после запятой, с разным количеством цифр после запятой, сложение целого и дробного числа, а также вычет из целого числа дробное, при написании операции вычитание. При написании операции умножение стандартными средствами Delphi подсчет происходил слишком долго, выходом из данной ситуации стал встроенный в среду Delphi, assembler. При написании операции деление проблемой стало, то, что в задании не была указана точность для таких вычислений. В теории при написании программы возможно деление до бесконечного знака после запятой (ограничением является лишь оперативная память компьютера), но при таком условии этот результат никогда не будет посчитан. Но при дальнейшем развитии программы целесообразно добавить эту функцию, ограничив её условием необходимой точности вычисления. Также при дальнейшем развитии программы можно добавить такие операции, как извлечение квадратного корня из числа, факториал, возведение в дробную, отрицательную степень, логарифм и др.

В целом программа оправдывает своё назначение и выполняет операции с длинными числами, что и являлось заданием данной курсовой работы.

Список используемых источников