Пролетарська рекурсія за ваш рахунок

[euthanasepam]

 

На популярному сайті Rosetta Code з прикладами програм на розмаїтих програмувальних мовах є зразки вирішення всіляких типових математичних, алгоритмічних і хтозна ще яких проблем.

Погляньмо, наприклад, на рекурсивний пошук якогось числа у послідовності Фібоначчі, запрограмований мовою Паскаль:

http://rosettacode.org/wiki/Fibonacci_sequence#Pascal

function fib(n: integer): integer;
  begin
    if (n = 0) or (n = 1)
      then
        fib := n
      else
        fib := fib(n-1) + fib(n-2)
  end;

Гарно? Авжеж. Вельми гарно. Тішить серце і милує око.

Але коли ви цей алгоритм відкомпілюєте і запустите на виконання для числа, скажімо, 64, то встигнете посивіти поснідати й випити горнятко кави, а може й не одне. Дуже, дуже, дуже довго… Про якісь справді великі числа в цьому випадку говорити зайве.

Для порівняння: ітеративний алгоритм працює блискавично навіть для досить великих чисел, що вмістяться у комп’ютерну пам’ять.


Отож, мораль: коли вам якесь занюхане чмо велемудре цабе каже, що воно вміє рахувати всілякі математичні фокуси рекурсивно і функціонально, ви теє цабе негайно пиздіть по мармизі та женіть із хати геть. Бо якщо воно почне писати для вас програми, то буде вам клопіт, і горе, і видатки.



P. S.

Нарешті порахувало для 64:

10610209857723

real    5257m47,799s
user    0m0,000s
sys     0m0,015s

 

Comments

[balu]

Спробував піпіськомірку на ванільному ємаксі:

(defun fibonacci (n)
  (let ( (vec) (i) (j) (k) )
    (if (< n 2) n
      (progn
          (setq vec (make-vector (+ n 1) 0) i 0 j 1 k 2)
          (setf (aref vec 1) 1)
          (while (<= k n)
            (setf (aref vec k) (+ (elt vec i) (elt vec j) ))
            (setq i (+ 1 i) j (+ 1 j) k (+ 1 k) ))
          (elt vec n) ))))

ELISP> (benchmark 1 (fibonacci 94000))
"Elapsed time: 0.000002s"
ELISP> (benchmark 1 (fibonacci 95000))
*** Eval error ***  Arithmetic overflow error

Вивело 18809 знаків. В принципі, ємакс навчився і bignum, такий як у python, але, наразі, щось там потрібно додатково включати.