Exercise1-21 <---> Exercise1-23
Exercise 1.22.
Most Lisp implementations include a primitive called runtime that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following timed-prime-test procedure, when called with an integer n, prints n and checks to see if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time used in performing the test.
(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)
(display " *** ")
(display elapsed-time))
Using this procedure, write a procedure search-for-primes that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test each prime. Since the testing algorithm has order of growth of O(√n), you should expect that testing for primes around 10,000 should take about 10 times as long as testing for primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the n prediction? Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?
Ru: Большая часть реализаций Лиспа содержат элементарную процедуру 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)
(display " *** ")
(display elapsed-time))
Используя эту процедуру, напишите процедуру search-for-primes, которая проверяет на простоту все нечетные числа в заданном диапазоне. С помощью этой процедуры найдите наименьшие три простых числа после 1000; после 10 000; после 100 000; после 1 000 000. Посмотрите, сколько времени затрачивается на каждое простое число. Поскольку алгоритм проверки имеет порядок роста O(√n), Вам следовало бы ожидать, что проверка на простоту чисел, близких к 10 000, занимает в √10 раз больше времени, чем для чисел, близких к 1000. Подтверждают ли это Ваши замеры времени? Хорошо ли поддерживают предсказание √n данные для 100 000 и 1 000 000? Совместим ли Ваш результат с предположением, что программы на Вашей машине затрачивают на выполнение задач время, пропорциональное числу шагов?
Exercise1-21 <---> Exercise1-23
Comments
Here is my partial solution: ; Exercise 1.22
(define (timed-prime-test start n)
(newline)
(display start)
(start-prime-test start n (runtime)))
(define (start-prime-test start n start-time)
(if (search-for-primes start n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
(define (search-for-primes start n)
(if (= n 0) true
(if (prime? (+ start 1))
(search-for-primes (+ start 2) (- n 1))
(search-for-primes (+ start 2) n))))
It doesn't output the values of the primes because I don't know how to make an if statement do two things if it is true! | ||||
| Posted by DanielMoerner at 2008-12-24 21:02:07 | ||||
; from example (define (timed-prime-test n)
(define (start-prime-test n start-time)
(define (report-prime elapsed-time)
(define (square x) (* x x)) (define (fast-prime? n times)
(define (expmod base exp m)
(define (fermat-test n)
(define (search-for-primes start count)
| ||||
| Posted by nx at 2009-01-05 04:43:47 X | ||||
(define (makeodd n)
| ||||
| Posted by 195 at 2009-01-27 21:05:47 X | ||||