Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, сокращённый курс, по 2 часа в неделю)



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




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

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

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

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

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

Задачи


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


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

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

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

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

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

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

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

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

12345678 = 12 • 10002 + 345 • 10001 + 678 • 10000.

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

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

от -232 = -4 294 967 296 до 232 - 1 = 4 294 967 295.

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

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

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



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






Наверх