SICP по-русски

Упражнение по написанию процедуры, вычисляющей произведение полезное, но несложное, так как аналогии с суммированием просматриваются очень легко. Все понимают, что роль операции + из суммирования в умножении выполняет операция *. Роль нуля выполняет единица. Те, кто изучал линейную алгебру, вообще особой разницы между сложением и умножением не видят
Итак, процедуру product можно записать […]

Это тот случай, когда любые пояснения будут лишними.
(define (sum term a next b)
    (define (iter a result)
      (if (> a b)
          result
          (iter (next a) (+ result (term a)))))
    (iter a 0))
Если что-то непонятно, комментируйте.

Итак, мы переходим к упражнениям раздела 1.3, в котором речь идет о процедурах высших порядков. Поддержка процедур высших порядков и вообще работа с процедурами как с данными является очень мощным средством построения абстракций. В упражнениях мы как раз этими абстракциями и займемся.
Реализация формулы Симпсона для вычисления определенного интеграла выглядит следующим образом:
(define (simpson f a b n)
  […]

Это упражнение немного заковыристо сформулировано, но сложным не является.
Вот код модифицированной процедуры expmod, которая сигнализирует о нахождении нетривиального квадратного корня из 1, возвращая 0 (как и рекомендовано в условии).
(define (square x)
  (* x x))
(define (apply-trivial-check k m r)
  (if (and (not (= k 1))
           (not (= k (- m 1)))
           (= r 1))
      0
      r))
(define […]

Совершенно случайно наткнулся на новый сайт, посвященный решению упражнений из SICP и обсуждению книги. Сайт называется SICP Wiki и появился в сентябре этого года (совсем свеженький). На данный момент доступны решения большинства упражнений из первой главы и части упражнений из второй.
Мне очень понравилось внутреннее устройство сайта, то, что он построен на базе вики и рассчитан […]

Код процедуры проверки приведен ниже. Процедура называется (test-all) и принимает один параметр - число для проверки на простоту.
(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 (test […]

Отличие реализации Хьюго в том, что на каждом шаге (expmod) для четного показателя степени вызывает себя с вдвое меньшим показателем не один раз, а два.
Пусть C(n) - число операций, необходимых для вычисления (expmod n exp m). Покажем, что для реализации Хьюго C(n) растет как линейная функция, а не логарифм.
Про алгоритм Хюго можно записать:

C(2n) = 2 C(n) + […]

Идея Алисы проста и понятна. Более того, ее вариант процедуры (expmod) выдает те же результаты, что и исходный. Но в нем есть проблема, имя которой - эффективность.
Количество операций, производимых при вычислении по обеим процедурам, будет примерно одинаковым (иметь один порядок роста) только в том случае, если элементарные функции, такие как * и remainder, выполняются за […]

Это упражнение также базируется на упражнении 22, так что изучите его до того, как переходить к этому.
Для замеров времени в этом упражнении я применю несколько другую технику. Если в упражнении 22 я выбрал большие числа, то в данном случае достаточно будет просто задать в (fast-prime?) достаточно большое число прогонов теста Ферма и работать с числами порядка […]

Это упражнение является логическим продолжением предыдущего упражнения 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)))))

 
Результаты запусков тестов из предыдущего […]