<div dir="ltr">Hi all,<div><br></div><div>I was exploring the <i>mathematical functions</i> category of the class <i>Integer</i> and a I didn't find the very well-known Fibonacci function ("<i>f(n)=f(n-1)+f(n-2)"</i>) , so I decided to implement it. I think this will be interesting due to the complexity I found (wich is O(log(n))!!).</div><div><ul><li>A simple way to implement it is by writing the direct recursive mathematical recurrence relation. This would be exponential.</li><li>An iterative solution wouldn't do all this repeated work, therefore it would be lineal.</li><li>I used a dynamic-programming-divide-and-conquer-aproach wich computes the n-th Fibonacci number in O(log(n)). I think from this comment you can see why it works: <font color="#000000"><a href="https://math.stackexchange.com/questions/1834242/derivation-of-fibonacci-logn-time-sequence">https://math.stackexchange.com/questions/1834242/derivation-of-fibonacci-logn-time-sequence</a>.</font></li></ul><div><font color="#000000">Here are some running times:</font></div></div><div>exponential --> [1 to: 40 do: [:elem | elem fibonacciNumber]] timeToRun   38536 <font color="#000000"><br></font></div><div>lineal -->           [1 to: 10000 do: [:elem | elem fibonacciNumber]] timeToRun.   25558 </div><div>logarithmic -->  [1 to: 10000 do: [:elem | elem fibonacciNumber]] timeToRun.   1471<br></div><div><br></div><div>I leave you all three implementations, let me know what you think,</div><div>Agustín</div><div><br></div><div><br></div><div><br></div></div>