Решение для упражнения 1.23 Модификация smallest-divisor

Упражнение 1.23 Модификация smallest-divisor

Код Ревью

Сравни свои решения

    #| BEGIN (Введите свое решение) |#
(define (runtime) (current-milliseconds))

(define (square x) (* x x))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

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

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))
#| END |#

    #| BEGIN (Введите свое решение) |#
; !Важное уточнение! В связи с низкой точностью возвращаемого результата у runtime в реализации LISP'а от MIT, для получения видимого результата будет повторение 1000 раз. Изменена процедура start-prime-test

(define (square x) (* x x))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

(define (start-prime-test n start-time)
  (define (loop i k)
    (if (= i k)
        (report-prime (- (runtime) start-time))
        (begin
          (prime? n)
          (loop (+ i 1) k))))
  (if (prime? n)
      (loop 1 1000)
      #f))

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

; Тесты
(define (assert condition message)
  (if (not condition)
      (error message)))

(assert (= (next 2) 3) "1 test failed")
(assert (= (next 4) 6) "2 test failed")
(assert (= (smallest-divisor 4) 2) "3 test failed")
(assert (= (smallest-divisor 5) 5) "4 test failed")
(display "Tests passed")
(newline)

; Ожидаемое изменение времени выполнения: уменьшение в 2 раза

; (timed-prime-test 1009) 1009 *** 3.9999999999999994e-2
; (timed-prime-test 1013) 1013 *** .03
; (timed-prime-test 1019) 1019 *** .03
#|
Старое среднее: 0.05
Новое среднее: 0.0(3)
Отношение: 1.5
Вывод: Отклонение от ожидаемого значения
|#

; (timed-prime-test 10007) 10007 *** .11000000000000001
; (timed-prime-test 10009) 10009 *** .1
; (timed-prime-test 10037) 10037 *** .09999999999999998
#|
Старое среднее: 0.16(3)
Новое среднее: 0.10(3)
Отношение: 1.5806...
Вывод: Аналогично предыдущему выводу
|#

; (timed-prime-test 100003) 100003 *** .31
; (timed-prime-test 100019) 100019 *** .31000000000000005
; (timed-prime-test 100043) 100043 *** .31000000000000005
#|
Старое среднее: 0.52
Новое среднее: 0.31
Отношение: 1.6774...
Вывод: Отклонение незначительно уменьшилось относительно предыдущих, но все еще существенно
|#

; (timed-prime-test 1000003) 1000003 *** 1.01
; (timed-prime-test 1000033) 1000033 *** .98
; (timed-prime-test 1000037) 1000037 *** .9899999999999998
#|
Старое среднее: 1.57
Новое среднее: 0.99(3)
Отношение: 1.5805...
Вывод: Относительно предыдущих вычислений отклонение не сильно изменилось
|#

#|
Вывод: Ожидания не подтвердились, новые измерения стали в среднем в 1.5846... раз меньше по времени. Это объясняется тем, что:

  1.  оптимизация уменьшает число проверок делителей примерно вдвое, но не устраняет накладные расходы, не зависящие от количества делителей (вызовы, проверки условий, арифметика, измерение времени);
  2.  добавляется стоимость вычисления next;
  3.  есть шум измерения и особенности runtime.
|#

#| END |#

    #| BEGIN (Введите свое решение) |#
(define (runtime) (current-milliseconds))

(define (square x) (* x x))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

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

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))
#| END |#

    #| BEGIN (Введите свое решение) |#
; !Важное уточнение! В связи с низкой точностью возвращаемого результата у runtime в реализации LISP'а от MIT, для получения видимого результата будет повторение 1000 раз. Изменена процедура start-prime-test

(define (square x) (* x x))

(define (runtime) (current-milliseconds))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

(define (start-prime-test n start-time)
  (define (loop i k)
    (if (= i k)
        (report-prime (- (runtime) start-time))
        (begin
          (prime? n)
          (loop (+ i 1) k))))
  (if (prime? n)
      (loop 1 1000)
      #f))

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

; Тесты
(define (assert condition message)
  (if (not condition)
      (error message)))

(assert (= (next 2) 3) "1 test failed")
(assert (= (next 4) 6) "2 test failed")
(assert (= (smallest-divisor 4) 2) "3 test failed")
(assert (= (smallest-divisor 5) 5) "4 test failed")
(display "Tests passed")
(newline)

; Ожидаемое изменение времени выполнения: уменьшение в 2 раза

; (timed-prime-test 1009) 1009 *** 3.9999999999999994e-2
; (timed-prime-test 1013) 1013 *** .03
; (timed-prime-test 1019) 1019 *** .03
#|
Старое среднее: 0.05
Новое среднее: 0.0(3)
Отношение: 1.5
Вывод: Отклонение от ожидаемого значения
|#

; (timed-prime-test 10007) 10007 *** .11000000000000001
; (timed-prime-test 10009) 10009 *** .1
; (timed-prime-test 10037) 10037 *** .09999999999999998
#|
Старое среднее: 0.16(3)
Новое среднее: 0.10(3)
Отношение: 1.5806...
Вывод: Аналогично предыдущему выводу
|#

; (timed-prime-test 100003) 100003 *** .31
; (timed-prime-test 100019) 100019 *** .31000000000000005
; (timed-prime-test 100043) 100043 *** .31000000000000005
#|
Старое среднее: 0.52
Новое среднее: 0.31
Отношение: 1.6774...
Вывод: Отклонение незначительно уменьшилось относительно предыдущих, но все еще существенно
|#

; (timed-prime-test 1000003) 1000003 *** 1.01
; (timed-prime-test 1000033) 1000033 *** .98
; (timed-prime-test 1000037) 1000037 *** .9899999999999998
#|
Старое среднее: 1.57
Новое среднее: 0.99(3)
Отношение: 1.5805...
Вывод: Относительно предыдущих вычислений отклонение не сильно изменилось
|#

#|
Вывод: Ожидания не подтвердились, новые измерения стали в среднем в 1.5846... раз меньше по времени. Это объясняется тем, что:

  1.  оптимизация уменьшает число проверок делителей примерно вдвое, но не устраняет накладные расходы, не зависящие от количества делителей (вызовы, проверки условий, арифметика, измерение времени);
  2.  добавляется стоимость вычисления next;
  3.  есть шум измерения и особенности runtime.
|#

#| END |#

    #| BEGIN (Введите свое решение) |#
; !Важное уточнение! В связи с низкой точностью возвращаемого результата у runtime в реализации LISP'а от MIT, для получения видимого результата будет повторение 1000 раз. Изменена процедура start-prime-test

(define (square x) (* x x))

(define (runtime) (current-milliseconds))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

(define (start-prime-test n start-time)
  (define (loop i k)
    (if (= i k)
        (report-prime (- (runtime) start-time))
        (begin
          (prime? n)
          (loop (+ i 1) k))))
  (if (prime? n)
      (loop 1 1000)
      #f))

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

; Ожидаемое изменение времени выполнения: уменьшение в 2 раза

; (timed-prime-test 1009) 1009 *** 3.9999999999999994e-2
; (timed-prime-test 1013) 1013 *** .03
; (timed-prime-test 1019) 1019 *** .03
#|
Старое среднее: 0.05
Новое среднее: 0.0(3)
Отношение: 1.5
Вывод: Отклонение от ожидаемого значения
|#

; (timed-prime-test 10007) 10007 *** .11000000000000001
; (timed-prime-test 10009) 10009 *** .1
; (timed-prime-test 10037) 10037 *** .09999999999999998
#|
Старое среднее: 0.16(3)
Новое среднее: 0.10(3)
Отношение: 1.5806...
Вывод: Аналогично предыдущему выводу
|#

; (timed-prime-test 100003) 100003 *** .31
; (timed-prime-test 100019) 100019 *** .31000000000000005
; (timed-prime-test 100043) 100043 *** .31000000000000005
#|
Старое среднее: 0.52
Новое среднее: 0.31
Отношение: 1.6774...
Вывод: Отклонение незначительно уменьшилось относительно предыдущих, но все еще существенно
|#

; (timed-prime-test 1000003) 1000003 *** 1.01
; (timed-prime-test 1000033) 1000033 *** .98
; (timed-prime-test 1000037) 1000037 *** .9899999999999998
#|
Старое среднее: 1.57
Новое среднее: 0.99(3)
Отношение: 1.5805...
Вывод: Относительно предыдущих вычислений отклонение не сильно изменилось
|#

#|
Вывод: Ожидания не подтвердились, новые измерения стали в среднем в 1.5846... раз меньше по времени. Это объясняется тем, что:

  1.  оптимизация уменьшает число проверок делителей примерно вдвое, но не устраняет накладные расходы, не зависящие от количества делителей (вызовы, проверки условий, арифметика, измерение времени);
  2.  добавляется стоимость вычисления next;
  3.  есть шум измерения и особенности runtime.
|#

#| END |#

    #| BEGIN (Введите свое решение) |#
(define (runtime) (current-milliseconds))

(define (square x) (* x x))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

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

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))
#| END |#

    #| BEGIN (Введите свое решение) |#
; !Важное уточнение! В связи с низкой точностью возвращаемого результата у runtime в реализации LISP'а от MIT, для получения видимого результата будет повторение 1000 раз. Изменена процедура start-prime-test

(define (square x) (* x x))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

(define (start-prime-test n start-time)
  (define (loop i k)
    (if (= i k)
        (report-prime (- (runtime) start-time))
        (begin
          (prime? n)
          (loop (+ i 1) k))))
  (if (prime? n)
      (loop 1 1000)
      #f))

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

; Тесты
(define (assert condition message)
  (if (not condition)
      (error message)))

(assert (= (next 2) 3) "1 test failed")
(assert (= (next 4) 6) "2 test failed")
(assert (= (smallest-divisor 4) 2) "3 test failed")
(assert (= (smallest-divisor 5) 5) "4 test failed")
(display "Tests passed")
(newline)

; Ожидаемое изменение времени выполнения: уменьшение в 2 раза

; (timed-prime-test 1009) 1009 *** 3.9999999999999994e-2
; (timed-prime-test 1013) 1013 *** .03
; (timed-prime-test 1019) 1019 *** .03
#|
Старое среднее: 0.05
Новое среднее: 0.0(3)
Отношение: 1.5
Вывод: Отклонение от ожидаемого значения
|#

; (timed-prime-test 10007) 10007 *** .11000000000000001
; (timed-prime-test 10009) 10009 *** .1
; (timed-prime-test 10037) 10037 *** .09999999999999998
#|
Старое среднее: 0.16(3)
Новое среднее: 0.10(3)
Отношение: 1.5806...
Вывод: Аналогично предыдущему выводу
|#

; (timed-prime-test 100003) 100003 *** .31
; (timed-prime-test 100019) 100019 *** .31000000000000005
; (timed-prime-test 100043) 100043 *** .31000000000000005
#|
Старое среднее: 0.52
Новое среднее: 0.31
Отношение: 1.6774...
Вывод: Отклонение незначительно уменьшилось относительно предыдущих, но все еще существенно
|#

; (timed-prime-test 1000003) 1000003 *** 1.01
; (timed-prime-test 1000033) 1000033 *** .98
; (timed-prime-test 1000037) 1000037 *** .9899999999999998
#|
Старое среднее: 1.57
Новое среднее: 0.99(3)
Отношение: 1.5805...
Вывод: Относительно предыдущих вычислений отклонение не сильно изменилось
|#

#|
Вывод: Ожидания не подтвердились, новые измерения стали в среднем в 1.5846... раз меньше по времени. Это объясняется тем, что:

  1.  оптимизация уменьшает число проверок делителей примерно вдвое, но не устраняет накладные расходы, не зависящие от количества делителей (вызовы, проверки условий, арифметика, измерение времени);
  2.  добавляется стоимость вычисления next;
  3.  есть шум измерения и особенности runtime.
|#

#| END |#

    #| BEGIN (Введите свое решение) |#
(define (runtime) (current-milliseconds))

(define (square x) (* x x))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

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

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))
#| END |#

    #| BEGIN (Введите свое решение) |#
; !Важное уточнение! В связи с низкой точностью возвращаемого результата у runtime в реализации LISP'а от MIT, для получения видимого результата будет повторение 1000 раз. Изменена процедура start-prime-test

(define (square x) (* x x))

(define (runtime) (current-milliseconds))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

(define (start-prime-test n start-time)
  (define (loop i k)
    (if (= i k)
        (report-prime (- (runtime) start-time))
        (begin
          (prime? n)
          (loop (+ i 1) k))))
  (if (prime? n)
      (loop 1 1000)
      #f))

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

; Тесты
(define (assert condition message)
  (if (not condition)
      (error message)))

(assert (= (next 2) 3) "1 test failed")
(assert (= (next 4) 6) "2 test failed")
(assert (= (smallest-divisor 4) 2) "3 test failed")
(assert (= (smallest-divisor 5) 5) "4 test failed")
(display "Tests passed")
(newline)

; Ожидаемое изменение времени выполнения: уменьшение в 2 раза

; (timed-prime-test 1009) 1009 *** 3.9999999999999994e-2
; (timed-prime-test 1013) 1013 *** .03
; (timed-prime-test 1019) 1019 *** .03
#|
Старое среднее: 0.05
Новое среднее: 0.0(3)
Отношение: 1.5
Вывод: Отклонение от ожидаемого значения
|#

; (timed-prime-test 10007) 10007 *** .11000000000000001
; (timed-prime-test 10009) 10009 *** .1
; (timed-prime-test 10037) 10037 *** .09999999999999998
#|
Старое среднее: 0.16(3)
Новое среднее: 0.10(3)
Отношение: 1.5806...
Вывод: Аналогично предыдущему выводу
|#

; (timed-prime-test 100003) 100003 *** .31
; (timed-prime-test 100019) 100019 *** .31000000000000005
; (timed-prime-test 100043) 100043 *** .31000000000000005
#|
Старое среднее: 0.52
Новое среднее: 0.31
Отношение: 1.6774...
Вывод: Отклонение незначительно уменьшилось относительно предыдущих, но все еще существенно
|#

; (timed-prime-test 1000003) 1000003 *** 1.01
; (timed-prime-test 1000033) 1000033 *** .98
; (timed-prime-test 1000037) 1000037 *** .9899999999999998
#|
Старое среднее: 1.57
Новое среднее: 0.99(3)
Отношение: 1.5805...
Вывод: Относительно предыдущих вычислений отклонение не сильно изменилось
|#

#|
Вывод: Ожидания не подтвердились, новые измерения стали в среднем в 1.5846... раз меньше по времени. Это объясняется тем, что:

  1.  оптимизация уменьшает число проверок делителей примерно вдвое, но не устраняет накладные расходы, не зависящие от количества делителей (вызовы, проверки условий, арифметика, измерение времени);
  2.  добавляется стоимость вычисления next;
  3.  есть шум измерения и особенности runtime.
|#

#| END |#

    #| BEGIN (Введите свое решение) |#
; !Важное уточнение! В связи с низкой точностью возвращаемого результата у runtime в реализации LISP'а от MIT, для получения видимого результата будет повторение 1000 раз. Изменена процедура start-prime-test

(define (square x) (* x x))

(define (runtime) (current-milliseconds))

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

(define (prime? n)
  (= n (smallest-divisor n)))

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

(define (start-prime-test n start-time)
  (define (loop i k)
    (if (= i k)
        (report-prime (- (runtime) start-time))
        (begin
          (prime? n)
          (loop (+ i 1) k))))
  (if (prime? n)
      (loop 1 1000)
      #f))

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

; Ожидаемое изменение времени выполнения: уменьшение в 2 раза

; (timed-prime-test 1009) 1009 *** 3.9999999999999994e-2
; (timed-prime-test 1013) 1013 *** .03
; (timed-prime-test 1019) 1019 *** .03
#|
Старое среднее: 0.05
Новое среднее: 0.0(3)
Отношение: 1.5
Вывод: Отклонение от ожидаемого значения
|#

; (timed-prime-test 10007) 10007 *** .11000000000000001
; (timed-prime-test 10009) 10009 *** .1
; (timed-prime-test 10037) 10037 *** .09999999999999998
#|
Старое среднее: 0.16(3)
Новое среднее: 0.10(3)
Отношение: 1.5806...
Вывод: Аналогично предыдущему выводу
|#

; (timed-prime-test 100003) 100003 *** .31
; (timed-prime-test 100019) 100019 *** .31000000000000005
; (timed-prime-test 100043) 100043 *** .31000000000000005
#|
Старое среднее: 0.52
Новое среднее: 0.31
Отношение: 1.6774...
Вывод: Отклонение незначительно уменьшилось относительно предыдущих, но все еще существенно
|#

; (timed-prime-test 1000003) 1000003 *** 1.01
; (timed-prime-test 1000033) 1000033 *** .98
; (timed-prime-test 1000037) 1000037 *** .9899999999999998
#|
Старое среднее: 1.57
Новое среднее: 0.99(3)
Отношение: 1.5805...
Вывод: Относительно предыдущих вычислений отклонение не сильно изменилось
|#

#|
Вывод: Ожидания не подтвердились, новые измерения стали в среднем в 1.5846... раз меньше по времени. Это объясняется тем, что:

  1.  оптимизация уменьшает число проверок делителей примерно вдвое, но не устраняет накладные расходы, не зависящие от количества делителей (вызовы, проверки условий, арифметика, измерение времени);
  2.  добавляется стоимость вычисления next;
  3.  есть шум измерения и особенности runtime.
|#

#| END |#