Хранение числа в памяти

При реализации на практике более универсальным способом оказалось хранения указателя на массив цифр и длины числа в отдельной ячейке, чем массива фиксированного размера. Такой подход даёт возможность не ограничивать длину числа какой-то константой, пусть даже и очень большой. Известно, что учёные оценивают количество атомов во Вселенной величиной, приблизительно равной 10⁸³, то есть теоретически пользователь вряд ли будет оперировать более крупными числами. Однако, чтобы не ограничивать возможности программы, был реализован подход, при котором любое число будет размещено в памяти[1].

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

В итоге в памяти длинное число представляется следующей структурой:

- указатель на начало целой части;

- указатель на начало дробной части;

- длина целой части;

- длина дробной части;

- знак.

Такая организация позволяет выполнять операции сложения и вычитания практически без проведения дополнительных операций.

ПРОЕКТИРОВАНИЕ АЛГОРИТМОВ

Сравнение

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

Сложение

Реализуются алгоритм сложения в столбик. Предполагается, что оба числа одного знака (иначе запускается алгоритм вычитания), поэтому полю знака ответа присваивается значения знака любого из операндов. Длина целой части ответа заранее определяется как максимум из длин целых частей двух операндов плюс 1 (дополнительный разряд для возможного переноса). Длина дробной части – максимум из длин дробных частей операндов.

В алгоритме сложения цифры чисел последовательно складываются, начиная с младшей значащей цифры дробной части – справа налево. Если при сложении в ячейке памяти получается значение, большее 9, то формируется знак переноса, который складывается с результатом в следующем разряде, а из значения текущей ячейки вычитается 10.

Вычитание

Реализуется алгоритм вычитания в столбик. Предполагается, что числа разных знаков и уменьшаемое по модулю больше, чем вычитаемое. В таком случае знак ответа равен знаку уменьшаемого. Если вычитаемое по модулю больше уменьшаемого, то знак ответа равен обратному знаку уменьшаемого, а перед запуском непосредственно алгоритма операнды меняются местами.

Длина целой части ответа заранее определяется как максимум из длин целых частей двух. Длина дробной части – максимум из длин дробных частей операндов.

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

Умножение

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

Непосредственно алгоритм состоит в следующем. Множимое последовательно умножается на каждую из цифр множителя. Эти частичные произведения складываются с учётом порядка цифр.

Деление

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

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

X = M*B^E,

где X – число, M – мантисса, 1≤ M<10, E – порядок, B – основание системы счисления (в данном случае - 10).

Тогда длина целой части ответа равно длине разнице порядков операндов (если разница оказалась отрицательной, длина приравнивается к нулю), длина дробной части ответа – длина дробной части первого операнда плюс порядок второго операнда. Но здесь может возникнуть проблема деления коротких чисел. Например, при таком подходе выражение 5/3 имело бы результат только 1,6. Очевидно, что нужна большая точность.

Обычно в математических расчётах используется немного знаков после запятой, редко больше 10. Но для высокой точности возможных последующих вычислений программа использует минимальное количество знаков после запятой, равное 50.

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

Служебные алгоритмы

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