Решение упражнения 1.23 из SICP

10 October, 2007 (22:17) | Решения упражнений

Это упражнение является логическим продолжением предыдущего упражнения 22, поэтому ознакомьтесь с его решением прежде, чем продолжать.

Итак, измененный код процедуры (find-divisor) будет выглядеть так:

(define (next n) 
  (if (= n 2) 
      3 
      (+ 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)))))
 

Результаты запусков тестов из предыдущего упражнения таковы:

> (search-for-primes 100000000000 3) 
100000000003 *** 516 
100000000019 *** 235 
100000000057 *** 516
> (search-for-primes 1000000000000 3) 
1000000000039 *** 1031 
1000000000061 *** 1016 
1000000000063 *** 1031
> (search-for-primes 10000000000000 3) 
10000000000037 *** 3515 
10000000000051 *** 3453 
10000000000099 *** 3469
> (search-for-primes 100000000000000 3) 
100000000000031 *** 11203 
100000000000067 *** 11032 
100000000000097 *** 11000

А вот сравнительная таблица:

Числа около Старый алгоритм, мс Новый алгоритм, мс Ускорение в, раз
1011 589 422 1.40
1012 2104 1026 2.05
1013 6214 3479 1.79
1014 20875 11078 1.88

Можно говорить, что для достаточно больших чисел ускорение действительно практически в два раза. Для маленьких чисел это не так, что можно объяснить, в первую очередь, увеличившимися накладными расходами в процедуре (find-divisor), которые “съедают” выигрыш от усечения множества перебираемых кандидатов в простые числа.

Write a comment