Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лк13 Длинная арифметика.doc
Скачиваний:
42
Добавлен:
28.10.2018
Размер:
252.93 Кб
Скачать

29

Длинная арифметика

Длинная арифметика 1

Введение 1

1. Способы представления «длинных» чисел 3

2. Ввод-вывод "длинных" чисел 7

3. Сложение двух «длинных» чисел 11

4. Умножение «длинного» числа на «короткое» 13

5. Умножение «длинного» числа на «длинное» 15

6. Рекурсивный алгоритм умножения 17

7. Вычитание двух “длинных” чисел с учетом сдвига 18

8. Деление «короткого» числа на «короткое» столбиком 19

9. Деление «длинного» числа на «короткое» нацело с остатком 23

10. Сравнение двух “длинных” чисел 25

27

11. Задачи с решениями 27

12. Контрольные вопросы и упражнения 30

Введение

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

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

5980000000000000000000000000,

выражающее массу Земли в граммах, или микроскопически малыми, как число

0.00000000000000000000000000091091,

выражающее массу электрона в граммах.

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

Однако это не совсем так, потому что делаются точные космические расчеты, вычисляются массы планет и звезд, в физических экспериментах делаются точные вычисления, но главное это делает компьютер. Но как?

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

В распространенных системах программирования для хранения целых чисел обычно отводится два или четыре байта, то есть 16 или 32 бита. В первом случае можно представить 216=65536 различных чисел, во втором — 232=4294967296.

Таким образом, используя для целого числа 4 байта (что соответствует типу longint в Турбо Паскале), мы можем представить числа от 0 до 4294967295.

Этого количества (больше 4 миллиардов!) оказывается достаточно для многих задач. Для многих, но не для всех. Иногда нужно обрабатывать числа, которые не входят в этот диапазон. (Программисты обычно говорят, что эти числа не помещаются в разрядную сетку.)

Итак, можно сделать вывод: диапазон представления целых чисел (Integer, Word, Longint) ограничен. Поэтому при решении некоторых задач всегда приходится действовать с оглядкой: как бы не допустить возникновения ошибки из-за выхода за диапазон или переполнения.

Например, если стоит задача вычисления факториала (n! = 123…n), то в диапазоне представления величин типа Integer удается правильно получить только 7! = 5040, а в диапазоне представления типа Longint — 12! = 479001600. Для больших значений, конечно, можно использовать действительные типы данных, но это уже не гарантирует точного результата. А если нам необходимо выполнить арифметические действия над очень большими числами, например,

30! = 265252859812191058636308480000000?

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

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

Для операций над целыми числами мы можем гарантировать точный результат, если будем производить только операции сложения, вычитания и умножения над вещественным типом с максимальным количеством разрядов, отведенных под мантиссу (Extended или Сотрlex в Turbo-Pascal) и если количество значащих цифр в результате выполнения таких действий не превышает точности этих типов (18 значащих цифр для приведенных типов).

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

Если количества двоичных разрядов в стандартных компьютерных типах данных для представления числа недостаточно, то назовем такое число "длинным" (ДЧ). Реализация арифметических операций над такими "длинными" числами получила название "длинной" арифметики.

Основными сложностями при работе с такими числами являются их представление в памяти ЭВМ и операции над ними: сложение, вычитание, умножение и деление "длинных" чисел; функции их сравнения.