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

Процедура smallest-divisor в начале этого раздела проводит множество лишних проверок: после того, как она проверяет, делится ли число на 2, нет никакого смысла проверять делимость на другие четные числа. Таким образом, вместо последовательности 2, 3, 4, 5, 6 ..., используемой для test-divisor, было бы лучше использовать 2, 3, 5, 7, 9 .... Чтобы реализовать такое улучшение, напишите процедуру next, которая имеет результатом 3, если получает 2 как аргумент, а иначе возвращает свой аргумент плюс 2. Используйте (next test-divisor) вместо (+ test-divisor 1) в smallest-divisor. Используя процедуру timed-prime-test с модифицированной версией smallest-divisor, запустите тест для каждого из 12 простых чисел, найденных в упражнении 1.22. Поскольку эта модификация снижает количество шагов проверки вдвое, Вы должны ожидать двукратного ускорения проверки. Подтверждаются ли эти ожидания? Если нет, то каково наблюдаемое соотношение скоростей двух алгоритмов, и как Вы объясните то, что оно отличается от 2?

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

Модифицируйте процедуру timed-prime-test из упражнения 1.22 так, чтобы она использовала fast-prime? (метод Ферма) и проверьте каждое из 12 простых чисел, найденных в этом упражнении. Исходя из того, что у теста Ферма порядок роста e(logn), то какого соотношения времени Вы бы ожидали между проверкой на простоту поблизости от 1 000 000 и поблизости от 1000? Подтверждают ли это Ваши данные? Можете ли Вы объяснить наблюдаемое несоответствие, если оно есть?

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

Лиза П. Хакер жалуется, что при написании expmod мы делаем много лишней работы. В конце концов, говорит она, раз мы уже знаем, как вычислять степени, можно просто написать

(define (expmod base exp m)

(remainder (fast-expt base exp) m))

Права ли она? Стала бы эта процедура столь же хорошо работать при проверке простых чисел? Объясните.

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

У Хьюго Дума большие трудности в упражнении 1.24. Процедура fast-prime? у него работает медленнее, чем prime?. Хьюго просит помощи у своей знакомой Евы Лу Атор. Вместе изучая код Хьюго, они обнаруживают, что тот переписал процедуру expmod с явным использованием умножения вместо того, чтобы вызывать square:

(define (expmod base exp m)

(cond ((= exp 0) 1)

((even? exp) (remainder (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m))

m))

(else

(remainder (* base (expmod base (- exp 1) m))

m))))

Хьюго говорит: «Я не вижу здесь никакой разницы». «Зато я вижу, - отвечает Ева. - Переписав процедуру таким образом, ты превратил процесс порядка e(logn) в процесс порядка 0(n)». Объясните.

1.3. Формулирование абстракций с помощью процедур высших порядков 47 Упражнение 1.27.

Покажите, что числа Кармайкла, перечисленные в сноске 47, действительно «обманывают» тест Ферма: напишите процедуру, которая берет целое число п и проверяет, правда ли а" равняется а по модулю п для всех а < п, и проверьте эту процедуру на этих числах Кармайкла.

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

Один из вариантов теста Ферма, который невозможно обмануть, называется тест Мил-лера-Рабина (Miller-Rabin test) (Miller 1976; Rabin 1980). Он основан на альтернативной формулировке Малой теоремы Ферма, которая состоит в том, что если п - простое число, а а - произвольное положительное целое число, меньшее п, то а в п - 1-ой степени равняется 1 по модулю п. Проверяя простоту числа п методом Миллера-Рабина, мы берем случайное число а < п и возводим его в (п - 1)-ю степень по модулю п с помощью процедуры expmod. Однако когда в процедуре expmod мы проводим возведение в квадрат, мы проверяем, не нашли ли мы «нетривиальный квадратный корень из 1 по модулю п», то есть число, не равное 1 или п - 1, квадрат которого по модулю п равен 1. Можно доказать, что если такой нетривиальный квадратный корень из 1 существует, то п не простое число. Можно, кроме того, доказать, что если п - нечетное число, не

"- i

являющееся простым, то по крайней мере для половины чисел а < п вычисление а" i с помощью такой процедуры обнаружит нетривиальный квадратный корень из 1 по модулю п (вот почему тест Миллера-Рабина невозможно обмануть). Модифицируйте процедуру expmod так, чтобы она сигнализировала обнаружение нетривиального квадратного корня из 1, и используйте ее для реализации теста Миллера-Рабина с помощью процедуры, аналогичной fermat-test. Проверьте свою процедуру на нескольких известных Вам простых и составных числах. Подсказка: удобный способ заставить expmod подавать особый сигнал - заставить ее возвращать 0.

1.3 Формулирование абстракций с помощью процедур высших порядков

Мы видели, что процедуры, в сущности, являются абстракциями, которые описывают составные операции над числами безотносительно к конкретным числам. Например, когда мы определяем

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

мы говорим не о кубе какого-то конкретного числа, а о способе получить куб любого числа. Разумеется, мы могли бы обойтись без определения этой процедуры, каждый раз писать выражения вроде

(* 3 3 3)

(* x x x)

(* y y y)

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

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

Но даже при обработке численных данных наши возможности создавать абстракции окажутся сильно ограниченными, если мы сможем определять только процедуры, параметры которых должны быть числами. Часто одна и та же схема программы используется с различными процедурами. Для того чтобы выразить эти схемы как понятия, нам нужно строить процедуры, которые принимают другие процедуры как аргументы либо возвращают их как значения. Процедура, манипулирующая другими процедурами, называется процедурой высшего порядка (higher-order procedure). В этом разделе показывается, как процедуры высших порядков могут служить в качестве мощного механизма абстракции, резко повышая выразительную силу нашего языка.

1.3.1 Процедуры в качестве аргументов

Рассмотрим следующие три процедуры. Первая из них вычисляет сумму целых чисел от a до b:

(define (sum-integers a b)

(if (> a b) 0

(+ a (sum-integers (+ a 1) b))))

Вторая вычисляет сумму кубов целых чисел в заданном диапазоне: (define (sum-cubes a b)

(if (> a b) 0

(+ (cube a) (sum-cubes (+ a 1) b)))) Третья вычисляет сумму последовательности термов в ряде

1 1 1

который (очень медленно) сходится к п/8:49 (define (pi-sum a b)

(if (> a b) 0

(+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))

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

49 Этим рядом, который обычно записывают в эквивалентной форме =1 - i + i -

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