SICP по-русски

Итак, у нас вновь сравнение нормального и аппликативного порядков вычислений. В данном случае речь идет об эффективности. Сначала набросаем процесс для нормального порядка (знаком > отмечается текущее количество выполненных операций 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 раза.

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