Fibonacci sequence: Difference between revisions

=={{header|Bruijn}}==

<syntaxhighlight lang="bruijn">

:import std/Combinator .

:import std/Math .

:import std/List .

# unary/Church fibonacci (moderately fast but very high space complexity)

fib-unary [0 [[[2 0 [2 (1 0)]]]] k i]

:test (fib-unary (+6u)) ((+8u))

# ternary fibonacci using infinite list iteration (very fast)

fib-list \index fibs

fibs head <$> (iterate &[[0 : (1 + 0)]] ((+0) : (+1)))

:test (fib-list (+6)) ((+8))

# recursive fib (very slow)

fib-rec y [[0 <? (+1) (+0) (0 <? (+2) (+1) rec)]]

rec (1 --0) + (1 --(--0))

:test (fib-rec (+6)) ((+8))

</syntaxhighlight>

Performance using <code>HigherOrder</code> reduction without optimizations:

<syntaxhighlight>

> :time fib-list (+1000)

0.9 seconds

> :time fib-unary (+50u)

1.7 seconds

> :time fib-rec (+25)

5.1 seconds

> :time fib-list (+50)

0.0006 seconds

</syntaxhighlight>