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

[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

[euthanasepam]

Цей гарнесенький алгоритм із сайту Rosetta Code буде так само нескінченно довго рахувати 64-е число Фібоначчі, якщо переписати на Сі чи на Фортран.

[balu]

От ти сам і відповів на своє питання :) Проблема в алгоритмові, а не в підході (ФП).

[euthanasepam]

Проблема, звісно, в алгоритмі.

Але є ще одна проблема — в доречності використання рекурсії у таких випадках. Процесор не знає ні про жодні рекурсії та не вміє їх рахувати. Він тупий і не знає вищої математики, абстракцій, алгоритмів тощо. ФП, ООП і таке інше — лише «синтаксичний цукор» для зручності людей. А на рівні процесора сам знаєш що: нулі та одиниці та прості операції.

Отже, маємо такий алгоритм. Він починає істотно і помітно неозброєним оком тупити десь із 35-го числа. Після 45-го це вже забавки для фанатичних слоупокерів. Скільки воно буде рахувати після 50-го, я не знаю, а скільки буде для 50-го на моєму комп’ютері — напишу пізніше, я саме запустив. :)


P. S.

Порахувало:

real    6m14,898s
user    0m0,000s
sys     0m0,062s

P. S.

Порахувало для 51-го:

real    9m56,589s
user    0m0,000s
sys     0m0,062s

P. S.

І для 52-го:

real    16m12,635s
user    0m0,000s
sys     0m0,078s

Думаю, зрозуміло, що далі буде лише гірше. :)

[balu]

Але є ще одна проблема — в доречності використання рекурсії у таких випадках.

На невеликих наборах даних рекурсія дозволяє зробити програму яснішою. У цьому її сенс. І кожен притомний спеціаліст знає про те, що алгоритми на ній просідають по перфомансу. Це для заліза загального призначення, звісно. Можливо, якесь спеціалізоване вміє оптимізувати рекурсію. Х.З.

[euthanasepam]

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

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

F_previous = 0
F_next = 1

limit = int(input("Enter the natural number: "))
limit = limit + 1

for counter in range(int(0), int(limit)):
    F_new = F_previous
    F_previous = F_next
    F_next = F_new + F_previous

print("{}th Fibonacci number = {}". format(counter, F_new))

Просто, швидко і рахує правильно. Примітивно? Без модних штучок-дрючок? То й нехай. :)


P. S.

Там у них є купа інших варіянтів, але я хотів якомога точнішої відповідності до того ітеративного, що вже маю на Паскалі.

[euthanasepam]

Ще для порівняння ітеративно порахуймо на Пітоні 100500-е число:

time python3 Fibonacci_number.py

[ Тут дуже велике число результату: 23003 знака ]

real    0m3,106s
user    0m0,436s
sys     0m0,077s

[euthanasepam]

Поставлю на ніч паскалівську рекурсію: хай рахує для 64-го числа. :)


P. S.

Досі рахує.

Коли закінчить рахувати, якщо я того дочекаю, то напишу. :)



P. S.

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

10610209857723

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

[balu]

Ну ти й терплячий

[euthanasepam]

Воно ж собі крутиться, їсти не просить, а комп’ютер я не вимикаю.

Результат красномовний.

Як хтось розумний казав — чи то Кнут, чи то Вірт, — що простий і «тупий» алгоритм зазвичай кращий за кручений та вишуканий.

[balu]

алгоритм

Але не цього разу :). Бо найпростіший алгоритм якраз рекурсивний.

[balu]

До речі, не факт, що Сішечка стільки рекурсії витримає.

[euthanasepam]

В цьому сенсі Сішечка нічим не відрізняється від Паскалю.

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

[balu]

У мене з функціональщини тільки Emacs Lisp 😁. Але навряд чи він осилить таке число без бубна. Точніше, порахує він швидше, тільки результат буде дивним. Я так думаю 😁.

[euthanasepam]

Для Windows є безкоштовні ліспи:

Corman Lisp, github.com/sharplispers/cormanlisp

LispWorks, www.lispworks.com



Щодо алгоритмів, то є там само, де й паскалівський:

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

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

Я ще не пробував, тож не скажу, як воно.

[balu]

Безкоштовних ліспів під що хочеш вистачає. Я на Андроїді, наприклад, бавлюся. Але ємаксовський найбільш практичний для моїх потреб.

[balu]

Щодо числа, то, по-ідеї, int в ємакс, обмежено unsigned long long. Для С повинні бути якісь ліби для роботи з більшими числами, але я з цим не стикався. Натомість, python автоматично розширяє пам'ять, щоб вмістити число.

[euthanasepam]

От за це люди й полюбили Пітон: можна рахувати страшенну математику без вагітної голови.

Цікаво, до речі, як воно влаштовано і який має вигляд «під капотом».

[balu]

C там під капотом, математичні пакети саме на ньому і написані :) Але Пітон та швидкість, то речі погано сумісні. Я коли робив обробку текстів, то Пітон просідав раза в три ємаксу (правда скомпільованому). А найкращий результат був у grep/sed/awk.

[euthanasepam]

Та я не про те… Цікаво, як влаштовано роботу з великими числами. Треба десь пошукати часу і натхнення, щоб зазирнути під той капот.

[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 я не пробував, бо не знаю. Ймовірно, що має бути швидким Форт, бо стекова машина й ото всьо. Випробую, коли буду мати час і натхнення.

[balu]

Не думаю, що саме через це.

• По-перше, цій фічі менше 10-ти років.
• По-друге, у python є кілька дуже вдалих моментів: це цукор для списків та словників, foreach, слайси, імпорт та мінімум бюрократії. Це дозволяє легко його використовувати непрограмістам.
• По-третє, він був частиною дистрибутивів з маком включно, а науковці часто сидять саме на якихось ніксах. От і отримали на халяву простий інструмент.

---

Такі великі числа мало кому цікаві. Мені, за 25 років практики, тільки пару раз long не вистачило. І таких — переважна більшість. А от науковцям воно потрібно.

[euthanasepam]

> А от науковцям воно потрібно.


Отож.

Бо дивимось ув інші мови і бачимо там таке:

https://classic.startpage.com/do/asearch?q=pascal+largest+integer

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



> Такі великі числа мало кому цікаві.


Мені цікаві: це найперше, на що я дивлюся, коли дивлюся на якийсь інтерпретатор чи компілятор.

[euthanasepam]

Косячная арифметика

http://www.freepascal.ru/article/freepascal/20181215220000

[balu]

А що, в літературі по Паскалю не кажуть про ці проблеми?

[euthanasepam]

Відверто кажучи, я не знаю. Щось про Паскаль я читав років мало не зо тридцять тому і давно все забув. Тепер знов читаю, але вже інше, сучасніше, про Free Pascal.

Нещодавно я в одному журналі з подивом читав, що працевлаштовані у великих ΙΤ-компаніях люди бува не знають про IEEE 754.


Часто в йойтішних книжках пишуть ото як ти кажеш: вам не треба тої довгої арифметики, то ми про неї не пишемо. Або й нічого про неї не згадують.

[balu]

В книжках по С та Java пишуть, що буде якщо помилишся з діапазонами. Ну і в Java є BigNum. А що є в С ХЗ, непотрібно було.

[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, але, наразі, щось там потрібно додатково включати.

[balu]

Втім:

ELISP> integer-width
65536 (#o200000, #x10000)
ELISP> (setq integer-width 131072)
131072 (#o400000, #x20000)
ELISP> (benchmark 1 (fibonacci 100500))
"Elapsed time: 0.000003s"

Вивело 21003 знаків.

---

Твій варіант на python:

real    0m0,112s
user    0m0,088s
sys 0m0,004s

Результати ті ж.

[balu]

Ще тупіший алгоритм:

(require 'cl)

(defun fib-loop (num)
  (cl-do ((n 0 (1+ n))
       (cur 0 next)
       (next 1 (+ cur next)))
      ((= num n) cur)))

ELISP> (benchmark 1 (fib-loop 100500))
"Elapsed time: 0.000002s"

[euthanasepam]

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