примерно удвоит количество используемых ресурсов. Для экспоненциального процесса каждое увеличение размера задачи на единицу будет умножать количество ресурсов на постоянный коэффициент. В оставшейся части раздела 1.2 мы рассмотрим два алгоритма, которые имеют логарифмический порядок роста, так что удвоение размера задачи увеличивает требования к ресурсам на постоянную величину.

Упражнение 1.14.

Нарисуйте дерево, иллюстрирующее процесс, который порождается процедурой count-change из раздела 1.2.2 при размене 11 центов. Каковы порядки роста памяти и числа шагов, используемых этим процессом при увеличении суммы, которую требуется разменять?

Упражнение 1.15.

Синус угла (заданного в радианах) можно вычислить, если воспользоваться приближением sin x « x при малых x и употребить тригонометрическое тождество

sin х = 3 sin--4 sin -

33

для уменьшения значения аргумента sin. (В этом упражнении мы будем считать, что угол «достаточно мал», если он не больше 0.1 радиана.) Эта идея используется в следующих процедурах:

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)

(if (not (> (abs angle) 0.1))

angle

(p (sine (/ angle 3.0)))))

a.Сколько раз вызывается процедура p при вычислении (sine 12.15)?

b.Каковы порядки роста в терминах количества шагов и используемой памяти (как функция а) для процесса, порождаемого процедурой sine при вычислении (sine a)?

1.2.4 Возведение в степень

Рассмотрим задачу возведения числа в степень. Нам нужна процедура, которая, приняв в качестве аргумента основание b и положительное целое значение степени n, возвращает Ъп. Один из способов получить желаемое - через рекурсивное определение

Ъп = ь • bn-1 b° = 1

которое прямо переводится в процедуру

(define (expt b n) (if (= n 0) 1

(* b (expt b (- n 1)))))

Это линейно рекурсивный процесс, требующий 0(n) шагов и 0(n) памяти. Подобно факториалу, мы можем немедленно сформулировать эквивалентную линейную итерацию:

(define (expt b n) (expt-iter b n 1))

(define (expt-iter b counter product) (if (= counter 0) product (expt-iter b

(- counter 1)

(* b product))))

Эта версия требует 0(n) шагов и 0(1) памяти.

Можно вычислять степени за меньшее число шагов, если использовать последовательное возведение в квадрат. Например, вместо того, чтобы вычислять b8 в виде

b • (b • (b • (b • (b • (b • (b • b)))))) мы можем вычислить его за три умножения:

b2 = b • b

b4 = b2 • b2 b8 = b4 • b4

Этот метод хорошо работает для степеней, которые сами являются степенями двойки. В общем случае при вычислении степеней мы можем получить преимущество от последовательного возведения в квадрат, если воспользуемся правилом

bn = (bn/2)2 если n четно bn = b • bn-1 если n нечетно

Этот метод можно выразить в виде процедуры

(define (fast-expt b n) (cond ((= n 0) 1)

((even? n) (square (fast-expt b (/ n 2)))) (else (* b (fast-expt b (- n 1))))))

где предикат, проверяющий целое число на четность, определен через элементарную процедуру remainder:

(define (even? n)

(= (remainder n 2) 0))

Процесс, вычисляющий fast-expt, растет логарифмически как по используемой памяти, так и по количеству шагов. Чтобы увидеть это, заметим, что вычисление b2n с помощью этого алгоритма требует всего на одно умножение больше, чем вычисление bn. Следовательно, размер степени, которую мы можем вычислять, возрастает примерно вдвое с каждым следующим умножением, которое нам разрешено делать. Таким образом, число умножений, требуемых для вычисления степени n, растет приблизительно так же быстро, как логарифм n по основанию 2. Процесс имеет степень роста 0(log(n)).37

37Точнее, количество требуемых умножений равно логарифму n по основанию 2 минус 1 и плюс

Если n велико, разница между порядком роста 0(log(n)) и 0(n) оказывается очень заметной. Например, fast-expt при n = 1000 требует всего 14 умножений.38 С помощью идеи последовательного возведения в квадрат можно построить также итеративный алгоритм, который вычисляет степени за логарифмическое число шагов (см. упражнение 1.16), хотя, как это часто бывает с итеративными алгоритмами, его нельзя записать так же просто, как рекурсив-

39

ный алгоритм.39 Упражнение 1.16.

Напишите процедуру, которая развивается в виде итеративного процесса и реализует возведение в степень за логарифмическое число шагов, как fast-expt. (Указание: используя наблюдение, что (bn/2)2 = (b2)n/2, храните, помимо значения степени п и основания b, дополнительную переменную состояния а, и определите переход между состояниями так, чтобы произведение abn от шага к шагу не менялось. Вначале значение а берется равным 1, а ответ получается как значение а в момент окончания процесса. В общем случае метод определения инварианта (invariant quantity), который не изменяется при переходе между шагами, является мощным способом размышления о построении итеративных алгоритмов.)

Упражнение 1.17.

Алгоритмы возведения в степень из этого раздела основаны на повторяющемся умножении. Подобным же образом можно производить умножение с помощью повторяющегося сложения. Следующая процедура умножения (в которой предполагается, что наш язык способен только складывать, но не умножать) аналогична процедуре expt:

(define (* a b) (if (= b 0)

0

(+ a (* a (- b 1)))))

Этот алгоритм затрачивает количество шагов, линейно пропорциональное b. Предположим теперь, что, наряду со сложением, у нас есть операции double, которая удваивает целое число, и halve, которая делит (четное) число на 2. Используя их, напишите процедуру, аналогичную fast-expt, которая затрачивает логарифмическое число шагов.

Упражнение 1.18.

Используя результаты упражнений 1.16 и 1.17, разработайте процедуру, которая порождает итеративный процесс для умножения двух чисел с помощью сложения, удвоения и деления пополам, и затрачивает логарифмическое число шагов.40

количество единиц в двоичном представлении n. Это число всегда меньше, чем удвоенный логарифм n по основанию 2. Произвольные константы к\ и k2 в определении порядка роста означают, что для логарифмического процесса основание, по которому берется логарифм, не имеет значения, так что все такие процессы описываются как G(log(n)).

38Если Вас интересует, зачем это кому-нибудь может понадобиться возводить числа в 1000-ю степень, смотрите раздел 1.2.6.

39Итеративный алгоритм очень стар. Он встречается в Чанда-сутре Ачарьи Пингалы, написанной до 200 года до н.э. В Knuth 1981, раздел 4.6.3, содержится полное обсуждение и анализ этого и других методов возведения в степень.

40 Этот алгоритм, который иногда называют «методом русского крестьянина», очень стар. Примеры его использования найдены в Риндском папирусе, одном из двух самых древних существующих математических документов, который был записан (и при этом скопирован с еще более древнего документа) египетским писцом по имени Ах-мосе около 1700 г. до н.э.