Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
§ 1. ВРЕМЕННЫЕ ОЦЕНКИ СЛОЖНОСТИ
3
Решение. Сначала представляется целая часть. Потом дробная часть умножается на основание 6. Целая часть полученного числа дает d_i, а к его дробной части применяется та же процедура, что последовательно дает а!_2, .... Таким способом получаем:
3,1415926... = (11,001001000011111...)2 = (D, DRS .. .)26-Число разрядов. Как было упомянуто выше, целое число, удо-
к — 1 к
влетворяющее неравенствам b ^ n < b , имеет к разрядов по основанию Ь. С помощью логарифмов это можно переписать в следующем виде («[ ]» обозначает целую часть числа):
+ 1
(здесь и всюду далее log понимается как натуральный логарифм loge).
Двоичные операции. Начнем с очень простой арифметической задачи сложения двух двоичных целых чисел, например,
пи
1111000 + 0011110 10010110
Предположим, что оба числа имеют длину в к бит (слово «бит» является сокращением выражения «бшагу digi?»). Если запись одного из чисел короче, ее можно дополнить нужным числом нулей слева. Хотя в примере рассматриваются маленькие целые (складываются 120 и 30), следует иметь в виду, что число к может быть очень большим, скажем, 500 или 1000.
Детально проанализируем всю процедуру сложения. При сложении необходимо к раз повторить следующие шаги.
1. Посмотреть на верхний и нижний биты, а также проверить, имеется ли перенос единицы от сложения младших разрядов.
2. Если оба бита нулевые, а переноса нет, то в данном разряде суммы записываем нуль и двигаемся дальше.
3. Если либо а) оба бита нулевые и есть перенос, либо Ь) один бит — нуль, другой — единица и переноса нет, то записываем единицу и двигаемся дальше.
4. Если либо а) один бит — нуль, другой — единица и есть перенос, либо Ь) оба бита — единицы и переноса нет, то записываем нуль в данный разряд, записываем единицу переносов в следующий столбец и двигаемся дальше.
м і , logn
число разрядов = logb n + 1 =---
L log Ь _
4
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
5. Если оба бита — единицы и есть перенос, то в данном разряде суммы записываем единицу, записываем единицу переносов в следующий столбец и двигаемся дальше.
Однократное выполнение этих шагов называется двоичной (битовой) операцией. Сложение двух /с-разрядных двоичных чисел требует к двоичных операций. Мы увидим ниже, что и более сложные задачи тоже могут быть разбиты на двоичные операции. Время, которое расходует компьютер на решение задачи, по сути дела пропорционально числу двоичных операций. Конечно, константа пропорциональности — число наносекунд, расходуемых на одну двоичную операцию, — зависит от вида компьютера. (Сказанное является упрощением, так как это время может зависеть также от «технических» факторов, например, времени доступа к памяти.) Когда мы говорим об оценке времени работы, подразумевается оценка числа двоичных операций. В этих оценках мы будем пренебрегать временем, расходуемым на запись информации или на логические шаги, отличные от двоичных операций. На практике основное время занимает выполнение именно двоичных операций.
Теперь рассмотрим процесс умножения fc-разрядного двоичного числа на /-разрядное двоичное число. Например,
11101 1101 11101 111010 11101 101111001
Предположим, что мы пользуемся обычным способом умножения /с-разрядного двоичного числа п и /-разрядного двоичного числа т. Мы получаем самое большее / строк (каждый нулевой бит числа т уменьшает это количество на единицу), где каждая строка содержит копию числа п, сдвинутую влево на некоторое расстояние, т. е. копию, дополненную нулями справа. Пусть имеется / ^ / строк. Поскольку мы ограничиваемся двоичными операциями, мы не можем сложить все строки сразу. Правильнее будет двигаться от второй строки к /'-й, складывая каждую строку с накопившейся суммой верхних строк. На каждом этапе сначала отмечаем, как далеко сдвинуто влево число п в рассматриваемой строке. Сносим вниз крайние правые разряды накопленной суммы верхних строк, а остальную часть записи накопленной суммы складываем (описанным выше способом) с числом п, что требует к двоичных операций. В примере выше 11101 х 1101 после сложения первых двух строк получаем 10010001, сносим вниз послед-
§ 1. ВРЕМЕННЫЕ ОЦЕНКИ СЛОЖНОСТИ
5
ние три разряда 001 и складываем остальное (т.е. 10010) с n = 11101. И наконец, к сумме 10010+ 11101 = 101111 приписываем 001 и получаем 101111001 — сумму /' = 3 строк.
Это описание показывает, что задача умножения может быть разложена на / — 1 сложений, по к двоичных операций каждое. Так как /' — 1 < / ^ /, то получаем простую оценку
Time (умножение ^-разрядного и /-разрядного двоичных чисел) < kl.
Здесь и далее Time (Л) обозначает число двоичных операций, необходимых для выполнения процедуры А.
Сделаем несколько замечаний об этом выводе оценки для числа двоичных операций, необходимых для двоичного умножения. Во-первых, как упоминалось выше, мы подсчитали только число двоичных операций. Мы пренебрегли временем на сдвиг числа п влево и временем на снос крайних правых разрядов накопленной суммы. На практике операции сдвига и копирования являются быстрыми по сравнению с большим числом производимых двоичных операций, так что можно без опаски проигнорировать их. Другими словами, мы определим «временную оценку (сложности)» арифметической задачи как верхнюю границу для числа двоичных операций без учета операций сдвига, копирования, обращения в память и т.п. Заметим, что мы могли бы применить эту же временную оценку к умножению к-разрядной и /-разрядной двоичных дробей. Единственное отличие состоит в необходимости правильного определения места для запятой, разделяющей целую и дробную части.
