С использованием больших чисел

В языке программирования C существует большое количество целочисленных типов данных, области определения которых охватывают числа различных диапазонов. При решении задачи программист должен выбрать правильные типы данных для числовых переменных, исходя из природы соответствующих данных, а также требований к занимаемой программой и ее данными памяти и желаемому быстродействию. Тем не менее диапазоны встроенных целочисленных типов данных языка C ограничены, что не позволяет выполнять вычисления над достаточно большими числами (например, с разрядностью более 20 десятичных цифр). Это оказывается серьезным препятствием при решении задач, требующих выполнения операций над большими числами, например вычисления элементов быстрорастущих последовательностей. В частности, использование типа int языка C для вычисления элементов последовательности Фибоначчи позволяет получить только 46 первых чисел, после чего наступает целочисленное переполнение.

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

· на компьютерах с процессорами низкой разрядности и микроконтроллерах. Например, на компьютерах и микроконтроллерах с 8-битными процессорами без использования длинной арифметики невозможно выполнить никакие сколько-нибудь полезные вычисления;

· при решении задач криптографии;

· при создании математического и финансового программного обеспечения, требования к точности вычислений в котором очень высоки и критичны, а ошибки округления и переполнения недопустимы;

· для «спортивных» вычислений трансцендентных чисел (π;, e и т. д.) с высокой точностью;

· для решения олимпиадных задач по программированию.

Рассмотрим, каким образом можно хранить длинные целые числа в памяти компьютера и как выполнять над ними действия. Обычно длинное число представляют в виде массива, элементы которого содержат цифры длинного числа, и отдельно дополнительно сохраняют длину числа, т. е. количество значимых цифр. В этом случае удобнее перейти от десятичной системы счисления к системе счисления с большим основанием, так как появится возможность лучше использовать пространство оперативной памяти, занятой массивом. Количество значимых цифр занесем в первый элемент массива (с индексом 0). Цифры числа будем хранить в обратном порядке, т. е. младшая цифра будет храниться в элементе массива с меньшим индексом.

Сделаем следующие объявления: