LINEBURG


<< Пред. стр.

страница 6
(всего 7)

ОГЛАВЛЕНИЕ

След. стр. >>

цифр. Для этого определения не очевидна ни единственность ми-
нимальной формы, ни минимальность длины минимальной формы.
Однако и то, и другое верно, т. е. минимальная форма определе-
на однозачно и содержит наименьшее количество ненулевых цифр
среди всех возможных форм двоичной записи числа с использова-
нием отрицательных единиц.
Докажем это. Пусть A=an ...a0 — произвольная двоичная
запись числа a, т. е.
a=2n an +...+2a1 +a0 ,
где ai =0, ±1. Далее вместо ?1 будем писать 1. Обозначим че-
рез ?(A) количество ненулевых цифр в этой записи и через µ(A) —
количество пар соседних ненулевых цифр. Заметим, что
2k +2k+1 +...+2m?1 =2m ?2k ,
поэтому, выполняя в записи A следующие преобразования:

1? ??>0?,
2? 0??...? >?0...0? (n?3),
| {z } | {z }
n n?1

3? 0?(?0)...(?0)??>?0(0?)...(0?) (n?1),
| {z } | {z }
n n+1

4? 00(?0)...(?0)??>0?(0?)...(0?) (n?0),
| {z } | {z }
n n+1

5? (n?0)
?0(?0)...(?0)??>(0?)...(0?)
| {z } | {z }
n n+2
43
(где для ?=1, 1, соответственно, ?=1, 1), мы не меняем записы-
ваемого числа, не увеличиваем величин ?(A) и µ(A) и всегда умень-
шаем их сумму:

Операция µ ?

1? или µ?2
µ?1 ??1

2? µ+2?n или µ+1?n (n?3) ?+2?n

3? или µ?2
µ?1 ??1

4? µ?1 ?

5? или µ?2
µ?1 ??1


Будем выполнять эти преобразования, пока это возможно. Так
как величина ?(A)+µ(A) не может неограниченно уменьшаться, то
в конце концов получим запись числа a, в которой нельзя будет
выполнить ни одну из этих операций.
28. Докажите, что если в записи невозможно выполнить ни одну
из указанных операций, то в этой записи нигде не будет встре-
чаться соседних ненулевых цифр.
Докажем единственность минимальной формы для данного чи-
сла a. Допустим, что есть две разные минимальные формы A и B.
Тогда они заканчиваются одинаковым числом нулей в младших
разрядах, иначе, если бы одна заканчивалась k нулями, а другая
m>k нулями, то наше число делилось бы на 2m , а с другой сто-
роны, делилось бы только на 2k , но не на 2k+1 , что невозможно.
Аналогично получаем, что их последние ненулевые цифры равны,
так как в противном случае наше число имело бы при делении
на 2m+2 (где m — число нулей в конце) в остатке разные числа 2m
и 2m+2 ?2m (так как в конце одной записи стоят цифры 010...0,
а в конце другой — цифры 010...0 ввиду отсутствия пар ненуле-
вых цифр в обеих записях). Отбрасывая равные последние цифры
от обеих записей, получаем более короткие различные записи для
равных чисел. Повторяя для этих записей проведённое рассужде-
ние, получим, наконец, что число ±1 или 0 имеет две разные за-
писи, а это невозможно.
Наконец, докажем, что в минимальной форме наименьшее ко-
личество ненулевых цифр среди всех записей с отрицательными
единицами. Действительно, из любой записи можно с помощью
рассмотренных преобразований получить построенную запись (как
только что доказано, всегда одну и ту же). Но при выполнении
этих преобразований величина ?(a) не возрастала, значит, постро-
енная запись имеет значение этой величины, равное наименьшему
возможному.
44
Преобразование обычной двоичной записи числа a к мини-
мальной форме более удобно проводить следующим образом: вычи-
слить обычную двоичную запись ?n+1 ...?1 числа 3a и вычислить
обычные разности ?i?1 =?i ??i , где i=2, ..., n+1, ?i — цифры за-
писи числа a, а ?n =?n+1 =0, тогда ?n ...?1 — минимальная форма
числа a.
Минимальная форма максимум на единицу длиннее обычной
записи, но содержит не более n/2 ненулевых цифр. При смене
знака у числа меняются знаки у всех цифр его минимальной
формы. Действительно, при замене знаков всех цифр минимальной
формы числа a получается запись числа ?a, в которой нет двух
ненулевых цифр подряд. А это по определению и есть минимальная
запись числа ?a.
Одно из возможных применений указанной минимальной фор-
мы — уменьшение числа арифметических операций для возведения
в степень. Мы уже приводили конкретный пример такого примене-
ния, а сейчас сформулируем общую теорему. Далее для краткости
вместо словосочетания <число арифметических операций алгоритма>
будем писать <сложность алгоритма>.
Обозначим число ненулевых цифр в записи числа n в виде мини-
мальной формы через ?(n), а уменьшенную на единицу длину этой
записи — через ?(n). Мы используем те же обозначения, что и в обыч-
ном бинарном методе (см. § 2), но заметим, что новая функция ?(n)
может быть на единицу больше старой, зато новая функция ?(n) не мо-
жет быть больше старой, а часто меньше её, иногда почти в два раза.
Теорема. При использовании калькулятора с одной ячейкой
памяти сложность вычисления xn не превосходит
?(n)+?(n)?1.
Д о к а з а т е л ь с т в о. Используя полученную минимальную
форму, запишем n в виде суммы 2?(n) ??(n) +...+2?1 +?0 , ?i =0, ±1,
содержащей ?(n) ненулевых слагаемых. Далее, как и в обычном
бинарном методе возведения в степень, используем аналог схемы
Горнера, а цифрам ?1 сопоставляем операцию деления на основа-
ние степени. Полученное обобщение бинарного метода использует
не более ?(n) возведений в квадрат и ?(n)?1 умножений и деле-
ний. Теорема доказана.
Аналогично обычному бинарному методу можно доказать соот-
ношения ?(2n)+?(2n)=?(n)+?(n)+1, ?(n±1)??(n)+1. Из послед-
него неравенства следует, что ?(n±1)+?(n±1)??(n)+?(n)+1. Дей-
ствительно, случай n±1=n+1 рассматривается аналогично обычно-
му бинарному методу, а в случае n±1=n?1, очевидно, ?(n?1)?
??(n) и из неравенства ?(n?1)??(n)+1 следует нужная оценка.
Используя доказанное неравенство, можно аналогично обычному
бинарному методу в случае, когда содержимое ячейки памяти
45
никогда не обновляется, получить аналогичную нижнюю оценку
сложности возведения в степень ?(n)+?(n)?1. Читателю предоста-
вляется возможность самому убедится в этом.
Недостатком двоичной системы при её ручном использовании
является то, что из-за увеличения длины записи по сравнению с де-
сятичной системой соответственно возрастает и сложность умно-
жения. Использование минимальной формы позволяет уменьшить
сложность ручного умножения двоичных чисел. Опишем алгоритм
умножения, предложенный в начале 1950-х годов американским
математиком Бутом.
Для этого данные n-разрядные и m-разрядные двоичные числа
преобразуем в их минимальные формы и заметим, что эти формы
содержат не более n+1 и m+1 разрядов, причём из них не более
a=n/2+1 и b=m/2+1 ненулевых разрядов соответственно.
Сложность преобразования не превосходит 3n+3m?4. Умножая
минимальные формы с помощью школьного алгоритма, замечаем,
что число нетривиальных умножений не превосходит ab, так как
ненулевых строк будет не более b и в каждой из них нетривиальных
умножений не более a. Отметим, что каждое нетривиальное
умножение, по-существу, не сложнее нетривиального умножения
в обычной двоичной системе, и будем считать, что оно выполняется
с единичной сложностью, так же как и нетривиальное сложение
(операция нетривиальна, если оба операнда не нули). Заметим
также, что число нетривиальных сложений не превосходит (b?1)?
?(a+n?1), так как всего сложений различных строк требуется
не более b?1, а каждое из них состоит из не более чем n пе-
реносов (переносы могут быть как 1, так и ?1) и не более чем
a?1 нетривиальных сложений (в складываемых строчках имеется
не более a?1 стоящих друг под другом ненулевых цифр). Поэтому
сложность умножения не превосходит (b?1)(a+n?1)+ab?
?mn+(m+n)/2+1. Полученный результат содержит не более
n+m+2 разрядов (так как он получается при сложении m+1
не более чем (n+1)-разрядных чисел с соответствующими сдвига-
ми). Его можно преобразовать к обычной двоичной записи, сделав
не более n+m+2 операции (заменяем блоки соседних цифр вида
10...01 на соответствующие блоки вида 01...11, блоки вида 11 —
на блоки 01, блоки без отрицательных цифр оставляем без измене-
ния). Значит, полная сложность операции умножения не превосхо-
дит mn+(m+n)/2+1+3n+3m?4+n+m+2?mn+3,5(m+n).

§ 18. БЫСТРОE УМНОЖЕНИЕ МНОГОЧЛЕНОВ
Мало кто знает, что относительно недавно были открыты
гораздо более быстрые алгоритмы умножения и деления много-
значных чисел и многочленов, чем <школьные>. Первый такой
46
алгоритм придумал в 1962 году А. А. Карацуба, отвечая на вопрос
А. Н. Колмогорова. Впоследствии А. Л. Тоомом, Ф. Штрассеном
и А. Шенхаге были построены ещё более быстрые алгоритмы.
Идею метода Карацубы можно пояснить на следующем приме-
ре. Пусть перемножаются восьмизначные числа U=u1 ...u8 и V =
=v1 ...v8 . Представим их как двузначные числа в системе счи-
сления с основанием 104 : U=U1 U2 , V =V1 V2 , где U1 =u1 u2 u3 u4 ,
U2 =u5 u6 u7 u8 , V1 =v1 v2 v3 v4 , V2 =v5 v6 v7 v8 . Тогда их произведение
можно представить в следующем виде:
UV =108 U1 V1 +104 ((U1 ?U2 )(V2 ?V1 )+U1 V1 +U2 V2 )+U2V2 .
Эта формула сводит умножение восьмизначных чисел к трём
операциям умножения и шести операциям сложения-вычитания
четырёхзначных чисел (с учётом переносов в следующие разряды).
Обычный способ требует четырёх умножений и трёх сложений-
вычитаний, но так как три раза сложить четырёхзначные числа
можно быстрее, чем один раз перемножить, то метод Карацубы
уже восьмизначные числа перемножает быстрее. В общем случае он
требует для перемножения n-значных чисел по порядку не больше
nlog2 3 <n1,585 операций над цифрами.
Далее мы поговорим о сложности умножения более подробно.
Обозначим через M(n) наименьшее количество операций сло-
жения, вычитания и умножения (выполняемых над коэффициен-
тами многочленов и промежуточными числовыми результатами),
требующихся для перемножения двух многочленов степеней, мень-
ших n. Тогда справедливо неравенство
M(n)?2M( n/2 )+M( n/2 )+4 n/2 +2n?4 *). (*)
Действительно, применим равенство
(f1 x n/2 +f0 )(g1 x n/2 +g0 )=
=f1 g1 x2 n/2 +((f1 +f0 )(g1 +g0 )?f1 g1 ?f0 g0 )x n/2 +f0 g0 ,
где степени многочленов f1 и g1 меньше n/2 , а степени многочле-
нов f0 и g0 меньше n/2 , и заметим, что для вычисления произве-
дений f1 g1 , f0 g0 требуется не более M( n/2 )+M( n/2 ) операций,
для вычисления сумм f1 +f0 , g1 +g0 , f1 g1 +f0 g0 нужно не более
2 n/2 +2 n/2 ?1 операций (так как число операций равно наи-
меньшему из количеств ненулевых коэффициентов у складывае-
мых многочленов), для вычисления произведения (f1 +f0 )(g1 +g0 )
используется не более M( n/2 ) операций, для вычисления разно-
сти (f1 +f0 )(g1 +g0 )?f1 g1 ?f0 g0 достаточно n?1 операций, так как

*) Через x обозначается наибольшее целое число, не большее x (<округление
вниз>), а через x — наименьшее целое число, не меньшее x (<округление вверх>).
47
(f1 +f0 )(g1 +g0 )?f1 g1 ?f0 g0 =f1 g0 +f0 g1 , значит, степень этого мно-
гочлена равна n/2 + n/2 ?2=n?2, сложение многочленов f0 g0
и f1 g1 x2 n/2 выполняется <бесплатно>, так как они не имеют по-
добных членов, причём в их сумме отсутствует член вида x2 n/2 ?1 ,
поэтому для сложения многочленов f0 g0 +f1 g1 x2 n/2 и (f1 g0 +f0 g1 )?
?x n/2 достаточно n?2 операций. B итоге требуется дополнительно
4 n/2 +2n?4 операций.
Оценку сложности метода Карацубы можно представить в сле-
дующем виде. Если n кратно 2k , то справедливо неравенство
##A A
k M n ! + 8n ?2! ?8n+2,
! !
M(n)?3   k ! !
2 
2k
а при любом n — неравенство
35 log2 3
M(n)< n .
3
Действительно, пусть 2k m=n. Тогда неравенство
##A A
k M n ! + 8n ?2! ?8n+2,
! !
! !
M(n)?3   k  
k
2 2
доказывается индукцией по k. База (k=1) — это неравенство (*).
Шаг индукции обосновывается тем же неравенством.
Bыберем k так, чтобы 2k <n?2k+1 . Тогда, если 3·2k?1 <n, то
# Alog 3
k+1 )<3k?1 (M(4)+30)?3k?1 ·55<55 n ! 2 < 35 nlog2 3 .
!
! 
M(n)?M(2
3 3
Если же n?3·2k?1 , то
35 log2 3
M(n)?M(3·2k?1 )<3k?1 (M(3)+22)?3k?1 ·35? n .
3
29. Проверьте, что обычный способ умножения многочленов
даёт оценку M(n)?n2 +(n?1)2 .

§ 19. БЫСТРОE УМНОЖЕНИЕ ЧИСЕЛ
Перейдём теперь к умножению чисел.
Обозначим через M(n) наименьшее количество операций сло-
жения, вычитания и умножения, выполняемых над числами, мень-
шими a, требующихcя для перемножения двух n-значных чисел,
записанных в позиционной системе счисления с основанием a.
Метод умножения почти такой же, как и для многочленов.
Для примера укажем, как сделать необходимые изменения в рас-
суждениях из предыдущего параграфа.
Справедливы неравенства
M(2n)?3M(n)+19n, M(2n+1)?2M(n+1)+M(n)+17n+10.
48
Действительно, применим тождество
(f1 b n/2 +f0 )(g1 b n/2 +g0 )=
=f1 g1 b2 n/2 +(f1 g1 +f0 g0 ?(f1 ?f0 )(g1 ?g0 ))b n/2 +f0 g0 ,
где числа f1 и g1 — n/2 -разрядные, а числа f0 и g0 — n/2 -раз-
рядные и заметим, что для вычисления произведений f1 g1 и f0 g0
требуется M( n/2 )+M( n/2 ) операций, для вычисления разностей
f0 ?f1 , g0 ?g1 и суммы f1 g1 +f0 g0 требуется не более
n(1+ n/2 ? n/2 )+2( n/2 + n/2 ?1)+2( n/2 + n/2 )?1=
=4n?3+n(1+ n/2 ? n/2 )
операций, так как числа f1 g1 и f0 g0 имеют не более чем 2 n/2
и 2 n/2 разрядов соответственно, а в случае чётного n нужно ещё
2 n/2 =n операций для предварительного сравнения чисел (чтобы
не вычитать из меньшего большее). Заметим далее, что для вычисле-
ния произведения (f1 ?f0 )(g1 ?g0 ) требуется не более M( n/2 )+1
операций (одна операция для вычисления знака у произведения),
для вычисления разности f1 g1 +f0 g0 ?(f1 ?f0 )(g1 ?g0 )=f1 g0 +f0 g1
требуется не более 2 n/2 +1+2 n/2 ?1=4 n/2 операций, сложе-
ние чисел f0 g0 и f1 g1 b2 n/2 осуществляется <бесплатно> (записи
этих чисел просто объединяются в одну запись), а для сложе-
ния чисел f1 g1 b2 n/2 +f0 g0 и (f1 g0 +f0 g1 )b n/2 требуется не более
2n? n/2 +n+1?1=2n+ n/2 операций (так как число f1 g0 +f0 g1
имеет не более n+1 разрядов, а младшие n/2 разрядов числа
f0 g0 не участвуют в операциях). B итоге требуется дополнительно
4n?3+n(1+ n/2 ? n/2 )+1+4 n/2 +2n+ n/2 =7n+3 n/2 +
+n(1+ n/2 ? n/2 )?2 операций.
Остальные детали предоставляем додумать читателю.
Обозначим через Q(n) сложность возведения n-разрядного чи-
сла в квадрат и такое же обозначение будем использовать для
сложности возведения в квадрат многочлена степени n?1.
(a+b)2 ?(a?b)2
30. Используя тождество ab= , докажите для
4
случая операций с числами неравенство M(n)?2Q(n)+13n+
+O(1), а для случая операций с многочленами — неравенство
M(n)?2Q(n)+6n+4.

ПРИЛОЖЕНИЕ
ЧТО МОЖНО ВЫЧИСЛИТЬ НА СЧЁТАХ?
Воспользовавшись такой простейшей моделью вычислений, как
абак, в России называвшийся просто счётами, можно построить всё
здание современной теории алгоритмов. Разумеется, это понятие
надо немного идеализировать и придать ему, например, такой вид.
49
Пусть нам нужно вычислить данную числовую функцию
f(x1 , ..., xn ). Представим себе, что у нас есть счёты, содержащие n
<входных> спиц, на i-й из которых имеется в начальный момент
xi костяшек, одну <выходную> (первоначально пустую) спицу,
на которой будет получен результат, и некоторое количество
(первоначально пустых) <рабочих> спиц. Каждая спица состоит
на самом деле из двух половин, и пока речь шла только о левых
половинах. В правой половине каждой спицы помещается потен-
циально не ограниченный запас костяшек, и по нашему желанию
мы можем сделать в любой момент одну из двух операций: либо
передвинуть самую левую костяшку из правой половины спицы
в <рабочую> левую половину, увеличив тем самым <записанное>
в ней число на единицу, либо передвинуть крайнюю правую ко-
стяшку из <рабочей> левой половины спицы в правую <запасную>
половину, уменьшив тем самым <записанное> в левой половине
число на единицу.
Если перейти к терминологии языков программирования,
то мы здесь описали систему регистров машины, и две опера-
ции, применимые к ним — прибавление единицы и вычитание
единицы.
Сама программа вычисления на счётах (или на соответству-
ющей идеализированной машине с неограниченными регистрами)
представляет из себя диаграмму, состоящую из кружочков, в ко-
торых написаны номера спиц (регистров), после которых стоят
знаки плюс или минус, указывающие на операции, которые мы
выполняем на этих спицах (регистрах). Из кружочков со знаком
плюс выходит одна стрелка, ведущая в какой-то другой кружочек
(она указывает какую следующую операцию делать). Из кружоч-
ков со знаком минус выходит две такие стрелки. Одна из них по-
мечается специальным значком ? и используется только тогда, ко-
гда на <рабочей> половине спицы не осталось костяшек (в регистре
записан ноль). Тогда операция вычитания единицы, естественно,
не может быть выполнена, и просто делается переход к новой
вершине диаграммы по указанной стрелке. Если же на спице оста-
вались костяшки (регистр не равен 0), то операция вычитания
единицы выполняется и тоже делается переход к новой вершине
диаграммы, но, естественно, по второй стрелке. Отметим ещё,
что совсем не обязательно, чтобы разные вершины диаграммы вы-
полняли операции с разными спицами.
Теперь, чтобы такая диаграмма могла определить работающую
программу, осталось выделить в ней две стрелки — начало и конец
работы программы. Первая из них выделяется среди других стрелок
тем, что имеет конец в одной из вершин диаграммы, но не имеет
начала в вершинах диаграммы, а начинается в специальном кружке
со словом <НАЧАЛО>, а вторая, наоборот, начинается в одной
50
из вершин, но не ведёт ни в одну из вершин диаграммы, а ведёт
в кружок со словом <КОНЕЦ>.
Программа начинает работать со слова <НАЧАЛО> и заканчи-
вает, когда придёт в слово <КОНЕЦ> (но может и <зациклиться>
и никогда не закончить работу). Результатом работы программы
можно считать число, записанное на <выходном> регистре. Если
это число всегда совпадает со значением рассматриваемой функции
f(x1 , ..., xn ), в случае, если она определена при заданных значениях
переменных, и если программа всегда <зацикливается> в случае,
если эта функция не определена при заданных значениях перемен-
ных, то говорят, что программа (вычисления на счётах!) правильно
вычисляет заданную функцию.
С целью сокращения диаграмм у сложных программ можно
вместо некоторых вершин, имеющих одну выходную стрелку, ис-
пользовать не оператор прибавления единицы, а кружок с сим-
волическим обозначением какой угодно программы (называемой
в этом случае, естественно, подпрограммой).
Работу любой такой программы можно промоделировать и на ма-
шине Тьюринга, если изображать состояние абака в каждый момент
времени на ленте машины в виде массивов палочек, разделённых
пробелами. В возможность обратного моделирования поверить труд-
нее, тем не менее справедливо следующее утверждение, приводимое
без доказательства.
Класс числовых функций, вычислимых на абаке, совпадает
с классом функций, вычислимых по Тьюрингу.
А как известно, на машине Тьюринга можно промоделировать
любые компьютерные вычисления. Значит, и на счётах тоже можно!
31. Приведите пример <зацикливающейся> программы для абака.
32. Приведите пример программы, складывающей содержимое
двух регистров и помещающей результат во второй регистр одно-
временно с обнулением первого регистра.
33. Приведите пример программы, складывающей содержи-
мое двух регистров и помещающей результат во второй регистр,
но не изменяющей первый регистр (используйте вспомогатель-
ный <рабочий> регистр).
34. Приведите пример программы, перемножающей содержи-
мое двух регистров и помещающей результат в третий регистр
одновременно с обнулением первого регистра. (Используйте пре-
дыдущую программу в качестве подпрограммы.)

<< Пред. стр.

страница 6
(всего 7)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign