1. Введение

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

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

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

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

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

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

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

1. Аналоги разработки данной программы

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

C, C++ — библиотека libgmp

Common Lisp — не ограничивает разрядность целых чисел

Erlang — встроенный численный тип (integer())

Go — типы Int и Rat из библиотеки big.

Haskell — встроенный тип Integer

Java — класс java.math.BigInteger

OCaml — библиотека num

Pascal/Delphi — библиотека MPArith

Perl — модули bignum и bigrat

PHP — модуль BCMath

Python — встроенный тип long

Ruby — тип Bignum

Scala — класс BigInt

Scheme — начиная с R5RS рекомендация, с R6RS — требование о неограниченности разрядности чисел

Языки .NET — класс System.Numerics.BigInteger (появился в .NET Framework 4.0)

2. Существующие алгоритмы

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

Для множества приложений предоставляемых процессором базовых типов вполне хватает. Однако встречается много задач, исходные данные которых слишком велики. Число из 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 (вывод информации, отладка).