Длинная арифметика, Неспирный В.Н., 2010

Длинная арифметика, Неспирный В.Н., 2010.

   Как известно, в большинстве языков программирования в переменных целочисленного типа могут храниться значения из довольно ограниченного диапазона. Так в 32-разрядной знаковой переменной могут быть представлены значения не превышающие по абсолютной величине 2-1 = 2•10, в 64-разрядпой - до 2-1 = 9•10. В го же время в ряде олимпиадных задач и некоторых приложениях приходится работать с целыми числами, которые имеют большее количество знаков, или с вещественными заданными с довольно большой точностью.
Следует отметить, что в некоторых языках (Python, Java и др.) реализована поддержка больших чисел. Однако в тех же Pascal и C++ приходится самостоятельно реализовывать все необходимые операции над числами многократной точности. Работа с такими числами и называется длинной арифметикой.




Представление чисел с многократной точностью.
Как правило, числа записываются в некоторой позиционной системе счисления. Пусть это будет система с основанием Base. Тогда удобно представлять это число в памяти компьютера, записывая его цифры в некоторый массив А[МахLеп]. где MaxLen - это максимальное количество цифр в числе, с которым может потребоваться работа. В отличие от привычной записи, где на первой позиции поит самый старший разряд, в машинном представлении удобнее использовать обратную запись, где А[0] будет соответствовать младшему разряду. Тогда число А будет представляться в виде А[0] + А[ 1] • Base + А [2] • Base2 + ...

Разумеется, далеко не всегда все MaxLen цифр числа будут необходимы. При представлении маленьких чисел большинство разрядов будут просто нулевыми и их обрабатывать при большинстве операций не имеет смысла. Поэтому добавим в нашему представлению переменную 1еп, в которой будет храниться позиция старшего разряда числа (то есть А[1еп] = 0 и А[i] = 0 для всех i > 1еп, при этом эти старшие нули не обязательно будут действительно записываться в массив Л. но это будет неявно предполагаться). Возможно использование 1еп как длины представляемого числа (тогда старшая цифра будет храниться в А[1еп — 1]. однако мы в данной лекции будем рассматривать первый вариант.

Еще один вопрос, который возникает при представлении чисел - это выбор основания системы. Разумеется для компьютера более удобной является двоичная система, в этом случае многие элементарные операции могут быть реализованы с помощью битовых операций. Однако, как правило, на вход подаются и на выходе требуются числа, представленные в десятичной системе. Поскольку перевод из одной системы в другую является достаточно трудоемкой операцией (сложность O(1еп2)). то предпочтительнее использовать десятичную систему. О двоичной системе представления есть смысл задумываться .тишь в том случае, когда количество операций, выполняемых над длинными числами, довольно велико, и среди них встречаются операции со сложностью не менее O(1еп2).



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Длинная арифметика, Неспирный В.Н., 2010 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Теги: учебник по программированию :: программирование :: Неспирный