Занятие 16

В некоторых задачах требуется производить вычисления с большими числами, сохраняя все цифры результата. Стандартный целый тип short позволяет хранить значения не более `3,2*10^4`, тип long – не более `2*10^9`, тип long long – не более `9*10^18`. При превышении предела происходит переполнение и потеря старших разрядов числа. Вещественные типы double и long double хотя и позволяют работать с большими числами (до `10^300` и `10^4000` соответственно), но за счет потери младших разрядов числа (сохраняются 15 и 18 старших разрядов результата соответственно).

При решении подобных задач обычно определяется специальный тип данных – длинное целое число, позволяющий хранить необходимое количество разрядов числа. Обычно достаточно неотрицательных целых чисел.

Числа можно хранить в виде строки, что неэффективно как с точки зрения использования памяти (в одном байте можно не 1, а 2 цифры), так и времени работы (каждая цифра обрабатывается отдельно). Наиболее приемлимым способом является представление числа в виде последовательности разрядов по основанию `10^4` или `10^9`, причем в начале последовательности лучше хранить младшие разряды числа.

Последовательность может быть фиксированного размера (старшие неиспользуемые разряды при этом равны 0).

const int lint_size=1000;
const int lint_base=10000;
typedef short lint[lint_size/4];

Недостатки такого способа: 1) возможно переполнение при неправильном определении величины получаемых чисел; 2) при обработке небольших чисел будут выполняться лишние вычисления с нулевыми старшими разрядами. Можно использовать последовательность переменного размера, например, vector<short>.

const int lint_base=10000;
typedef vector<short> lint;