Рефераты Набор процедур манипулирования с целыми числами произвольной длины.

Вернуться в Информатика

Набор процедур манипулирования с целыми числами произвольной длины.
МОСКОВСКИЙ ИНСТИТУТ РАДИОТЕХНИКИ ЭЛЕКТРОНИКИ И АВТОМАТИКИ МЕЖДУНАРОДНЫЙ ФАКУЛЬТЕТ ИНФОРМАТИКИ ИНТЕР ЭВМ К У Р С О В А Я Р А Б О Т А по дисциплине "Алгоритмические Языки и Программирование" Москва 1993г. Постановка задачи: Составить набор процедур манипулирования с целымичислами произвольной длины. Процедуры должны обеспечивать:формирование и ввод целых чисел произвольной длины,сложение, вычитание, сравнение и умножение целых чисел.Работоспособность процедур продемонстрировать надемонстрационной программе.. Использованные средства языка: Модуль, реализующий целые числа произвольной длины, итестовая программа написаны на языке С++. Для представления целых чисел произвольной длиныопределен класс UNLIM. Операции над этими числамиреализованы путем переопределения для класса UNLIM следующихопераций: + (унарный и бинарный) - (унарный и бинарный) * == != < > <= >= << (операция вывода класса OSTREAM). Структура данных: Абсолютная величина числа произвольной длины хранится впамяти в виде массива типа CHAR. В каждом элементе массиваможет находится число от 0 до 99, то есть два разряда всегочисла. В нулевом элементе хранятся младшие два разряда, впоследнем элементе - старшие два разряда. Если число имеетнечетное количество разрядов, то в последнем элементемассива хранится один последний разряд, т.е. число от 0 до9. Лидирующие нули в массиве не хранятся. Число 0представлено массивом из одного элемента, в котором хранится0. С целью минимизировать копирование и расход памяти классUNLIM реализован так, что на одно представление абсолютнойвеличины могут ссылаться несколько чисел, при этом ведетсяучет ссылок. Объект класса UNLIM состоит из поля SIGN - знака числа иполя PV - указателя на дескриптор представления абсолютнойвеличины. Число 0 всегда имеет знак PLUS. Дескриптор представления абсолютной величины числапредставляет собой объект структуры DESCRIPTOR и имеетследующие поля: body - указатель на массив, в котором хранится представление абсолютной величины числа; len - длина массива body[] в байтах; HowMany - количество ссылок на данное представление;. Реализация операций сравнения: Из операций сравнения только < и != напрямую сравниваютчисла, остальные операции выражены через эти две. При работеопераций < и != сначала проверяются знаки и длины чисел, итолько в случае их совпадения производится поразрядноесравнение чисел (в качестве разрядов здесь берутся целыебайты - т.е. разряды в системе счисления с основанием 100). Реализация операций арифметики: Операция унарный + просто возвращает само число. Операция унарный - возвращает новый объект класса UNLIM,который ссылается на то же представление модуля числа, что иаргумент, и имеет знак, противоположный знаку аргумента. Операция бинарный + определена и для случаев, когдазнаки операндов совпадают, и когда эти знаки различны. В первом случае знак результата соответствует знакуодного (любого) из операндов, а модуль результата являетсярезультатом сложения модулей операндов. При этом есликоличество разрядов первого операнда равно A, а второго - B,то количество разрядов операнда может быть либо max(A,B),либо max(A,B)+1, поэтому при выделении памяти под массив длямодуля результата берется второе значение. Никакойоптимизации этого массива после сложения модулей операндовне делается, так как в данном случае потеря памяти налидирующие нули может быть максимум 1 байт, и выгоднеесэкономить на скорости, чем на памяти. В случае, когда знаки операндов различны, знакрезультата равен знаку операнда с максимальным модулем, амодуль результата получатся вычитанием модуля операнда сминимальным модулем из модуля операнда с максимальныммодулем
Добавить в Одноклассники    

 

Rambler's Top100