83 lines
2.9 KiB
Plaintext
83 lines
2.9 KiB
Plaintext
1) basic version
|
|
{def fib1
|
|
{lambda {:n}
|
|
{if {< :n 3}
|
|
then 1
|
|
else {+ {fib1 {- :n 1}} {fib1 {- :n 2}}} }}}
|
|
|
|
{fib1 16} -> 987 (CPU ~ 16ms)
|
|
{fib1 30} = 832040 (CPU > 12000ms)
|
|
|
|
2) tail-recursive version
|
|
{def fib2
|
|
{def fib2.r
|
|
{lambda {:a :b :i}
|
|
{if {< :i 1}
|
|
then :a
|
|
else {fib2.r :b {+ :a :b} {- :i 1}} }}}
|
|
{lambda {:n} {fib2.r 0 1 :n}}}
|
|
|
|
{fib2 16} -> 987 (CPU ~ 1ms)
|
|
{fib2 30} -> 832040 (CPU ~2ms)
|
|
{fib2 1000} -> 4.346655768693743e+208 (CPU ~ 22ms)
|
|
|
|
3) Dijkstra Algorithm
|
|
{def fib3
|
|
{def fib3.r
|
|
{lambda {:a :b :p :q :count}
|
|
{if {= :count 0}
|
|
then :b
|
|
else {if {= {% :count 2} 0}
|
|
then {fib3.r :a :b
|
|
{+ {* :p :p} {* :q :q}}
|
|
{+ {* :q :q} {* 2 :p :q}}
|
|
{/ :count 2}}
|
|
else {fib3.r {+ {* :b :q} {* :a :q} {* :a :p}}
|
|
{+ {* :b :p} {* :a :q}}
|
|
:p :q
|
|
{- :count 1}} }}}}
|
|
{lambda {:n}
|
|
{fib3.r 1 0 0 1 :n} }}
|
|
|
|
{fib3 16} -> 987 (CPU ~ 2ms)
|
|
{fib3 30} -> 832040 (CPU ~ 2ms)
|
|
{fib3 1000} -> 4.346655768693743e+208 (CPU ~ 3ms)
|
|
|
|
4) memoization
|
|
{def fib4
|
|
{def fib4.m {array.new}} // init an empty array
|
|
{def fib4.r {lambda {:n}
|
|
{if {< :n 2}
|
|
then {array.get {array.set! {fib4.m} :n 1} :n} // init with 1,1
|
|
else {if {equal? {array.get {fib4.m} :n} undefined} // if not exists
|
|
then {array.get {array.set! {fib4.m} :n
|
|
{+ {fib4.r {- :n 1}}
|
|
{fib4.r {- :n 2}}}} :n} // compute it
|
|
else {array.get {fib4.m} :n} }}}} // else get it
|
|
{lambda {:n}
|
|
{fib4.r :n}
|
|
{fib4.m} }} // display the number AND all its predecessors
|
|
-> fib4
|
|
{fib4 90}
|
|
-> 4660046610375530000
|
|
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,
|
|
317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,
|
|
165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,
|
|
20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,
|
|
1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,
|
|
72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,
|
|
2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676220,23416728348467684,
|
|
37889062373143900,61305790721611580,99194853094755490,160500643816367070,259695496911122560,420196140727489660,
|
|
679891637638612200,1100087778366101900,1779979416004714000,2880067194370816000,4660046610375530000]
|
|
|
|
5) Binet's formula (non recursive)
|
|
{def fib5
|
|
{lambda {:n}
|
|
{let { {:n :n} {:sqrt5 {sqrt 5}} }
|
|
{round {/ {- {pow {/ {+ 1 :sqrt5} 2} :n}
|
|
{pow {/ {- 1 :sqrt5} 2} :n}} :sqrt5}}} }}
|
|
|
|
{fib5 16} -> 987 (CPU ~ 1ms)
|
|
{fib5 30} -> 832040 (CPU ~ 1ms)
|
|
{fib5 1000} -> 4.346655768693743e+208 (CPU ~ 1ms)
|