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

11 October, 2007 (23:27) | Решения упражнений

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

Количество операций, производимых при вычислении по обеим процедурам, будет примерно одинаковым (иметь один порядок роста) только в том случае, если элементарные функции, такие как * и remainder, выполняются за время, не зависящее от значений своих аргументов. Но это не так, ведь это операции над числами произвольного размера, поддержка таких операций отсутствует на уровне процессора/сопроцессора. Следовательно каждая подобная операция не элементарна, а влечет выполнение некоторой процедуры, время работы которой увеличивается с ростом чисел, над которыми выполняется операция.

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

Comments

Comment from shini
Date: May 10, 2013, 8:58 pm

Количество операций, производимых при вычислении по обеим процедурам, будет примерно одинаковым (иметь один порядок роста) только в том случае, если элементарные функции, такие как * и remainder, выполняются за время, не зависящее от значений своих аргументов.

Поправьте меня, если я не прав, но количество операций не будет одинаковым.
Код из оригинальной книги.

(define (expmod base exp m)
(remainder (fast-expt base exp) m))

(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))

Вариант Алисы (выше).

(define (expmod_2 base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod_2 base (/ exp 2) m))
m))
(else
(remainder (* base (expmod_2 base (- exp 1) m))
m))))

Версия из книги.
Давайте пошагово пройдемся по процедуре Алисы с аргументами,к примеру, 23 5 5.
(expmod 23 5 5)
[0] (expmod 23 5 5)
[1] (remainder ( * 23 (expmod 23 4 5)) 5)
[2] (remainder ( * 23 (square (expmode 23 2 5))) 5)
[3] (remainder ( * 23 (square (square (expmode 23 1 5))))5)
[4] (remainder ( * 23 (square (square ( * 23 (expmode 23 0 5))))) 5)
[5] (remainder ( * 23 (square (square ( * 23 ( * 1))))) 5)
Для вычисления алгоритма Алисы надо 5 операций.
[1] 23 * 1
[2] square 23
[3] square 529
[4] 279841 * 23
[5] remainder 6436343 5
[6] 3

Для примера из книги :
[0] (expmode 23 5 5)
[1] (remainder (* 23 (expmode 23 4 5)) 5)
[2] (remainder (* 23 (remainder (square (expmode 23 2 5))5))5)
[3] (remainder (* 23 (remainder (square (remainder (square (expmode 23 1 5))5))5))5)
[5] (remainder (* 23 (remainder (square (remainder (square (remainder(* 23 (expmode 23 0 5))) 5))5))5)
[6] (remainder (* 23 (remainder (square (remainder (square (remainder (* 23 (* 1)))5 ))5))5)
Теперь посчитаем количество операций в данном примере:
[1] 23 *1
[2] remainder 23 5
[3] square 3
[4] remainder 9 5
[5] square 4
[6] remainder 16 5
[7] 23 * 1
[8] remainder 23 5
[9] 3
Только после 8 операции у нас выйдет ответ.Всё из-за процедуры remainder которая будет повторятся каждый раз после операций со степенем (exp).
Порядок роста операций из первого примера(примера Алисы) = (количество_операций_со_степенем)+1
Порядок роста операций из второго примера = (количество_операций_со_степенем) * 2

Comment from AlexF
Date: September 1, 2015, 1:48 am

А кто-нибудь может объяснить почему в алгоритме Алисы процедура remainder вызывается 1 раз. А в expmod каждый раз.

Comment from pamm
Date: May 25, 2016, 1:19 pm

shini, ну так автор и не говорит что оно будет одинаковым, 5 и 6 операции в алгоритме Лизы (у меня в книге она именно Лиза) работают с длинными числами, а если количество битовых разрядов в числе будет превышать максимальную длину числа обрабатываемого за 1 раз, то это уже не будет элементарная операция (операция выполняемая за 1 раз) и мы не сможем написать 5 и 6, а будем писать 5, 5.1, 6, 6.1… Как я понимаю (могу ошибаться).

AlexF а что объяснять? Это два по-разному написанных алгоритма. Посмотри выше как работает процедура expmod в каждом из них, где именно рекурсия возникает.

Знаю, что пишу в пустоту :)

Write a comment