Exercise1-22 <---> Exercise1-24
Exercise 1.23
The smallest-divisor procedure shown at the start of this section does lots of needless testing: After it checks to see if the number is divisible by 2 there is no point in checking to see if it is divisible by any larger even numbers. This suggests that the values used for test-divisor should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2. Modify the smallest-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1). With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of the 12 primes found in exercise 1.22. Since this modification halves the number of test steps, you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is different from 2?
Ru: Процедура 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?
Scheme solution:
(define (square n) (* n n))
(define (next n)
(if (= n 2) 3
(+ 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 (next test-divisor)))))
(define (divides? a b)
(= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (current-seconds)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (current-seconds) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
The observed ratio of the initial algorithm execution time to modified one is 3:2.
Although the number of steps is reduced in half in the modified find-divisor, each step requires additional calculations of if expression, its predicate and the next procedure itself.
I suppose, the time complexity of each basic Scheme operation depends on the compiler\interperer quality and the hardware. However, we may give a rough argumentation. Each iteration of the initial find-divisor procedure has 9 elementary operations and function calls. An iteration of modified procedure has 12 operations, which we may count as 6, because the total number of iterations is halved. And 9:6 = 3:2 is exactly the ratio observed.
Exercise1-22 <---> Exercise1-24