Уроки 64 - 65
Длинные числа
(§38. Целочисленные алгоритмы)

Содержание урока

Решето Эратосфена

«Длинные» числа

«Длинные» числа. Задача

Вопросы и задания

Задачи

«Длинные» числа

Современные алгоритмы шифрования используют достаточно длинные ключи, которые представляют собой числа длиной 256 битов и больше. С ними нужно выполнять разные операции: складывать, умножать, находить остаток от деления. Вопрос состоит в том, как хранить такие числа в памяти, где для целых чисел отводится память значительно меньших размеров (обычно до 64 битов). Ответ достаточно очевиден: нужно разбить длинное число на части так, чтобы оно занимало несколько ячеек памяти.

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

Для хранения «длинного» числа удобно использовать массив целых чисел. Например, число 12345678 можно записать в массив с индексами от 0 до 9 таким образом:

Такой способ имеет ряд недостатков:

1) нужно где-то хранить длину числа, иначе числа 12345678, 123456780 и 1234567800 будет невозможно различить;
2) неудобно выполнять арифметические операции, которые начинаются с младшего разряда;
3) память расходуется неэкономно, потому что в одном элементе массива хранится только один разряд — число от 0 до 9.

Чтобы избавиться от первых двух проблем, достаточно «развернуть» массив наоборот, так чтобы младший разряд находился в А[0]. В этом случае на рисунках удобно применять обратный порядок элементов:

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

Здесь использовано равенство

12345678 = 12 • 1000² + 345 • 1000¹ + 678 • 1000⁰.

Фактически мы представили исходное число в системе счисления с основанием 1000.

Сколько разрядов можно хранить в одном элементе массива? Это зависит от размера элемента. Например, если переменная занимает 4 байта и число хранится со знаком, допустимый диапазон его значений:

от -2³² = -4 294 967 296 до 2³² - 1 = 4 294 967 295.

В таком элементе можно хранить до 9 разрядов десятичного числа, т. е. использовать систему счисления с основанием 1 000 000 000. Однако нужно учитывать, что с такими числами будут выполняться арифметические операции, результат которых должен помещаться в переменную некоторого типа. Например, если надо умножать разряды этого числа на число k < 100 и в языке программирования нет 64-битных целочисленных типов данных, то в элементе массива можно хранить не более 7 разрядов.

Покажем на примере, как можно использовать систему счисления с основанием 1 000 000 для выполнения операций с «длинными» числами.

Следующая страница «Длинные» числа. Задача

Cкачать материалы урока