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

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

К сожалению, пауза в публикации решений затянулась. Буду наверстывать.

В 22-ом упражнении нас просят произвести замер производительности алгоритма вычисления простых чисел и подтвердить (или опровергнуть) экспериментально то теоретическое заключение, что его порядок роста равен Θ(√n).

Сначала вычислим, как указано в условии, наименьшие три простых числа после 1000; после 10 000; после 100 000; после 1 000 000. Я несколько видоизменил код из условия с тем, чтобы сделать вывод более компактным и выводить только найденные простые числа. Также, поскольку я использую DrScheme, я сделал (runtime) (этой функции нет в стандартной библиотеке) алиасом для стандартной функции (current-milliseconds).

Код для экспериментов выглядит следующим образом:

(define (runtime) 
  (current-milliseconds))
(define (timed-prime-test n) 
  (start-prime-test n (runtime)))
(define (start-prime-test n start-time) 
  (if (prime? n) 
      (report-prime n (- (runtime) start-time)) 
      false))
(define (report-prime n elapsed-time) 
  (display n) 
  (display " *** ") 
  (display elapsed-time) 
  (newline) 
  true)
(define (search-for-primes number-from prime-count) 
  (if (> prime-count 0) 
      (if (timed-prime-test number-from) 
          (search-for-primes (+ number-from 1) (- prime-count 1)) 
          (search-for-primes (+ number-from 1) prime-count))))

В результате получаем:

> (search-for-primes 1000 3) 
1009 *** 0 
1013 *** 0 
1019 *** 0
> (search-for-primes 10000 3) 
10007 *** 0 
10009 *** 0 
10037 *** 0
> (search-for-primes 100000 3) 
100003 *** 0 
100019 *** 0 
100043 *** 0
> (search-for-primes 1000000 3) 
1000003 *** 0 
1000033 *** 0 
1000037 *** 0

Как видим, все измеренные временные интервалы нулевые. Это связано с тем, что современные компьютеры настолько быстры, что успевают выполнить все операции за время, меньшее порога чувствительности функции (current-milliseconds). Во времена выхода первого и даже второго издания SICP вычислительная мощь компьютеров была куда скромнее.

Для получения более интересных результатов, которые позволят проверить гипотезу о равенстве порядка роста Θ(√n), мы просто будем рассчитывать простые числа для интервалов, начинающихся с больших значений.

Вот что получается, если вычислять по 3 наименьших простых числа, начиная с 100 000 000 000, 1 000 000 000 000, 10 000 000 000 000, 100 000 000 000 000:

> (search-for-primes 100000000000 3) 
100000000003 *** 422 
100000000019 *** 672 
100000000057 *** 672
> (search-for-primes 1000000000000 3) 
1000000000039 *** 2328 
1000000000061 *** 1922 
1000000000063 *** 2062
> (search-for-primes 10000000000000 3) 
10000000000037 *** 6188 
10000000000051 *** 6157 
10000000000099 *** 6297
> (search-for-primes 100000000000000 3) 
100000000000031 *** 19844 
100000000000067 *** 21765 
100000000000097 *** 21016

Усредняя время вычисления по каждой из троек чисел, получаем: 

n1=1011,  t1=589 мс
n2=1012,  t2=2104 мс,  t2/t1=3.57
n3=1013,  t3=6214 мс,  t3/t2=2.95
n4=1014,  t4=20875 мс,  t4/t3=3.36

Все отношения tk+1/tk достаточно близки к √(nk+1/nk)=√10=3.16, то есть мы можем говорить, что гипотеза о равенстве порядка роста Θ(√n) подтверждается на практике.

Так же утвердительно мы можем ответить и на вопрос о совместимости полученного результата с предположением, что программы на машине затрачивают на выполнение задач время, пропорциональное числу шагов. Это очень важный факт, который, впрочем, как и многие другие важные и основополагающие факты, кажется очевидным.

Comments

Comment from Sergey Khenkin
Date: October 10, 2007, 9:31 pm

Любопытно, что Кен Дик, на которого я люблю ссылаться время от времени, в своем решении (http://www.kendyck.com/archives/2005/05/23/solution-to-sicp-exercise-122/) не смог ни подтвердить, ни опровергнуть гипотезу о порядке роста равном квадратному корню.

Pingback from SICP по-русски » Blog Archive » Решение упражнения 1.23 из SICP
Date: October 10, 2007, 10:25 pm

[…] SICP по-русски Структура и интерпретация компьютерных программ: заметки и решения « Решение упражнения 1.22 из SICP […]

Pingback from SICP по-русски » Blog Archive » Решение упражнения 1.24 из SICP
Date: October 11, 2007, 8:30 pm

[…] упражнение также базируется на упражнении 22, так что изучите его до того, как переходить к […]

Comment from Johnny
Date: November 5, 2009, 11:24 am

Странно. Похоже в DrScheme 4.2.2 (r5rs) current-milliseconds уже не является стандартной функцией. Вставляю ваш код и: reference to undefined identifier: current-milliseconds.

Comment from smersh
Date: December 30, 2009, 7:21 pm

2Johnny нужно установить новый язык SICP (установка работает только с последней версией drscheme!). Там рантайм уже есть в стандартной библиотеке.
http://www.neilvandyke.org/sicp-plt/

Comment from Dmitri
Date: July 25, 2010, 9:46 pm

В последней DrRacket вместо (runtime) следует использовать (current-inexact-milliseconds), тогда значения выдаются нормальные.
Кроме того, в вашем решении вы забыли выполнить условие задачи, что проверять следует только нечетные числа. Примерно вот так:

(define (odd? n)
  (= (remainder n 2) 1))
  
(define (search-for-primes start-num count)  
  (if (< 0 count)
      (if (timed-prime-test start-num)
          (search-for-primes (+ start-num 1) (- count 1))  
          (search-for-primes (+ start-num 1) count))))

Comment from Ruslan
Date: January 7, 2014, 12:19 pm

Поправьте меня если я не прав. В книге(на русском) сказано: “Напишите процедуру …, которая проверяет на простоту все нечетные числа в заданном диапазоне“.
Мой вариант решения:

(define runtime current-inexact-milliseconds)

(define (timed-prime-test n)
(start-prime-test n (runtime)))

(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time) n)
#f))

(define (report-prime elapsed-time n)
(display n)
(display " *** ")
(display elapsed-time)
(newline))

(define (inc x) (+ x 1))

(define (search-for-primes start end)
(cond ((= start end) (newline))
((odd? start) (begin (timed-prime-test start)
(search-for-primes (inc start) end)))
(else (search-for-primes (inc start) end))))

(search-for-primes 1000000 1000100)

Comment from Ruslan
Date: January 7, 2014, 12:22 pm

Небольшой организационный момент, как вы правильно форматируете код? Используя ?

Comment from ASh
Date: June 11, 2014, 10:26 am

В приведенном коде у верхнего if нет else.

Comment from Irv
Date: January 3, 2016, 5:25 pm

(define (prime? n)
  (define (try x)
    (if (> (* x x) n)
        n
        (if (= (remainder n x) 0)
            x
            (try (+ x 1)))))
  (= (try 2) n))

(define (test n)
  (define (runtime) 
    (current-milliseconds))
  (define (start time)
    (define (report-true x)
      (display x)
      (display " : ")
      (display (- (runtime) time))
      (newline)
      true)
    (if (prime? n)
        (report-true n)
        false))
  (start (runtime)))

(define (print-primes from)
  (define (iter v cnt)
    (if (> cnt 0)        
        (if (test v)
            (iter (+ v 1) (- cnt 1))
            (iter (+ v 1) cnt))
        from))
    (iter from 5))

(print-primes 100000000)
(print-primes 10000000000)
(print-primes 1000000000000)
(print-primes 100000000000000)
(print-primes 10000000000000000)

; (test 2147483647)
; (test 359334085968622831041960188598043661065388726959079837)

Write a comment