SICP по-русски

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

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

Выбрав количество прогонов теста равным 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 1000² = 2 log 1000. Наши экспериментальные данные полностью согласуются с этими ожиданиями.

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