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

1 September, 2007 (18:53) | Решения упражнений

Итак, у нас вновь сравнение нормального и аппликативного порядков вычислений. В данном случае речь идет об эффективности. Сначала набросаем процесс для нормального порядка (знаком > отмечается текущее количество выполненных операций remainder:

>0
(gcd 206 
     40)
>0
(if (= 40 0) 
    206 
    (gcd 40 
         (remainder 206 
                    40)))
>0
(gcd 40 
     (remainder 206 
                40)))
>0
(if (= (remainder 206 
                  40) 
       0) 
    40 
    (gcd (remainder 206 
                    40) 
         (remainder 40 
                    (remainder 206 
                               40))))
>0+1=1
(if (= 6 
       0) 
    40 
    (gcd (remainder 206 
                    40) 
         (remainder 40 
                    (remainder 206 
                               40))))
>1
(gcd (remainder 206 
                40) 
     (remainder 40 
                (remainder 206 
                           40))))
>1
(if (= (remainder 40 
                  (remainder 206 
                             40)) 
       0) 
    (remainder 206 
               40)) 
    (gcd (remainder 40 
                    (remainder 206 
                               40)) 
         (remainder (remainder 206 
                               40) 
                    (remainder 40 
                               (remainder 206 
                                          40)))))
>1+2=3
(if (= 4) 
       0) 
    (remainder 206 
               40)) 
    (gcd (remainder 40 
                    (remainder 206 
                               40)) 
         (remainder (remainder 206 
                               40) 
                    (remainder 40 
                               (remainder 206 
                                          40)))))
>3
(gcd (remainder 40 
                (remainder 206 
                           40)) 
     (remainder (remainder 206 
                           40) 
                (remainder 40 
                           (remainder 206 
                                      40)))))
>3
(if (= (remainder (remainder 206 
                             40) 
                  (remainder 40 
                             (remainder 206 
                                        40))) 
       0) 
    (remainder 40 
               (remainder 206 
                          40)) 
    (gcd (remainder (remainder 206 
                               40) 
                    (remainder 40 
                               (remainder 206 
                                          40))) 
         (remainder (remainder 40 
                               (remainder 206 
                                          40)) 
                    (remainder (remainder 206 
                                          40) 
                               (remainder 40 
                                          (remainder 206 
                                                     40)))
>3+4=7
(if (= 2) 
       0) 
    (remainder 40 
               (remainder 206 
                          40)) 
    (gcd (remainder (remainder 206 
                               40) 
                    (remainder 40 
                               (remainder 206 
                                          40))) 
         (remainder (remainder 40 
                               (remainder 206 
                                          40)) 
                    (remainder (remainder 206 
                                          40) 
                               (remainder 40 
                                          (remainder 206 
                                                     40)))
>7
(gcd (remainder (remainder 206 
                           40) 
                (remainder 40 
                           (remainder 206 
                                      40))) 
     (remainder (remainder 40 
                           (remainder 206 
                                      40)) 
                (remainder (remainder 206 
                                      40) 
                           (remainder 40 
                                      (remainder 206 
                                                 40)))
>7
(if (= (remainder (remainder 40 
                             (remainder 206 
                                        40)) 
                  (remainder (remainder 206 
                                        40) 
                             (remainder 40 
                                        (remainder 206 
                                                   40)))) 
       0) 
    (remainder (remainder 206 
                          40) 
               (remainder 40 
                          (remainder 206 
                                     40))) 
    (gcd (remainder (remainder 206 
                               40) 
                    (remainder 40 
                               (remainder 206 
                                          40))) 
         (remainder (remainder 40 
                               (remainder 206 
                                          40)) 
                    (remainder (remainder 206 
                                          40) 
                               (remainder 40 
                                          (remainder 206 
                                                     40))))))
>7+7=14   
(if (= 0 
       0) 
    (remainder (remainder 206 
                          40) 
               (remainder 40 
                          (remainder 206 
                                     40))) 
    (gcd (remainder (remainder 206 
                               40) 
                    (remainder 40 
                               (remainder 206 
                                          40))) 
         (remainder (remainder 40 
                               (remainder 206 
                                          40)) 
                    (remainder (remainder 206 
                                          40) 
                               (remainder 40 
                                          (remainder 206 
                                                     40)))))) 
>14
(remainder (remainder 206 
                      40) 
           (remainder 40 
                      (remainder 206 
                                 40)))
>14+4=18
2

Всего, таким образом, операция remainder выполняется 18 раз.

Теперь перейдем к аппликативному процессу:

>0
(gcd 206 
     40)
>0
(if (= 40 
       0) 
    206 
    (gcd 40 
         (remainder 206 
                    40)))
>0
(gcd 40 
     (remainder 206 
                40)))
>0+1=1
(gcd 40 
     6)
>1
(if (= 6 
       0) 
    40 
    (gcd 6 
         (remainder 40 
                    6)))
>1
(gcd 6 
     (remainder 40 
                6)))
>1+1=2
(gcd 6 
     4)
>2
(if (= 4 
       0) 
    6 
    (gcd 4 
         (remainder 6 
                    4)))
>2
(gcd 4 
     (remainder 6 
                4)))
>2+1=3
(gcd 4 
     2)
>3
(if (= 2 
       0) 
    4 
    (gcd 2 
         (remainder 4 
                    2)))
>3
(gcd 2 
     (remainder 4 
                2)))
>3+1=4
(gcd 2 
     0)
>4
(if (= 0 
       0) 
    2 
    (gcd 0 
         (remainder 2 
                    0)))
>4
2

Общее число выполнений операции remainder в этом случае – 4 раза.

Как видим, аппликативный процесс существенно более эффективен.

Comments

Comment from Alex K
Date: April 13, 2008, 7:18 pm

Привет, там вроде бы просили

Using the substitution method (for normal order), illustrate the process generated in evaluating (gcd 206 40) and indicate the remainder operations that are actually performed.

Если посмотреть на substitution method (1.1.5) то он от applicative метода отличается только тем, что “разворачивает” функции. Я сначала тоже хотел так подставлять, а потом перечитал и задумался 🙂 Может я не прав, конечно 🙂

Comment from Spok
Date: November 14, 2013, 1:09 pm

Некропост 🙂

Кстати да. В книге сказано что нормальный порядок – это таки “полное развертывание, затем редукция”. И по моим подсчетам получилось, что при нормальном порядке вычисления, процедура remainder выполнится 11 раз.

Comment from Yasheriza
Date: May 28, 2017, 5:32 pm

Супернекропост

to Spok

В отличие от автора решения, вы не удосужились посчитать количество процедур в предикате if. Там их как раз 7 штук скапливается. 11 + 7 = 18

Write a comment