Poza nawiasem

W Ä?wiczeniu 1.10 mamy okazjÄ? zapoznaÄ? siÄ? z funkcjÄ? Ackermanna, a raczej jej odmianÄ? przygotowanÄ? przez autor??w Wizard Booka. Definicja prawdziwej funkcji Ackermanna jest trochÄ? inna, obie wersje majÄ? jednak tÄ? w??a??ciwo??Ä?, ??e rosnÄ? bardzo szybko.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

Pierwsze polecenie ka??e obliczyÄ? warto??Ä? trzech wyra??e??: (A 1 10), (A 2 4) i (A 3 3). RozwiniÄ?cia sÄ? proste, ale do??Ä? ??mudne przy obliczeniach.

• (A 1 10)
  (A 0 (A 1 9))
  (A 0 (A 0 (A 1 8)))
  (A 0 (A 0 (A 0 (A 1 7))))
  ; ...
  (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
  (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
  (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
  ; ...
  (A 0 512)
  1024
  

• (A 2 4)
  (A 1 (A 2 3))
  (A 1 (A 1 (A 2 2)))
  (A 1 (A 1 (A 1 (A 2 1))))
  (A 1 (A 1 (A 1 2)))
  (A 1 (A 1 (A 0 (A 1 1))))
  (A 1 (A 1 (A 0 2)))
  (A 1 (A 1 4))
  (A 1 (A 0 (A 1 3)))
  (A 1 (A 0 (A 0 (A 1 2))))
  (A 1 (A 0 (A 0 (A 0 (A 1 1)))))
  (A 1 (A 0 (A 0 (A 0 2))))
  (A 1 (A 0 (A 0 4)))
  (A 1 (A 0 8))
  (A 1 16)
  (A 0 (A 1 15))
  (A 0 (A 0 (A 1 14)))
  ; ...
  (A 0 32768)
  65536
  

• (A 3 3)
  (A 2 (A 3 2))
  (A 2 (A 2 (A 3 1)))
  (A 2 (A 2 2))
  (A 2 (A 1 (A 2 1)))
  (A 2 (A 1 2))
  (A 2 (A 0 (A 1 1)))
  (A 2 (A 0 2))
  (A 2 4)
  ; to juz obliczylismy w poprzednim przykladzie, wiec...
  65536
  

Druga czÄ???Ä? zadania polega na podaniu zwartej definicji matematycznej funkcji (A 0 n), (A 1 n) i (A 2 n). Definicja funkcji Ackermanna m??wi o tym, ??e (A x y) to (A (- x 1) ... przy??o??one y-razy do 2 (pomijajÄ?c przypadek, gdy y jest r??wne 0). (A 0 n) jest r??wne 2n z definicji (drugi predykat wyra??enia cond). (A 1 n) to 2n przy??o??one (n-1)-razy do 2 lub 0, gdy n jest zerem. Definicja (A 1 n) wyglÄ?da wiÄ?c nastÄ?pujÄ?co:

W podobny spos??b dochodzimy do definicji (A 2 n):

Na tym ko??czy siÄ? zadanie, ja jednak zaczÄ???em siÄ? zastanawiaÄ? nad mo??liwo??ciÄ? przyspieszenia oblicze??. Obliczenie (A 2 5) zajmuje u mnie oko??o 4.5 sekundy, co pomimo wielko??ci wyniku (19729 cyfr :-), jest wynikiem ca??kiem s??abym. PierwszÄ? my??lÄ? by??o oczywi??cie przepisanie definicji rekurencyjnej na iteracyjnÄ?. Najpierw stworzy??em pomocniczÄ? funkcjÄ? iter-fun, kt??ra symuluje rekurencyjne z??o??enie (f (f (f ... (f start)))))):

(define (iter-fun f num start)
  (if (= num 0)
      start
      (iter-fun f (- num 1) (f start))))

WykorzystujÄ?c jÄ? przepisa??em funkcjÄ? Ackermanna do nastÄ?pujÄ?cej postaci:

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        (else (iter-fun (lambda (i) (A (- x 1) i))
                        (- y 1)
                        2))))

Z nowÄ? definicjÄ? na czasie obliczenia (A 2 5) zyska??em tylko oko??o p???? sekundy. To wciÄ??? dawa??o jednak wynik w okolicach 3.9 sekundy. Dla por??wnania, ten sam algorytm zapisany w Pythonie wykonuje siÄ? u mnie przez 1.2 sekundy.

def iter_fun(f, num, start):
    for i in xrange(num):
        start = f(start)
    return start
 
def A(x, y):
    if y == 0:
        return 0
    elif x == 0:
        return 2*y
    else:
        return iter_fun(lambda i: A(x-1, i), y-1, 2)

WiÄ?c jednak z tym kodem nie jest tak ??le. Mo??na jednak trochÄ? oszukaÄ? i wykorzystujÄ?c matematyczne definicjÄ? funkcji A(0,n) i A(1,n) zapisaÄ? kod w taki spos??b:

(define (A x y)
  (define (A0 n)
    (* 2 n))
  (define (A1 n)
    (if (= n 0)
        0
        (expt 2 n)))
  (cond ((= y 0) 0)
        ((= x 0) (A0 y))
        ((= x 1) (A1 y))
        (else (iter-fun (lambda (i) (A (- x 1) i))
                        (- y 1)
                        2))))

Ten kod generuje poprawnÄ? warto??Ä? wyra??enia (A 2 5) w niezmierzalnie ma??ym czasie. TestujÄ?c go dla du??ych warto??ci (A 1 n) mo??na przekonaÄ? siÄ? o tym, ??e MzScheme ma lepiej napisanÄ? arytmetykÄ? du??ych liczb od Pythona (a co najmniej ich potÄ?gowanie). To, co mnie jednak najbardziej zastanowi??o, to r????nica w wydajno??ci pomiÄ?dzy wersjami 2.3 i 2.4 Pythona. Oto bezpo??rednie wyniki uzyskane z interpreter??w MzScheme 301, Pythona 2.3 i Pythona 2.4:

MzScheme 301

> (time (expt 2 100000000))
cpu time: 568 real time: 570 gc time: 420

Python 2.3

Python 2.3.5 (#2, Mar  6 2006, 10:12:24)
[GCC 4.0.3 20060304 (prerelease) (Debian 4.0.2-10)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import timeit
>>> a = timeit.Timer('2**100000000')
>>> a.timeit(1)
5.5458259582519531

Python 2.4

Python 2.4.2 (#2, Nov 20 2005, 17:04:48)
[GCC 4.0.3 20051111 (prerelease) (Debian 4.0.2-4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import timeit
>>> a = timeit.Timer('2**100000000')
>>> a.timeit(1)
13.069931030273438

Pythonowy modu?? timeit zwraca czas w sekundach, a funkcja MzScheme time w milisekundach. R????nica wiÄ?c jest wyra??nie widoczna, dlaczego jednak nowsza wersja Pythona dzia??a ponad dwa razy wolniej od wersji wcze??niejszej?