Rosetta Code

Fibonacci sequence: Difference between revisions

Page Discussion

Fibonacci sequence (view source)

Revision as of 12:27, 8 October 2017

119 bytes removed ,  6 years ago
no edit summary
No edit summary
No edit summary
Line 4,903:
 
=={{header|lambdatalk}}==
(Following Scheme)
<lang scheme>▼
 
▲<lang scheme>
1) basic version (obvioulsy very very slow)
1) basic version
{def fibfib1
{lambda {:n}
{if {< :n 13}
then 1
else {+ {fibfib1 {- :n 1}} {fibfib1 {- :n 2}}} }}}
 
{fib1 16} -> 987 (CPU ~ 16ms)
2) tail-recursive version (very fast)▼
{fib1 30} = 832040 (CPU > 12000ms)
{def fib▼
 
{def fib.r ▼
▲2) tail-recursive version (very fast)
▲{def fibfib2
▲ {def fibfib2.r
{lambda {:a :b :i}
{if {< :i 1}
then :a
else {fibfib2.r :b {+ :a :b} {- :i 1}} }}}
{lambda {:n} {fibfib2.r 0 1 :n}}}
 
{fib2 16} -> 987 (CPU ~ 1ms)
3) Dijkstra Algorithm (very fast)▼
{fib2 30} -> 832040 (CPU ~2ms)
{def fib▼
{fib2 1000} -> 4.346655768693743e+208 (CPU ~ 22ms)
{def fib.r▼
 
▲3) Dijkstra Algorithm (very fast)
▲{def fibfib3
▲ {def fibfib3.r
{lambda {:a :b :p :q :count}
{if {= :count 0}
then :b
else {if {= {% :count 2} 0}
then {fibfib3.r :a :b
{+ {* :p :p} {* :q :q}}
{+ {* :q :q} {* 2 :p :q}}
{/ :count 2}}
else {fibfib3.r {+ {* :b :q} {* :a :q} {* :a :p}}
{+ {* :b :p} {* :a :q}}
:p :q
{- :count 1}} }}}}
{lambda {:n}
{fibfib3.r 1 0 0 1 :n} }}
 
{fib3 16} -> 987 (CPU ~ 2ms)
4) with memoization (slow, doesn't work as expected. Need help!)
{fib3 30} -> 832040 (CPU ~ 2ms)
{def mfib
{fib3 1000} -> 4.346655768693743e+208 (CPU ~ 3ms)
{def mfib.r
{lambda {:n :memo}
{if {< :n 2}
then 1
else {if {< :n {array.length :memo}}
then {array.get :memo :n}
else {let { {:n :n}
{:memo {array.set! :memo :n
{+ {mfib.r {- :n 1} :memo}
{mfib.r {- :n 2} :memo}}} }}
{array.get :memo :n} } }}}}
{lambda {:n}
{mfib.r :n {array}} }}
 
54) Binet's formula (non recursive)
{def fibfib4
{lambda {:n}
{let { {:n :n} {:sqrt5 {sqrt 5}} }
{round {/ {- {pow {/ {+ 1 :sqrt5} 2} :n}
{pow {/ {- 1 :sqrt5} 2} :n}} :sqrt5}}} }}
</lang>▼
 
 
{fib4 16} -> 987 (CPU ~ 1ms)
{fib4 30} -> 832040 (CPU ~ 1ms)
{fib4 1000} -> 4.346655768693743e+208 (CPU ~ 1ms)
 
▲</lang>
 
=={{header|Lasso}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/62701"