Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Янин В.Л. "Новгородские акты XII-XV Хронологический комментарий" (История)

Майринк Г. "Белый доминиканец " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 2" (Художественная литература)

Петров Г.И. "Отлучение Льва Толстого " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 1 " (Художественная литература)
Реклама

Структура и интерпритация компьютерных программ - Абельсон Х.

Абельсон Х. Структура и интерпритация компьютерных программ — М.: Добросвет, 2006. — 608 c.
ISBN 978-5-98227-708-4
Скачать (прямая ссылка): strukturaiinterpretacii2006.pdf
Предыдущая << 1 .. 23 24 25 26 27 28 < 29 > 30 31 32 33 34 35 .. 269 >> Следующая


46Шаги редукции для случаев, когда степень больше 1, основаны на том, что для любых целых чисел х, у и m мы можем найти остаток от деления произведения х и у на m путем отдельного вычисления остатков

66

Глава 1. Построение абстракций с помощью процедур

Тест Ферма производится путем случайного выбора числа а между 1 и n — 1 включительно и проверки, равен ли а остаток по модулю n от n-ой степени а. Случайное число а выбирается с помощью процедуры 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 каждый раз его пройдет, то вероятность ошибки в нашем тесте на простоту может быть сделана настолько малой, насколько мы того пожелаем.

К сожалению, это утверждение неверно. Существуют числа, которые «обманывают» тест Ферма: числа, которые не являются простыми и тем не менее обладают свойством, что для всех целых чисел а < n а” равно а по модулю n. Такие числа очень редки, так что на практике тест Ферма вполне надежен47. Существуют варианты теста Ферма, которые обмануть невозможно. В таких тестах, подобно методу Ферма, проверка числа n на простоту ведется путем выбора случайного числа а < n и проверки некоторого условия, зависящего от n и а. (Пример такого теста см. в упражнении 1.28.) С другой

х по модулю m, у по модулю m, перемножения их, и взятия остатка по модулю m от результата. Например, в случае, когда e четно, мы можем вычислить остаток be/2 по модулю m, возвести его в квадрат и взять остаток по модулю m. Такой метод полезен потому, что с его помощью мы можем производить вычисления, не используя чисел, намного больших, чем m. (Сравните с упражнением 1.25.)

47Числа, «обманывающие» тест Ферма, называются числами Кармайкла (Carmichael numbers), и про них почти ничего неизвестно, кроме того, что они очень редки. Существует 255 чисел Кармайкла, меньших 100 000 000. Несколько первых — 561, 1105, 1729, 2465, 2821 и 6601. При проверке на простоту больших чисел, выбранных случайным образом, шанс наткнуться на число, «обманывающее» тест Ферма, меньше, чем шанс, что космическое излучение заставит компьютер сделать ошибку при вычислении «правильного» алгоритма. То, что по первой из этих причин алгоритм считается неадекватным, а по второй нет, показывает разницу между математикой и техникой.

1.2. Процедуры и порождаемые ими процессы

67

стороны, в отличие от теста Ферма, можно доказать, что для любого n условие не выполняется для большинства чисел а < n, если n не простое. Таким образом, если n проходит тест для какого-то случайного а, шансы, что n простое, уже больше половины. Если n проходит тест для двух случайных а, шансы, что n простое, больше, чем 3 из 4. Проводя тест с большим количеством случайных чисел, мы можем сделать вероятность ошибки сколь угодно малой.

Существование тестов, для которых можно доказать, что вероятность ошибки можно сделать сколь угодно малой, вызвало большой интерес к алгоритмам такого типа. Их стали называть вероятностными алгоритмами (probabilistic alorithms). В этой области ведутся активные исследования, и вероятностные алгоритмы удалось с успехом применить во многих областях48.

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

С помощью процедуры smallest-divisor найдите наименьший делитель следующих чисел: 199, 1999, 19999.

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

Большая часть реализаций Лиспа содержат элементарную процедуру runtime, которая возвращает целое число, показывающее, как долго работала система (например, в миллисекундах). Следующая процедура timed-prime-test, будучи вызвана с целым числом n, печатает n и проверяет, простое ли оно. Если n простое, процедура печатает три звездочки и количество времени, затраченное на проверку.

(define (timed-prime-test n)

(newline)

(display n)

(start-prime-test n (runtime)))

(define (start-prime-test n start-time)

(if (prime? n)

(report-prime (- (runtime) start-time))))

(define (report-prime elapsed-time)
Предыдущая << 1 .. 23 24 25 26 27 28 < 29 > 30 31 32 33 34 35 .. 269 >> Следующая