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

[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]

https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

[euthanasepam]

Я маю на увазі конкретну реалізацію у програмних алгоритмах, а не теорію. Зокрема, як це зроблено в Пітоні — бо мені подобається те, як воно працює.

Для багатьох програмувальних мов довга арифметика є лише у сторонніх бібліотеках і відтак відсутня в інсталяції:

http://rosettacode.org/wiki/Arbitrary-precision_integers_(included)


GMP — це 4 МБ розпакованих файлів. Звісно, програмного тексту в кілька разів менше, але є що читати.

DelphiBigNumbers (BigInteger, BigDecimal and BigRational for Delphi) теж доволі великий.

А от Big Decimal Math — це фактично один файл bigdecimalmath.pas обсягом 82 КБ.

[balu]

Пітон автоматично вижирає пам'ять, якщо у цьому є потреба. Мені цей підхід якось не дуже подобається. Бо так можна вижрати багацько пам'яті, варто лише помилитися в алгоритмі.

Since large bignums consume a lot of memory, Emacs limits the size of the largest bignum a Lisp program is allowed to create.

Я допускаю, що десь можуть знадобитися такі цифри, але 18000+ знаків з коробки це більш ніж досить. А треба більше, просто збільши значення змінної.

[euthanasepam]

lurkmore.to/Число_Грэма

ru.wikipedia.org/wiki/Число_Грэма

[euthanasepam]

Пітон дає результат, і досить швидко. Я використовував базову інсталяцію без додаткових наукових бібліотек. Пітон рахує найшвидше з тих інтерпретувальних мов, які я пробував. Tcl троха повільніший, але теж працює перфектно. Perl 5 (Math::BigInt) суттєво повільніший (в рази). Ruby я не пробував, бо не знаю. Ймовірно, що має бути швидким Форт, бо стекова машина й ото всьо. Випробую, коли буду мати час і натхнення.