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

11 October, 2007 (19:42) | Решения упражнений

Это упражнение также базируется на упражнении 22, так что изучите его до того, как переходить к этому.

Для замеров времени в этом упражнении я применю несколько другую технику. Если в упражнении 22 я выбрал большие числа, то в данном случае достаточно будет просто задать в (fast-prime?) достаточно большое число прогонов теста Ферма и работать с числами порядка 1000, 10000, 100000, 1000000. Это позволит остаться в рамках ограничений процедуры (random), которая принимает на вход числа не больше 231.

Выбрав количество прогонов теста равным 10000, получим такой код:

(define (square x) 
  (* x x))
(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))))
(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)))
(define (runtime) 
  (current-milliseconds))
(define (timed-prime-test n) 
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time) 
  (if (fast-prime? n 10000) 
      (report-prime n (- (runtime) start-time)) 
      false))
(define (report-prime n elapsed-time) 
  (display n) 
  (display " *** ") 
  (display elapsed-time) 
  (newline) 
  true)

Теперь запустим (timed-prime-test) для каждого из 12 чисел, полученных в начале 22-го упражнения:

> (list 
   (timed-prime-test 1009) 
   (timed-prime-test 1013) 
   (timed-prime-test 1019) 
   (timed-prime-test 10007) 
   (timed-prime-test 10009) 
   (timed-prime-test 10037) 
   (timed-prime-test 100003) 
   (timed-prime-test 100019) 
   (timed-prime-test 100043) 
   (timed-prime-test 1000003) 
   (timed-prime-test 1000033) 
   (timed-prime-test 1000037))
1009 *** 1610 
1013 *** 1704 
1019 *** 1812 
10007 *** 2078 
10009 *** 1985 
10037 *** 2062 
100003 *** 2500 
100019 *** 2875 
100043 *** 2594 
1000003 *** 2953 
1000033 *** 3266 
1000037 *** 3296

Какие выводы можно сделать из полученных результатов? Легко видеть, что с увеличением чисел в 10 раз время увеличивается на константную величину. Что это означает? Это как раз и означает, что перед нами логарифмическая зависимость, так как log Cn = log C + log n, то есть log 1000000 = log 10 + log 100000 = 2 log 10 + log 10000 = 3 log 10 + log 1000.

Кроме того, сравнивая время для 1000 и для 1000000, в случае логарифмического порядка роста следует ожидать двукратного увеличения времени для 1000000 по сравнению со временем для 1000, так как log 1000000 = log 10002 = 2 log 1000. Наши экспериментальные данные полностью согласуются с этими ожиданиями.

Вообще тема логарифмов довольно сложна для неподготовленных людей, но если один раз разобраться в сути, то в дальнейшем проблем уже возникать не будет. Поэтому, если у вас есть какие-то вопросы, спрашивайте в комментариях. Постараюсь ответить всем.

Write a comment