Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 15
Текст из файла (страница 15)
Построение абстракций с помощью процедур64√должно выполняться n ≥ Fib(k) ≈ φk / 5. Следовательно, число шагов k растет каклогарифм n (по основанию φ). Следовательно, порядок роста равен Θ(log n).Упражнение 1.20.Процесс, порождаемый процедурой, разумеется, зависит от того, по каким правилам работает интерпретатор. В качестве примера рассмотрим итеративную процедуру gcd, приведенную выше.Предположим, что мы вычисляем эту процедуру с помощью нормального порядка, описанного вразделе 1.1.5. (Правило нормального порядка вычислений для if описано в упражнении 1.5.)Используя подстановочную модель для нормального порядка, проиллюстрируйте процесс, порождаемый при вычислении (gcd 206 40) и укажите, какие операции вычисления остатка действительно выполняются. Сколько операций remainder выполняется на самом деле при вычислении(gcd 206 40) в нормальном порядке? При вычислении в аппликативном порядке?1.2.6. Пример: проверка на простотуВ этом разделе√ описываются два метода проверки числа n на простоту, один с порядком роста Θ( n), и другой, «вероятностный», алгоритм с порядком роста Θ(log n).В упражнениях, приводимых в конце раздела, предлагаются программные проекты наоснове этих алгоритмов.Поиск делителейС древних времен математиков завораживали проблемы, связанные с простыми числами, и многие люди занимались поисками способов выяснить, является ли число простым.
Один из способов проверки числа на простоту состоит в том, чтобы найти делителичисла. Следующая программа находит наименьший целый делитель (больший 1) числаn. Она проделывает это «в лоб», путем проверки делимости n на все последовательныечисла, начиная с 2.(define (smallest-divisor n)(find-divisor n 2))(define (find-divisor n test-divisor)(cond ((> (square test-divisor) n) n)((divides? test-divisor n) test-divisor)(else (find-divisor n (+ test-divisor 1)))))(define (divides? a b)(= (remainder b a) 0))Мы можем проверить, является ли число простым, следующим образом: n простоетогда и только тогда, когда n само является своим наименьшим делителем.(define (prime? n)(= n (smallest-divisor n)))Тест на завершение основан на том,√ что если число n не простое, у него долженбыть делитель, меньше или равный n44 .
Это означает, что алгоритм может проверять44 Еслиd — делитель n, то n/d тоже. Но d и n/d не могут оба быть больше√n.1.2. Процедуры и порождаемые ими процессы65√делители только от 1 до n. Следовательно, число шагов,√ которые требуются, чтобыопределить, что n простое, будет иметь порядок роста Θ( n).Тест ФермаТест на простоту с порядком роста Θ(log n) основан на утверждении из теории чисел,известном как Малая теорема Ферма45 .Малая теорема Ферма:Если n — простое число, а a — произвольное целое число меньше, чем n, тоa, возведенное в n-ю степень, равно a по модулю n.(Говорят, что два числа равны по модулю n (congruent modulo n), если они дают одинаковый остаток при делении на n.
Остаток от деления числа a на n называется такжеостатком a по модулю n (remainder of a modulo n) или просто a по модулю n.)Если n не является простым, то, вообще говоря, большинство чисел a < n не будутудовлетворять этому условию. Это приводит к следующему алгоритму проверки на простоту:имея число n, случайным образом выбрать число a < n и вычислить остаток от anпо модулю n. Если этот остаток не равен a, то n определенно не является простым. Еслион равен a, то мы имеем хорошие шансы, что n простое. Тогда нужно взять еще однослучайное a и проверить его тем же способом.
Если и оно удовлетворяет уравнению,мы можем быть еще более уверены, что n простое. Испытывая все большее количествоa, мы можем увеличивать нашу уверенность в результате. Этот алгоритм называетсятестом Ферма.Для реализации теста Ферма нам нужна процедура, которая вычисляет степень числапо модулю другого числа:(define (expmod base exp m)(cond ((= exp 0) 1)((even? exp)(remainder (square (expmod base (/ exp 2) m))m))(else(remainder (* base (expmod base (- exp 1) m))m))))Эта процедура очень похожа на fast-expt из раздела 1.2.4. Она использует последовательное возведение в квадрат, так что число шагов логарифмически растет с увеличениемстепени46 .45 Пьер де Ферма (1601-1665) считается основателем современной теории чисел. Он доказал множество важных теорем, однако, как правило, он объявлял только результаты, не публикуя своих доказательств. Малаятеорема Ферма была сформулирована в письме, которое он написал в 1640-м году.
Первое опубликованноедоказательство было даноЭйлером в 1736 г. (более раннее, идентичное доказательство было найдено в неопубликованных рукописях Лейбница). Самый знаменитый результат Ферма, известный как Большая теоремаФерма, был записан в 1637 году в его экземпляре книги Арифметика (греческого математика третьего векаДиофанта) с пометкой «я нашел подлинно удивительное доказательство, но эти поля слишком малы, чтобывместить его». Доказательство Большой теоремы Ферма стало одним из самых известных вопросов теориичисел. Полное решение было найдено в 1995 году Эндрю Уайлсом из Принстонского университета.46 Шаги редукции для случаев, когда степень больше 1, основаны на том, что для любых целых чисел x,y и m мы можем найти остаток от деления произведения x и y на m путем отдельного вычисления остатков66Глава 1. Построение абстракций с помощью процедурТест Ферма производится путем случайного выбора числа a между 1 и n − 1 включительно и проверки, равен ли a остаток по модулю n от n-ой степени a.
Случайноечисло a выбирается с помощью процедуры random, про которую мы предполагаем, чтоона встроена в Scheme в качестве элементарной процедуры. Random возвращает неотрицательное число, меньшее, чем ее целый аргумент. Следовательно, чтобы получитьслучайное число между 1 и n − 1, мы вызываем random с аргументом n − 1 и добавляемк результату 1:(define (fermat-test n)(define (try-it a)(= (expmod a n n) a))(try-it (+ 1 (random (- n 1)))))Следующая процедура прогоняет тест заданное число раз, как указано ее параметром.Ее значение истинно, если тест всегда проходит, и ложно в противном случае.(define (fast-prime? n times)(cond ((= times 0) true)((fermat-test n) (fast-prime? n (- times 1)))(else false)))Вероятностные методыТест Ферма отличается по своему характеру от большинства известных алгоритмов,где вычисляется результат, истинность которого гарантирована.
Здесь полученный результат верен лишь с какой-то вероятностью. Более точно, если n не проходит тестФерма, мы можем точно сказать, что оно не простое. Но то, что n проходит тест, хотя и является очень сильным показателем, все же не гарантирует, что n простое. Намхотелось бы сказать, что для любого числа n, если мы проведем тест достаточное количество раз и n каждый раз его пройдет, то вероятность ошибки в нашем тесте напростоту может быть сделана настолько малой, насколько мы того пожелаем.К сожалению, это утверждение неверно.
Существуют числа, которые «обманывают»тест Ферма: числа, которые не являются простыми и тем не менее обладают свойством,что для всех целых чисел a < n an равно a по модулю n. Такие числа очень редки,так что на практике тест Ферма вполне надежен47 . Существуют варианты теста Ферма,которые обмануть невозможно.
В таких тестах, подобно методу Ферма, проверка числаn на простоту ведется путем выбора случайного числа a < n и проверки некоторогоусловия, зависящего от n и a. (Пример такого теста см. в упражнении 1.28.) С другойx по модулю m, y по модулю m, перемножения их, и взятия остатка по модулю m от результата. Например, вслучае, когда e четно, мы можем вычислить остаток be/2 по модулю m, возвести его в квадрат и взятьостаток по модулю m. Такой метод полезен потому, что с его помощью мы можем производить вычисления, неиспользуя чисел, намного больших, чем m. (Сравните с упражнением 1.25.)47 Числа, «обманывающие» тест Ферма, называются числами Кармайкла (Carmichael numbers), и про нихпочти ничего неизвестно, кроме того, что они очень редки.
Существует 255 чисел Кармайкла, меньших 100000 000. Несколько первых — 561, 1105, 1729, 2465, 2821 и 6601. При проверке на простоту больших чисел,выбранных случайным образом, шанс наткнуться на число, «обманывающее» тест Ферма, меньше, чем шанс,что космическое излучение заставит компьютер сделать ошибку при вычислении «правильного» алгоритма. То,что по первой из этих причин алгоритм считается неадекватным, а по второй нет, показывает разницу междуматематикой и техникой.1.2.
Процедуры и порождаемые ими процессы67стороны, в отличие от теста Ферма, можно доказать, что для любого n условие невыполняется для большинства чисел a < n, если n не простое. Таким образом, если nпроходит тест для какого-то случайного a, шансы, что n простое, уже больше половины.Если n проходит тест для двух случайных a, шансы, что n простое, больше, чем 3 из 4.Проводя тест с большим количеством случайных чисел, мы можем сделать вероятностьошибки сколь угодно малой.Существование тестов, для которых можно доказать, что вероятность ошибки можно сделать сколь угодно малой, вызвало большой интерес к алгоритмам такого типа.Их стали называть вероятностными алгоритмами (probabilistic alorithms).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
