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

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

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

• По-перше, цій фічі менше 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. А що є в С ХЗ, непотрібно було.