+
1
|
skin
|
login
|
edit
workshop
::
fibonacci
user:anonymous
_h2 fibonacci _p {b Fibonacci}'s numbers are recursively defined like this: {pre if n = 1 or n = 2 then f(n) = 1 else f(n) = f(n-1) + f(n-2) [{map fib4 {serie 1 20}}] } _p There are several ways to compute Fibonacci's numbers. Some of them are shown below using '{lambda talk}. _h5 1) using the {i naïve} version _p We simply follow the previous definition. {pre '{def fib1 {lambda {:n} {if {< :n 3} // n=1 and n=2 -> 1 then 1 else {+ {fib1 {- :n 1}} {fib1 {- :n 2}}} }}} -> {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) } _p The double recursive call leads to a waste of useless computations. This version can't be used in the real world. _h5 2) using a tail-recursive algorithm _p Using an accumulator we can build a simple recursive call. {pre '{def fib2 {def fib2.r {lambda {:a :b :i} {if {< :i 2} then :a else {fib2.r :b {+ :a :b} {- :i 1}} }}} {lambda {:n} {fib2.r 1 1 :n}}} // initialization -> {def fib2 {def fib2.r {lambda {:a :b :i} {if {< :i 2} then :a else {fib2.r :b {+ :a :b} {- :i 1}} }}} {lambda {:n} {fib2.r 1 1 :n}}} '{fib2 16} -> 987 (CPU ~ 1ms) '{fib2 30} -> 832040 (CPU ~2ms) '{fib2 1000} -> 4.346655768693743e+208 (CPU ~ 22ms) } _p This version demonstrates that recursion can be fast. _h5 3) Using memoization _p Following [[memoize|https://xlinux.nist.gov/dads/HTML/memoize.html]] we store results in an array to avoid duplicating computation: {pre '{def fib3 {def fib3.m {array.new}} // init an empty array {def fib3.r {lambda {:n} {if {< :n 2} then {array.get {array.set! {fib3.m} :n 1} :n} // init with 1,1 else {if {equal? {array.get {fib3.m} :n} undefined} // if not exists then {array.get {array.set! {fib3.m} :n {+ {fib3.r {- :n 1}} {fib3.r {- :n 2}}}} :n} // compute it else {array.get {fib3.m} :n} }}}} // else get it {lambda {:n} {fib3.r :n} {fib3.m} }} // display the number AND all its predecessors -> {def fib3 {def fib3.m {array}} {def fib3.r {lambda {:n} {if {< :n 2} then {array.get {array.set! {fib3.m} :n 1} :n} else {if {equal? {array.get {fib3.m} :n} undefined} then {array.get {array.set! {fib3.m} :n {+ {fib3.r {- :n 1}} {fib3.r {- :n 2}}}} :n} else {array.get {fib3.m} :n} }}}} {lambda {:n} {fib3.r :n} {fib3.m} }} } {pre {@ style="word-wrap: break-word; white-space:pre-wrap;"} '{fib3 50} -> {fib3 50} } _p Works fine! Note that {b fib3.m} should be embedded as a local variable, {b :mem}, in the function {b fib3.r} and so cleaned after use. _h5 4) Using the Dijkstra Algorithm _p Following [[https://rosettacode.org/wiki/Fibonacci_sequence#Scheme|https://rosettacode.org/wiki/Fibonacci_sequence#Scheme]] {pre '{def fib4 {def fib4.r {lambda {:a :b :p :q :count} {if {= :count 0} then :b else {if {= {% :count 2} 0} then {fib4.r :a :b {+ {* :p :p} {* :q :q}} {+ {* :q :q} {* 2 :p :q}} {/ :count 2}} else {fib4.r {+ {* :b :q} {* :a :q} {* :a :p}} {+ {* :b :p} {* :a :q}} :p :q {- :count 1}} }}}} {lambda {:n} {fib4.r 1 0 0 1 :n} }} -> {def fib4 {def fib4.r {lambda {:a :b :p :q :count} {if {= :count 0} then :b else {if {= {% :count 2} 0} then {fib4.r :a :b {+ {* :p :p} {* :q :q}} {+ {* :q :q} {* 2 :p :q}} {/ :count 2}} else {fib4.r {+ {* :b :q} {* :a :q} {* :a :p}} {+ {* :b :p} {* :a :q}} :p :q {- :count 1}} }}}} {lambda {:n} {fib4.r 1 0 0 1 :n} }} '{fib4 16} -> 987 (CPU ~ 2ms) '{fib4 30} -> 832040 (CPU ~ 2ms) '{fib4 1000} -> 4.346655768693743e+208 (CPU ~ 3ms) } _p Obfuscated but very fast. _h5 5) Using the Binet's formula _p The mathematician [[Jacques Philippe Binet|https://en.m.wikipedia.org/wiki/Jacques_Philippe_Marie_Binet]] discovered a beautiful formula avoiding any recursion and based on the golden number {b φ}: {pre {b f(n) = (φ1{sup n}-φ2{sup n})/√5}, where φ1 =(1+√5)/2, φ2 =(1-√5)/2 } {pre {@ style="white-space:pre-wrap;"} '{def fib5 {lambda {:n} {let { {:n :n} {:sqrt5 {sqrt 5}} } {round {/ {- {pow {/ {+ 1 :sqrt5} 2} :n} {pow {/ {- 1 :sqrt5} 2} :n}} :sqrt5}} }}} -> {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) } _p Elegant and fast. _h5 6) the golden rectangle _p The golden rectangle is built on "spiraling" adjacent squares whose sizes are the Fibonacci's numbers, [{map fib4 {serie 1 13}}]. _p We use the lambdatalk's {b turtle} function and, of course, the Binet's formula, {b fib5}, built on the golden number {b φ}. {pre '{def GR {def GR.square {lambda {:d} M:d T90 M:d T90 M:d T90 M:d T90 M:d T90 M:d}} {def GR.spiral {lambda {:d :n} {if {< :n 0} then else {GR.square :d} {GR.spiral {* 2 {fib5 :n}} {- :n 1}} }}} {lambda {:n} {GR.spiral 0 :n} }} -> {def GR {def GR.spiral {lambda {:d :n} {if {< :n 0} then else M:d T90 M:d T90 M:d T90 M:d T90 M:d T90 M:d {GR.spiral {* 2 {fib5 :n}} {- :n 1}} }}} {lambda {:n} {GR.spiral 0 :n}} } } _p And we call the whole in an SVG frame. {pre '{svg {@ width="600px" height="800px"} {polyline {@ points="{turtle 60 800 0 {GR 13}}" stroke="#f00" fill="#ffc"}} } } {svg {@ width="600px" height="800px"} {polyline {@ points="{turtle 60 800 0 {GR 13}}" stroke="#f00" fill="#ffc"}} } _h5 some references _ul [[wikipedia|http://en.wikipedia.org/wiki/Fibonacci_number]] _ul [[fast-fibonacci-algorithms|https://www.nayuki.io/page/fast-fibonacci-algorithms]] _ul [[http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/|http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html#CALCfibsq]] _ul [[https://lee-phillips.org/lispmath/|https://lee-phillips.org/lispmath/]] _ul [[https://rosettacode.org/wiki/Fibonacci_sequence|https://rosettacode.org/wiki/Fibonacci_sequence#lambdatalk]] _ul [[https://blog.des.io/posts/2018-03-08-fibonacci.html|https://blog.des.io/posts/2018-03-08-fibonacci.html]]