Fibonacci sequence: Difference between revisions
Add bruijn
(Add bruijn) |
|||
Line 3,657:
{true? x < 2, x, { cache[x] = fibonacci(x - 1) + fibonacci(x - 2) }}
}</syntaxhighlight>
=={{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>
=={{header|Burlesque}}==
| |||