How to resolve the algorithm Fibonacci sequence step by step in the Lambdatalk programming language

Published on 12 May 2024 09:40 PM
#Lambdatalk

How to resolve the algorithm Fibonacci sequence step by step in the Lambdatalk programming language

Table of Contents

Problem Statement

The Fibonacci sequence is a sequence   Fn   of natural numbers defined recursively:

Write a function to generate the   nth   Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion). The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition: support for negative     n     in the solution is optional.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Fibonacci sequence step by step in the Lambdatalk programming language

Source code in the lambdatalk programming language

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)

You may also check:How to resolve the algorithm Trigonometric functions step by step in the MAXScript programming language
You may also check:How to resolve the algorithm Pentagram step by step in the Scala programming language
You may also check:How to resolve the algorithm Hello world/Newline omission step by step in the beeswax programming language
You may also check:How to resolve the algorithm Odd word problem step by step in the TUSCRIPT programming language
You may also check:How to resolve the algorithm Ramer-Douglas-Peucker line simplification step by step in the Go programming language