SICP по-русски

Отличие реализации Хьюго в том, что на каждом шаге (expmod) для четного показателя степени вызывает себя с вдвое меньшим показателем не один раз, а два.

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

Про алгоритм Хюго можно записать:

1. C(2n) = 2 C(n) + A₁, где A₁- некая константа, не зависящая от n,
2. C(2n+1) = C(2n) + A₂, где A₂ некая константа, не зависящая от n.
3. С(0) = A₃, где A₃ некая константа, не зависящая от n.

Мы хотим показать, что для любого n выполняется соотношение (*) C(n) = C₁n + C₂, где C₁ и C₂ - константы.

Воспользуемся методом математической индукции.

В качестве базы индукции возьмем n=0. В этом случае соотношение (*) истинно в силу 3-го пункта описания алгоритма Хьюго.

Предположим, что для всех k от 0 до n-1 соотношение (*) выполняется и докажем его истинность при k=n. Рассмотрим отдельно случай нечетного и четного n.

Начнем с нечетного n = 2 m + 1. В этом случае по пункту 2 получаем:

С(n) = C(2m+1) = C(2m) + A₂ =  2 C₁ m + C₂ + A₂  (согласно индуктивного предположения, так как 2m < 2m+1 = n) =  C₁ (2m+1) + (C₂ + A₂ - C₁) = C₁n + (C₂ + A₂ - C₁)  - получили требуемый линейный вид.

Теперь перейдем к случаю четного  n = 2 m. Для этого случая по пункту 1 получаем:

C(n) = C(2m) = 2 C(m) + A₁ = 2 (C₁m + C₂) + A₁ (согласно индуктивного предположения, так как m < 2m = n) =  C₁2m + (2C₂ + A₁)  =  C₁n + (2C₂ + A₁)  - вновь получили линейный вид, к которому стремились.

Таким образом, согласно принципу математической индукции, мы доказали, что процесс, порождаемый процедурой Хьюго, имеет порядок Θ(n), а не Θ(log n).

Хьюго стоит хорошо подумать о вреде дублирования кода.